Data Structures and Algorithms
Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.
Why DSA Now
From using collections to choosing strategies
In Intermediate Java, you built a practical mental model for List, Set, Map, ownership, and implementation tradeoffs.
Now we move one level deeper: Data Structures and Algorithms asks:
- What work does this operation actually do?
- How does performance change as input grows?
- Which structure makes the algorithm simple, safe, and fast?
For interviews, DSA is the shared language of problem solving. For engineering, it is how you avoid accidental slowdowns in APIs, data pipelines, and services.
One sentence to carry through this lesson: data structures organize access; algorithms organize decisions.

Measure The Growth
Big-O is about scale, not stopwatch time
When engineers discuss complexity, we usually care about growth rate.
If input size doubles:
-
O(1)stays about the same -
O(log n)grows slowly -
O(n)roughly doubles -
O(n log n)grows faster than linear -
O(n²)can become painful quickly
In Java, implementation constants matter too: allocation, hashing, cache locality, object overhead, and JVM warmup. But Big-O helps you choose the right family of solution before tuning details.
Below, both searches are correct. The difference is how their work grows.
```java
import java.util.*;
public class Main {
static int linearSearch(int[] a, int target) {
int checks = 0;
for (int x : a) {
checks++;
if (x == target) break;
}
return checks;
}
static int binarySearchChecks(int[] a, int target) {
int lo = 0, hi = a.length - 1, checks = 0;
while (lo <= hi) {
checks++;
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return checks;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return checks;
}
public static void main(String[] args) {
int n = 1_000_000;
int[] data = new int[n];
for (int i = 0; i < n; i++) data[i] = i;
int target = 999_999;
System.out.println("Linear checks: " + linearSearch(data, target));
System.out.println("Binary checks: " + binarySearchChecks(data, target));
}
}
```
Complexity Check
You have a sorted array of n integers. You repeatedly cut the remaining search range in half until you find the target or prove it is absent.
What is the time complexity?
Pick Access Shape
Start with the access pattern
Since you already practiced Java collection tradeoffs in Intermediate Java, we will not re-teach ArrayList, HashSet, or HashMap here. Instead, ask what kind of access your algorithm needs.
ArrayList
Direct position access
Fast membership
HashSet
Avoid repeated scans
Key-to-value association
HashMap
Store derived facts
Process newest first
Stack / Deque
Backtracking, parsing
Process oldest first
Queue / Deque
BFS, scheduling
Ordered min/max access
Heap / priority queue
Repeated best-next choice
Relationships
Graph
Dependencies, networks, flows
A strong DSA solution often starts as a sentence: I need to repeatedly access X, so I will store Y.

Hash For Memory
Trading memory for fewer repeated decisions
A common interview and production pattern is: store what you have learned so you do not recompute it.
For example, frequency counting is useful in logs, events, deduplication, stream summaries, and many coding problems.
Here we use a HashMap<String, Integer> as an algorithmic tool: not just a container, but a compact memory of facts discovered during a scan.
Time: O(n) average-case scan.
Space: O(k) where k is the number of distinct words.
```java
import java.util.*;
public class Main {
public static void main(String[] args) {
List<String> events = Arrays.asList(
"login", "purchase", "login", "logout", "login", "purchase"
);
Map<String, Integer> counts = new HashMap<>();
for (String event : events) {
counts.put(event, counts.getOrDefault(event, 0) + 1);
}
System.out.println("Event counts: " + counts);
System.out.println("login count: " + counts.get("login"));
}
}
```
HashMap Guarantee
True or false: If a solution uses a HashMap, every operation is guaranteed to be O(1) in all cases.
Patterns Beat Memorization
Most DSA problems are variations
You do not need to memorize thousands of solutions. You need to recognize the shape of the problem.
Useful patterns:
- Two pointers: move through a sequence from one or both ends
- Sliding window: maintain a valid range while expanding and shrinking
- Prefix sums: convert repeated range totals into fast lookups
- Hash memory: remember seen values, counts, or positions
- BFS / DFS: explore connected states or relationships
- Heap: repeatedly choose the smallest, largest, or highest priority item
- Dynamic programming: reuse answers to overlapping subproblems
For a Java engineer, the key is translating the pattern into clean state: indexes, queues, maps, sets, and invariants.

Traversal Tool
In breadth-first search, we usually process nodes in first-in, first-out order using a ______.
Graph Traversal
Graphs model relationships
Graphs show up whenever entities connect:
- services calling services
- tasks depending on tasks
- users connected to users
- tables connected by references
- states connected by valid moves
BFS is a good first traversal when you want shortest distance in an unweighted graph, level-by-level exploration, or dependency-style reachability.
The code below builds a tiny graph and prints each node's distance from A.
```java
import java.util.*;
public class Main {
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("D"));
graph.put("C", Arrays.asList("D", "E"));
graph.put("D", Arrays.asList("F"));
graph.put("E", Arrays.asList());
graph.put("F", Arrays.asList());
Map<String, Integer> distance = new HashMap<>();
Queue<String> queue = new ArrayDeque<>();
distance.put("A", 0);
queue.add("A");
while (!queue.isEmpty()) {
String node = queue.remove();
for (String next : graph.getOrDefault(node, List.of())) {
if (!distance.containsKey(next)) {
distance.put(next, distance.get(node) + 1);
queue.add(next);
}
}
}
System.out.println("Distances from A: " + distance);
}
}
```
Practice Like Engineer
A repeatable DSA workflow
When solving a problem, use this loop:
- Restate the task in your own words.
-
Name the input size:
n,m, number of nodes, number of edges, etc. - Start brute force to clarify correctness.
- Find repeated work or expensive access.
- Choose a structure that removes that pain.
- State complexity before coding.
- Code small, test edges: empty input, one item, duplicates, extremes.
This is also how you communicate in interviews: not by instantly producing magic code, but by showing structured reasoning.
Next, Database Design will shift from in-memory structures to durable data models; the same habit of choosing structures based on access patterns will carry forward.
