Day 1 — Data Structures & Algorithms, the essentials

It's the night before a coding round and your notes are a mess — thirty data structures, a hundred algorithms, and no idea which ones actually show up. Breathe. The truth is that a handful of ideas carry almost every interview question you'll ever be asked. Today you and I will lay them out on one table, see how they fit together, and leave you able to reach for the right one under pressure.

This is Day 1, and it's on the house. If it clicks, the rest of the week goes deep on the language, concurrency, frameworks, and full machine-coding rounds.

Let's start in a kitchen

Watch a good cook work. Knives in one block, spices in a rack, pots hanging on the wall. Nothing is "better" than anything else — each tool just makes one job cheap. You wouldn't stir soup with a whisk or chop onions with a spoon.

Data structures are exactly that: a drawer of tools where each one makes a different operation cheap. The entire skill is matching your hot operation — the thing you do again and again — to the drawer that makes it fast.

Keep that picture in your head. Every question below is really asking: which drawer makes this cheap?

The four you must know cold

Arrays and lists — order in a line

An array is one solid block of memory. Because the slots sit next to each other, the index is really an address: element i lives a fixed jump from the start, so you reach it in a single step. A linked list gives that up — its nodes are scattered and joined by pointers — to buy cheap splicing at the ends.

int[] a = { 7, 3, 9, 4, 8, 1 };
int third = a[2];                 // O(1) — jump straight to the slot
 
Deque<Integer> list = new ArrayDeque<>();
list.addFirst(10);                // O(1) — splice a new end on
list.addLast(20);

Stacks and queues — same boxes, opposite doors

A stack is last-in-first-out: you add and remove from the top, like a stack of plates. A queue is first-in-first-out: you join the back and leave from the front, like a fair line. That single difference — which door you use — is the whole story, and it decides a surprising number of problems (undo, backtracking, and depth-first search want a stack; scheduling and breadth-first search want a queue).

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
int top = stack.pop();            // 2 — last in, first out
 
Queue<Integer> queue = new ArrayDeque<>();
queue.add(1); queue.add(2);
int front = queue.poll();         // 1 — first in, first out

Hash maps and sets — look up by key

This is the one that turns slow solutions fast. A hash map runs your key through a hash function to a bucket index, so instead of scanning a list you jump straight to the slot — average O(1) to store and to fetch. A set is the same trick when you only care whether something is present.

The classic move: whenever a brute force is "for every pair, check…", ask what you'd need to have remembered to answer in one pass. Usually a map is the answer.

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) {
            return new int[] { seen.get(need), i };
        }
        seen.put(nums[i], i);         // remember where each value lives
    }
    return new int[] {};
}

Trees and graphs — relationships and paths

When data is connected — a folder tree, a social graph, a road map — you explore it one of two ways. Breadth-first search fans out level by level using a queue; it finds the shortest path in an unweighted graph. Depth-first search follows one branch to the bottom before backing up, using a stack (or recursion).

List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
    List<Integer> order = new ArrayList<>();
    Set<Integer> seen = new HashSet<>();
    Queue<Integer> queue = new ArrayDeque<>();
    queue.add(start);
    seen.add(start);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int next : graph.getOrDefault(node, List.of())) {
            if (seen.add(next)) {         // add() returns false if already present
                queue.add(next);
            }
        }
    }
    return order;
}

Two cousins worth a mention: a heap (priority queue) always hands you the next smallest item in O(log n) — perfect for "top-k" and Dijkstra — and a trie stores strings by shared prefix, which is how autocomplete stays instant.

The algorithms that turn structures into answers

Structures are the nouns; algorithms are the verbs that act on them. Five families crack almost every coding round — learn to spot the shape of a problem and the right one picks itself. Each is a short template worth committing to memory.

Sorting — the setup move

Half the time your first move is to sort, because a sorted array unlocks binary search, two-pointer sweeps, and greedy choices. You rarely write the sort yourself — you call the library's O(n log n) sort — but you must know that cost, and that any custom order is one comparator away.

int[] a = { 5, 2, 8, 1, 9 };
Arrays.sort(a);                          // O(n log n) — a is now 1, 2, 5, 8, 9
 
// Sort objects by a field and the problem often falls out in a single pass.
intervals.sort((x, y) -> x.start - y.start);   // merge / scheduling problems start here

Binary search — halve the space

On a sorted space you never scan; you halve, so a million items cost about twenty steps. The same move solves a sneakier class too: when you can test a candidate answer quickly, binary-search the answer itself — the smallest speed, the largest weight — not the array.

int binarySearch(int[] sorted, int target) {
    int lo = 0, hi = sorted.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;     // avoids integer overflow
        if (sorted[mid] == target) return mid;
        if (sorted[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;                            // not found
}

Two pointers & the sliding window — one pass, no nesting

When a brute force is "check every pair" or "try every sub-array", two indices walking the array collapse O(n²) to O(n). Two pointers converge from the ends (pairs that sum to a target, palindromes); a sliding window grows on the right and shrinks from the left to hold a running condition — "the longest stretch that still fits".

int longest(int[] a, int limit) {
    int left = 0, sum = 0, best = 0;
    for (int right = 0; right < a.length; right++) {
        sum += a[right];                      // grow on the right
        while (sum > limit) sum -= a[left++]; // too big? shrink from the left
        best = Math.max(best, right - left + 1);
    }
    return best;                              // works on non-negative numbers
}

BFS & DFS — explore anything connected

Any question about reachability, shortest hops, or connected pieces is a graph walk. You met breadth-first search above — level by level with a queue, which finds the shortest path in an unweighted graph. Its twin, depth-first search, dives down one branch to the bottom before backing up, using recursion (or a stack); it is the tool for cycle detection and topological order.

void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> seen) {
    if (!seen.add(node)) return;          // add() is false if already visited
    for (int next : graph.getOrDefault(node, List.of())) {
        dfs(next, graph, seen);           // go all the way down before going wide
    }
}

Recursion → dynamic programming — stop redoing work

This is the family that separates "it works" from "it works in time". You solve a big problem from smaller identical ones — but naive recursion rebuilds the same sub-problem a branching number of times. Computing the n-th Fibonacci number the obvious way makes O(2ⁿ) calls for an answer you could reach in n steps.

The fix is a single line: remember each answer the first time you compute it (memoize), and the exponential avalanche on the left collapses to the linear pass on the right.

long fib(int n, long[] memo) {
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];     // already solved — reuse it
    return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}

That memo line is the whole seed of dynamic programming — the technique that turns "too slow" into "instant" on the hardest questions interviewers hand you.

Big-O in one picture

Every choice above is really about how the cost grows as your input n grows. You don't need the maths — you need the ladder, and the instinct to know which rung you're standing on.

If an interviewer asks "can you do better?", they're almost always asking you to move one rung up this ladder — usually by spending memory (a hash map) to buy time.

The questions asked most

Why is a hash map "O(1)" if it has to handle collisions? Because with a decent hash and a low load factor, collisions are rare and buckets stay tiny, so the average cost is constant. The worst case is O(n), which is why order-sensitive or adversarial cases sometimes prefer a balanced tree map (O(log n) guaranteed).

When BFS vs. DFS? BFS for the shortest path in an unweighted graph or anything "nearest first". DFS for exploring all the way down — cycle detection, topological order, or when the recursion mirrors the problem (like a tree).

How do I get the top-k elements efficiently? A heap of size k. Push everything; keep only the k best. O(n log k) instead of sorting the whole thing.

HashMap or array as a lookup? If your keys are small dense integers (like ASCII characters), a plain array is your map and it's faster. Otherwise, a hash map.

Practice — five to try tonight

Do these on paper first, then in code. Aim to name the structure and pattern before you write a line.

1. Contains duplicate — return whether an array has any repeated value. (Set.)
2. Valid parentheses — is a string of brackets balanced? (Stack.)
3. Longest substring without repeating characters — (sliding window + set.)
4. First bad version — find the first failing version in a sorted range. (Binary search on the answer.)
5. Number of islands — count connected land cells in a grid. (BFS or DFS.)

The interview corner

Clarifying questions to ask first

• What are the input sizes? (Decides whether O(n²) is even acceptable.)
• Can the input be empty, sorted, or contain duplicates or negatives?
• Do you want the value, the index, or all matches?

The follow-up ladder

1. "What's the brute force?" — State it and its cost. Never skip this; it shows you can always produce something correct.
2. "Can you do better?" — Trade memory for time: a hash map or set to remember what you've seen.
3. "What if the data doesn't fit in memory?" — Stream it, or sort externally, or sketch it (a Bloom filter for membership).
4. "What's the space complexity?" — Be ready to give both time and space, and to say which you optimised.
5. "Now make it thread-safe / concurrent." — That's Day 4; know that a plain HashMap is not safe under concurrent writes.

Mistakes that fail the round

• Jumping to code before stating the approach and its Big-O out loud.
• Off-by-one errors in binary search — use lo + (hi - lo) / 2 and be explicit about <= vs <.
• Forgetting the empty / single-element / all-duplicates edge cases.

Where to go from here

Tomorrow, Day 2 goes deep on the language itself — the core Java questions interviewers keep circling back to. But if you want the long-form version of two structures that love to show up, the reading path below picks up exactly where this lesson leaves off.