DEV Community: Prakhar Srivastava

Big O Notation Explained: Derive It, Don't Memorize It

Prakhar Srivastava — Sat, 23 May 2026 11:26:16 +0000

You can recite that binary search is O(log n) and nested loops are O(n²). That recitation stops helping the moment an interviewer writes an unfamiliar function on the whiteboard and asks you to analyse it. The useful version of Big O is the one you can derive, not the one you can look up.

TL;DR: Big O describes how an algorithm's work grows as input size grows. The interview skill isn't naming complexities from memory. It's counting how many times the dominant operation runs as a function of input size and watching what dominates as the input gets large.

What Big O actually measures

Big O describes the upper bound on how an algorithm's running time or space usage grows as its input grows. That word, grows, is the one that matters. It doesn't tell you that binary search takes exactly 20 comparisons on an array of a million elements. It tells you that doubling the array adds roughly one more comparison. The relationship between input and work is the thing being measured.

There are two simplifications Big O does on purpose. It drops constants, so O(3n) becomes O(n). And it drops lower-order terms, so O(n² + n) becomes O(n²). Both simplifications stop mattering at scale, which is the only scale the notation is built for. If n is 10, the constants matter. If n is 10 million, the highest-order term swallows everything else.

The "upper bound" piece is the worst case. An algorithm marked O(n²) might finish faster on certain inputs. It just won't do worse than quadratic. Worst-case behaviour is what interviewers care about because best-case behaviour doesn't protect you from the input that breaks the solution.

The five growth classes you'll actually see

Every algorithm you'll meet in an interview lives in one of these.

Complexity	Name	n=10	n=1,000	n=1,000,000
`O(1)`	Constant	1	1	1
`O(log n)`	Logarithmic	3	10	20
`O(n)`	Linear	10	1,000	1,000,000
`O(n log n)`	Linearithmic	33	10,000	20,000,000
`O(n²)`	Quadratic	100	1,000,000	1,000,000,000,000

The jump from O(n) to O(n²) is where most interview problems live. A brute-force solution that checks every pair in an array is quadratic. The optimised version using a hash map or two pointers drops it to linear. At a million elements, that's the difference between a million operations and a trillion.

O(n log n) is worth a side note. It's the theoretical floor for comparison-based sorting. Merge sort, heapsort, well-implemented quicksort all sit there. The number isn't arbitrary. It falls out of information theory.

Where the derivation skill lives

Most Big O guides hand you a lookup table. Binary search is logarithmic, merge sort is linearithmic, hash insert is constant amortised. Fine for reference. Useless when the interviewer hands you a function you've never seen.

The interview skill is derivation. Counting the dominant operation as a function of input size. The cleanest way to build that skill is to use Big O on code where you don't already know the answer.

Take a single loop. One pass through n elements does n units of work, so it's O(n). Two nested loops over the same array multiply: outer runs n times, inner runs up to n times, total work is n × n which is O(n²). The inner loop in something like a pair-check usually doesn't run the full n each time. The first outer pass runs the inner n-1 times, the next runs n-2, and so on. The sum is n(n-1)/2, which simplifies to O(n²) because the constant 1/2 and the linear term drop out.

The halving pattern, derived from scratch

Take binary search. It's the cleanest example of how O(log n) actually shows up.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Each loop iteration cuts the search space in half. Start with n elements, one comparison leaves n/2, two leave n/4, three leave n/8. You stop when the space hits 1. The question is: how many times can you halve n before reaching 1?

The answer is log₂(n). An array of a million elements needs at most 20 comparisons. A billion needs at most 30. That's why binary search feels almost instant on large inputs.

The shape generalises. Any loop where the search space shrinks by a constant fraction each step is logarithmic. You'll see the same shape when an index doubles (i *= 2), when a range halves, when a balanced-tree walk descends one level per iteration. The derivation isn't memorised. It's derived from the mechanic.

I keep coming back to this one because it's the easiest place to feel the difference between memorising and deriving. Once you've drawn the halving five or six times on a whiteboard, recognising it in unfamiliar code stops being effortful. The searching lesson on my own site walks through the halving invariant frame by frame, then extends the same derivation to predicate search problems where you're binary searching on an answer space instead of an array. Same mechanic, different surface.

A five-step derivation protocol

The five steps below work on any code, whether you've seen it before or not. They're the steps I use myself when an interviewer drops a function I don't recognise.

Identify the dominant operation. Inside the inner loop, the recursive call, the comparison. Whatever you'd count if you were ticking marks on paper.
Express the iteration count as a function of n. A single loop is n. Nested loops multiply. A halving loop is log n. A recursive call that branches twice and reduces by 1 each level builds a tree of depth n, giving 2ⁿ.
Sum across the levels. Single loop: n × O(1) = O(n). Recursive tree: branching factor b, depth d, total nodes roughly b^d. Multiply by the work per node.
Drop constants and lower-order terms. 3n + 5 becomes O(n). n² + n becomes O(n²). The simplification only matters because the notation is about behaviour at large n, where the highest-order term dominates everything.
Do the same thing for space. Track auxiliary memory. Count call-stack frames in recursion. Count the size of any data structure that grows with input.

The protocol works on hash-map resize, on BFS over a graph, on string concatenation in a loop, on dynamic programming with memoisation. It works on code you've never seen. That's the whole point.

A worked example on recursion

Take naive Fibonacci.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

The dominant operation is the recursive call. Each call to fib(k) makes two more calls. The call tree branches at every level. Depth is roughly n. Total nodes are roughly 2ⁿ. That's O(2ⁿ), which is why naive Fibonacci is unusably slow even for moderate n.

Adding memoisation collapses the tree to O(n) because each subproblem fib(k) is computed exactly once. The work per subproblem is constant, and there are n of them. Same recursion, different complexity, derived from the same counting.

The space complexity of the naive version is O(n) from the call stack, not O(2ⁿ) from the tree. At any moment, only one root-to-leaf path is on the stack. The branches aren't all simultaneously in memory. Easy mistake to make. Easy to catch if you're explicit about which operations are happening at the same time versus across the whole run.

Space complexity, including the parts that get forgotten

Time complexity gets most of the attention. Space gets asked about often enough that ignoring it loses interview points.

Space complexity measures the additional memory your algorithm uses beyond the input. The input array itself doesn't count toward auxiliary space. Sorting in place is O(1) auxiliary. Copying the array first is O(n) auxiliary for the same sort.

The piece that catches even experienced engineers is the recursive call stack. Every recursive invocation adds a frame. A function that recurses n levels deep uses O(n) stack space, even if it doesn't allocate any explicit data structure.

def sum_recursive(arr, i=0):
    if i == len(arr):
        return 0
    return arr[i] + sum_recursive(arr, i + 1)
    # Time: O(n), Space: O(n) due to call stack

The iterative version of the same logic uses constant space. That's the concrete reason converting recursion to iteration is sometimes worth the extra code.

Common space-complexity traps worth knowing by name:

Forgetting to count the recursive call stack.
Counting the input array size as auxiliary space.
Ignoring that hash maps and sets grow with input.
Missing that repeated string concatenation in a loop creates O(n²) total memory because each new string is a fresh allocation.

Where this shows up in interviews

Interviewers don't ask you to recite that merge sort is O(n log n). They hand you a function and ask you to analyse it, or they ask you to improve a brute-force O(n²) solution to O(n) or O(n log n). Derivation, not recall.

That's where a lot of self-taught preparation falls apart. You can grind hundreds of problems and memorise their complexities. If you haven't drilled the reasoning process of counting operations as a function of input, novel code still feels opaque. Learning science has a name for the right drill here: elaborative interrogation. Asking yourself why each operation contributes the work it does, rather than accepting the labelled answer.

Before Big O is derivable, you read a solution and think that looks fast. After, you look at the same solution and know it's O(n log n) because you can point at the divide step and the merge step independently. You can explain why adding a hash map drops a nested loop from quadratic to linear. You can evaluate code you've never seen and tell the interviewer how it scales.

At that point, Big O stops being a label you apply after the fact. It becomes a tool you reason with.

I wrote a longer version on my own blog that includes amortised analysis (the hash-map resize derivation in particular) and the recursion-tree shortcuts for divide-and-conquer.

What's a problem where the textbook complexity made sense to you only after you traced the work by hand? I'm curious which derivations clicked first for people, and which ones stayed stubborn.

BFS vs DFS: The Invariant Decides, Not Your Preference

Prakhar Srivastava — Fri, 22 May 2026 19:56:26 +0000

Two algorithms visit every node in a graph. Pick whichever you remember and most of the time nothing goes wrong. Then an interview hands you a shortest path problem, you reach for DFS because it's faster to write recursively, and you hand back a path that's valid and twice as long as the optimal one. No error. Just a quietly wrong answer you can't debug with the clock running.

TL;DR: BFS uses a queue and processes nodes in distance order, so the first time it reaches a node, that path is the shortest in an unweighted graph. DFS uses a stack, commits to one branch fully, and naturally exposes cycles, topological order, and connected components. The data structure creates the guarantee. The guarantee decides which problems each one can solve.

The queue and the stack create different guarantees

BFS and DFS aren't two flavors of the same traversal. They hold different invariants, and the invariant is what decides which problems each one can solve.

Breadth first search processes every node at distance 1 from the source before any node at distance 2, every node at distance 2 before distance 3, and so on. It uses a queue to hold that order. You get a level by level sweep outward from the start.

Depth first search drives down one path as far as it goes, then backtracks. It uses a stack, or the call stack when you write it recursively, to remember where it came from. One branch gets fully exhausted before the next one is touched.

That sounds academic until it costs you a problem. The order each one visits in is not a cosmetic difference. It's the whole reason one of them can answer a question the other can't.

Why BFS finds the shortest path and DFS doesn't

The queue is the entire reason BFS works for shortest paths. A queue is first in, first out. When you enqueue the neighbours at distance d, they sit behind any remaining distance d-1 nodes and ahead of every future distance d+1 node. The queue enforces distance order without you ever tracking distance explicitly.

The stack is last in, first out. The most recently pushed node gets processed next, so you keep diving deeper along whichever neighbour you pushed last. DFS might reach a node through a 7 edge path before it ever finds the 2 edge one. BFS can't do that, because it finishes every 2 edge path before it starts any 7 edge path.

I used to reach for whichever traversal I'd practiced most recently. The first time I watched that break a real solution, it was on a grid.

A grid problem where the wrong traversal costs you

Take a 2D grid where 0 is passable and 1 is a wall. You want the minimum number of steps from the top left corner to the bottom right, moving in four directions. Every move costs the same one step, so BFS's distance guarantee applies directly.

from collections import deque

def min_steps(grid):
    rows, cols = len(grid), len(grid[0])
    goal = (rows - 1, cols - 1)
    if grid[0][0] == 1 or grid[goal[0]][goal[1]] == 1:
        return -1

    queue = deque([((0, 0), 0)])
    seen = {(0, 0)}
    while queue:
        (r, c), dist = queue.popleft()
        if (r, c) == goal:
            return dist
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in seen:
                seen.add((nr, nc))
                queue.append(((nr, nc), dist + 1))
    return -1

The first time popleft() returns the goal, dist is the shortest distance. Nothing else can reach the goal in fewer steps, because the queue processed all the closer cells first.

Now swap queue.popleft() for a stack pop() and you have DFS. The first time it reaches the goal, the distance could be any valid length, often a wandering one. The code looks almost identical. The guarantee is gone.

The memory trade nobody mentions

The two algorithms also use memory differently, and the graph's shape decides which is cheaper. BFS holds the entire frontier at once. In a balanced tree with branching factor b and depth d, the queue holds O(b^d) nodes at the widest level. DFS holds at most O(d) nodes on the stack, one per level of depth. For a deep, narrow graph, DFS is far lighter. For a shallow, wide one, either works.

DFS also has a recursive form BFS can't match. When you write DFS recursively, the call stack is the stack, so you manage no explicit collection at all. That maps cleanly onto problems that are recursive by nature: trees, nested configurations, expression parsing. BFS has no equivalent, because a queue isn't built into the call stack.

How I decide which one to reach for

The question I ask now is simpler than any rule of thumb: does this problem need a distance guarantee or a structural property? Distance guarantee points at BFS. Structural property, meaning cycles, ordering, or connectivity, points at DFS.

Reach for BFS when the problem needs:

Shortest path: minimum steps in a grid, shortest word transformation, nearest distance to a target, all in an unweighted graph.
Level order processing: anything handled layer by layer, like a binary tree level order traversal or finding every node at distance k.
Nearest match: BFS hits the closest valid node first because it explores in distance order.

Reach for DFS when the problem needs:

Cycle detection: DFS tracks which nodes are currently on the recursion stack, so a back edge to one of them means a cycle.
Topological order: DFS finish times, reversed, give a valid topological ordering for a directed acyclic graph.
Connected components: run DFS from an unvisited node, mark everything reachable, repeat from the next unvisited node.
Path enumeration: backtracking and all source to target paths, because DFS explores one complete path before trying alternatives.

One trap worth naming: BFS assumes every edge costs the same. The moment edges carry weights, its distance order no longer holds, and you need Dijkstra's algorithm, or Bellman-Ford if weights can go negative.

I wrote a longer version on my own blog that traces both algorithms step by step on the same six node graph and walks through a directed cycle detection example with code.

Which graph problem finally made the BFS vs DFS choice obvious for you, the one where picking wrong actually broke your solution rather than just slowing it down?

Backtracking Algorithm Explained: An N-Queens Walkthrough

Prakhar Srivastava — Thu, 21 May 2026 16:03:35 +0000

The textbook line on backtracking is "try everything and undo what doesn't work." Accurate, and useless. It tells you nothing about how to write a solution to a problem you've never seen. Backtracking isn't trial and error. It's a depth first walk over a state space tree with a rule for quitting a branch the moment it can't lead anywhere valid.

Once you see it that way, the trick stops being clever and starts being mechanical. Every backtracking problem you'll meet runs the same loop. The only thing that changes is what you're choosing and what counts as a dead branch.

TL;DR: Backtracking builds a solution one decision at a time and walks a state space tree with DFS. When a partial solution breaks a constraint, you abandon that branch and try the next option. The whole algorithm is choose, check, undo. The variation between problems is what you choose and what the constraints are.

What backtracking actually is

Picture a tree where the root is the empty solution. Each edge is a decision: place a queen in a column, add a character to a string, include an element in a subset. Each node is the partial solution you have so far. Leaves are either complete valid answers or dead ends where a constraint already broke.

Exhaustive search builds every leaf and checks each one after the fact. Backtracking checks on the way down and stops descending the instant a partial answer is doomed. On a board with n queens, exhaustive search inspects all n^n configurations. Backtracking inspects a sliver of that, because it never places a queen in a row where a conflict already exists.

For tiny inputs the difference is academic. Generate every subset of a 10 element array and pruning saves you nothing, there's nothing to prune. The advantage shows up when constraints are tight and the search space is large, which is exactly the shape of the problems interviewers like.

The choose, check, undo skeleton

Strip away the problem specifics and every backtracking routine does three things in a loop:

Choose: extend the current partial solution with one option.
Check: test whether that extension violates a constraint. If it does, don't recurse into it.
Undo: after the recursive call returns, reverse the choice so the next option starts from a clean state.

That last step is the one people forget, and it's the one that quietly produces wrong answers instead of crashes. If you append to a path or flip a visited flag and never reverse it, later branches inherit corrupted state from earlier ones.

Walking N-Queens by hand

N-Queens is the cleanest place to watch this run. Place n queens on an n x n board so none attack each other, no shared row, column, or diagonal. The tree has n levels, one per row, and at each level you pick a column. The branching factor starts at n and shrinks as conflicts knock out columns.

Here's a partial trace for n=4, watching where pruning kicks in:

Row 0: try column 0
  Row 1: column 0 -> PRUNE (same column)
  Row 1: column 1 -> PRUNE (diagonal with row 0)
  Row 1: column 2 -> ok, partial [0, 2]
    Row 2: every column conflicts -> BACKTRACK
  Row 1: column 3 -> ok, partial [0, 3]
    Row 2: column 1 -> ok, partial [0, 3, 1]
      Row 3: every column conflicts -> BACKTRACK
    ...all of row 1's options exhausted -> BACKTRACK
Row 0: try column 1
  Row 1: column 3 -> [1, 3]
    Row 2: column 0 -> [1, 3, 0]
      Row 3: column 2 -> [1, 3, 0, 2] -> SOLUTION

Without pruning you'd evaluate all 4^4 = 256 placements. With it, the algorithm touches roughly 20 nodes before the first solution. Early constraint checks did the heavy lifting. The code is just the skeleton with the constraint filled in:

def solve_n_queens(n):
    solutions = []
    board = []

    def is_valid(row, col):
        for prev_row, prev_col in enumerate(board):
            if prev_col == col:
                return False
            if abs(prev_row - row) == abs(prev_col - col):
                return False
        return True

    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if is_valid(row, col):
                board.append(col)     # choose
                backtrack(row + 1)    # explore
                board.pop()           # undo

    backtrack(0)
    return solutions

board.append(col) is the choose. is_valid(row, col) is the check that prunes. board.pop() is the undo. The domain looks completely different on Sudoku or word search, but the three pieces are always sitting right there.

The three shapes backtracking takes

Backtracking problems aren't all the same. They sort into three shapes by how much you can prune:

Unconditional enumeration. Produce every arrangement with no extra rule: all subsets, all letter combinations of a phone number. The tree branches at every position and every leaf is valid output. Nothing to prune, you walk the whole tree.
Conditional enumeration. Same branching shape, but a constraint kills branches mid construction: valid parentheses, combinations that sum to a target, permutations of distinct elements. Some branches die before the leaf because the partial answer already broke the rule.
Backtracking search. Find one or more configurations that satisfy a global constraint: N-Queens, Sudoku, maze pathfinding. Pruning is heaviest here because each placement constrains every later one.

The reason this taxonomy is worth memorising: it tells you how aggressive your pruning should be before you write a line. Search problems want constraint checks at every level. Unconditional enumeration wants none, and adding them just slows you down.

To see the same skeleton with no pruning at all, here's generating every subset of an array. Every node is already a valid answer, so there's nothing to check:

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])          # every node is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])        # choose
            backtrack(i + 1, path)      # explore
            path.pop()                  # undo

    backtrack(0, [])
    return result

Same three pieces. The is_valid check from N-Queens is simply absent, because in unconditional enumeration there's no constraint to prune on. Drop the path.pop() line, though, and you reproduce the most common backtracking bug: every subset after the first comes back polluted with elements left over from an earlier branch. The undo is what keeps one mutable list honest across the whole tree.

One more thing the shapes tell you is the cost. The worst case for backtracking is exponential, because the tree can have exponentially many nodes. Pruning doesn't change that worst case, it changes how much of it you actually visit. On loose constraints you walk most of the tree anyway. On tight ones like N-Queens you skip the overwhelming majority, which is why the same algorithm feels fast on one problem and hopeless on another.

When backtracking is the wrong call

Reaching for backtracking on the wrong problem is a common interview misstep. Three signals tell you it fits:

The problem wants all valid configurations, or one valid configuration. "Generate all", "find every", "place the" are tells. If it only wants a count, DP is usually faster.
Each decision constrains future decisions. Placing an element at A removes options at B. That's a constrained search tree.
There's no greedy shortcut and no overlapping subproblem to cache. If locally optimal choices give the global optimum, that's greedy. If the same subproblem repeats, that's DP.

When the input is large and you can't prune hard, even correct backtracking times out. That's the boundary where the interviewer is usually steering you toward dynamic programming.

A quick gut check before you commit: estimate the branching factor and the depth. If the tree is roughly b choices deep d levels and your constraints don't kill many branches, you're looking at something near b^d work. When that number is astronomical and the problem only wants a count or a single optimal value, that's the cue to stop and ask whether the states overlap.

Where backtracking turns into DP

The two are closer than they look. When a backtracking solution explores the same partial state through different decision paths, you're recomputing work. Cache those states and top down DP falls out of the same recursion you already wrote.

That progression, from raw search to memoised recursion to a table, is one of the most reusable moves in interview prep. It also explains why solid recursion has to come first. Backtracking is recursion with a choose, check, undo wrapper, so if the recursive call still feels shaky, the wrapper won't save you. If you want to drill the pattern shapes directly, the backtracking pattern lessons work through each of the three with their own trigger checklist.

The gap that trips most people up isn't writing the recursion. It's trusting the moment a branch should be abandoned, and that's the part I keep coming back to in my own work.

I wrote a longer version on my blog that walks through the other two shapes with full code, plus the common bugs that make backtracking silently return wrong answers.

Which backtracking problem finally made the choose, check, undo loop click for you?

AVL Trees Explained: How Rotations Keep BST Operations O(log n)

Prakhar Srivastava — Wed, 20 May 2026 19:50:04 +0000

You learn binary search trees and walk away believing every operation is O(log n). It isn't. That guarantee only holds when the tree stays balanced, and a plain BST has no mechanism to enforce that. Insert [1, 2, 3, 4, 5] into an empty BST and you've built a linked list with extra steps.

TL;DR: An AVL tree adds one rule to a BST. No node's left and right subtrees can differ in height by more than 1. When an insertion breaks the rule, the tree fixes itself through rotations. Every operation stays O(log n). The four rotation cases aren't four separate things to memorise. They're two atomic moves combined twice.

The balance rule everything else hangs on

An AVL tree is a self balancing BST where, for every node, the heights of its left and right subtrees differ by at most 1. That's the whole rule. Every operation that preserves the rule preserves O(log n).

You track the rule with the balance factor:

balance_factor(node) = height(left_subtree) - height(right_subtree)

A node is balanced when its balance factor is -1, 0, or +1. Zero means both subtrees have the same height. +1 means the left is one level taller. -1 means the right is. When an insertion or deletion pushes any node's balance factor to -2 or +2, the tree is unbalanced and needs fixing.

The fix is always a rotation, and it's always local. You don't rebuild the tree. You rearrange 2 or 3 pointers near the imbalance and the invariant snaps back into place.

This single rule is strict enough to guarantee logarithmic height. An AVL tree with n nodes has height at most about 1.44 log(n). Slightly taller than a perfectly balanced tree, but the difference is a constant factor. Every operation traverses from root to leaf, so when height stays logarithmic, so does runtime.

Why the rule matters more than it looks

A plain BST gives you none of this. Insert the values [1, 2, 3, 4, 5] into an empty BST. Each value is larger than the last, so every insertion goes right. The resulting tree is a straight line, structurally identical to a linked list. Searching for 5 walks all five nodes. O(n), not O(log n).

Sorted input isn't unusual either. Database indices built from timestamped logs, primary keys assigned by an auto-increment column, sensor readings ordered by time. All of these produce sorted insertion sequences. A plain BST degenerates into a linked list on every one of them.

Performance depends entirely on height. Balanced, you get O(log n). Degenerate, you get O(n). Lose control of the height, lose control of the performance. That's the whole reason self balancing exists.

The four rotation cases, and why they're really just two

Every AVL imbalance falls into one of four cases. Each one is resolved by a specific rotation that preserves the BST ordering (left < parent < right) while restoring the height balance.

There are only two atomic moves: a left rotation and a right rotation. The four cases are these two moves applied once or twice.

LL case (left child of a left-heavy node): single right rotation on the unbalanced node
RR case (right child of a right-heavy node): single left rotation on the unbalanced node
LR case (right child of a left-heavy node): left rotate the left child first to straighten the kink, then right rotate the unbalanced node
RL case (left child of a right-heavy node): right rotate the right child first, then left rotate the unbalanced node

The single rotations handle the "outside" imbalances. The double rotations handle the "inside" imbalances where a single rotation would just move the heavy side from one position to another without fixing it. The trick is recognising which side of the parent is heavy AND which side of that child is heavy. Those two answers pick the case.

def right_rotate(z):
    y = z.left
    T3 = y.right
    y.right = z
    z.left = T3
    z.height = 1 + max(height(z.left), height(z.right))
    y.height = 1 + max(height(y.left), height(y.right))
    return y

Notice what the rotation actually does. It moves 3 pointers and updates 2 heights. That's it. Constant time. The O(log n) part of an insertion comes from walking down the tree to find the insertion point and walking back up to check balance factors. The rotation itself is free by comparison.

Tracing an insertion sequence

Walk through inserting [3, 2, 1, 4, 5] into an empty AVL tree. I find that watching two different rotations fire in the same sequence is what makes the four-case table click.

Inserting 3 creates a single-node tree with balance factor 0.

Inserting 2 sends it left of 3. Node 3's balance factor is +1 (left subtree height 1, right subtree height 0). Still within the rule.

Inserting 1 triggers the first rotation. 1 goes left of node 2. Walking back up, node 2's balance factor is +1 and node 3's is +2. That's an LL case (node 3 is left-heavy, its left child 2 is also left-heavy). A right rotation on node 3 puts node 2 at the root, node 1 on the left, and node 3 on the right. All balance factors drop to 0.

Inserting 4 goes right from node 2 to node 3, then right again to become node 3's right child. Walking back, node 3's balance factor is -1, node 2's is 0. Within the rule.

Inserting 5 breaks balance again. It lands as node 4's right child. Walking back up, node 4's balance factor is -1, but node 3's hits -2. That's an RR case. A left rotation on node 3 moves node 4 into node 3's position, with node 3 as 4's left child and node 5 as 4's right child. All balance factors back to 0.

Final tree: node 2 at the root, node 1 on the left, node 4 on the right, with 3 and 5 as 4's children. Height is 2.

A plain BST with the same insertion order [3, 2, 1, 4, 5] wouldn't degenerate this badly. But try [1, 2, 3, 4, 5] and the plain BST becomes a linked list of height 4. The AVL version still has height 2.

The full insertion algorithm bundles the BST insert with the balance check on the way back up:

def insert(node, key):
    if not node:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    node.height = 1 + max(height(node.left), height(node.right))
    bf = balance_factor(node)

    if bf > 1 and key < node.left.key:
        return right_rotate(node)
    if bf < -1 and key > node.right.key:
        return left_rotate(node)
    if bf > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)
    if bf < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

After every insertion you only check balance factors along the path from the inserted node back to the root. At most one rotation (single or double) is needed.

Why deletion is harder than insertion

This is the part most beginner tutorials gloss over and the part interviewers like to probe.

Insertion can break balance at one node along the ancestor path. You rotate once and you're done. Deletion isn't that clean.

When you remove a node, the height reduction can propagate upward. Fixing the first imbalanced ancestor might shorten that subtree, which then unbalances the next ancestor up. In the worst case you'll rotate at every level from the deleted node's position back to the root. That's O(log n) rotations instead of the single rotation insertion needs.

The rotation selection logic stays the same. You still compute balance_factor(node) and check whether the imbalance is LL, RR, LR, or RL. The difference is that you can't stop after the first fix. You have to keep walking up.

There's also a subtlety with the node you're actually removing. If the target has two children, you replace it with its in-order successor (smallest in the right subtree) or its in-order predecessor (largest in the left subtree), then delete that node instead. The replacement is identical to plain BST deletion. The AVL-specific work starts afterward, during the upward balance check.

I'd argue most interview questions won't ask you to implement AVL deletion from scratch. But understanding why deletion is more expensive than insertion is what separates "I've memorised the four cases" from "I've actually thought about the invariant." If an interviewer asks about the tradeoff of stricter balance, deletion cost is the concrete answer.

When to reach for AVL vs Red-Black

In interviews, AVL trees show up two ways: explaining self balancing BSTs conceptually, and implementing balanced insertion from scratch. Red-Black trees show up as a "why don't standard libraries use AVL" question.

Plain BST. Fine when input is random or the problem doesn't require worst-case guarantees. Tree problems on LeetCode typically assume balanced input and don't ask you to maintain balance yourself.

Red-Black tree. Relaxes the balance constraint to height up to 2 log(n) in exchange for cheaper insertion and deletion. At most 2 rotations per operation, vs potentially O(log n) for AVL deletion. Java's TreeMap, C++'s std::map, and Linux's CFS process scheduler all use Red-Black trees. So does the Linux kernel's anonymous VMA tree. Most standard libraries do.

AVL tree. Enforces stricter balance. Maximum height about 1.44 log(n) versus about 2 log(n) for Red-Black. Lookups are faster because the tree is shorter. The tradeoff is that insertions and deletions are slower because AVL trees may need more rotations to maintain the stricter rule.

Why are AVL trees less common in production despite being older and simpler? Looser balance makes insertion-heavy workloads faster, and most real systems insert and delete more than they search-only.

For interviews though, AVL trees are the better answer. The rotation logic is more intuitive than Red-Black's five-case colour rules. If an interviewer asks you to implement a self balancing BST from scratch, AVL is the cleaner choice under time pressure. I keep seeing candidates wedge themselves into Red-Black trees and run out of time at the recolouring step. AVL trees let you spend that same time tracing the four cases instead.

Honest credit where it's due: Red-Black trees aren't "worse." They're optimised for a different workload. The standard library authors knew exactly what they were trading. It's the same engineering call you'd make if you were building a key-value store that inserts billions of times a day. AVL is the wrong choice there. It's only the right choice for read-heavy workloads, or for an interview where the simpler invariant lets you finish before the timer.

The three mistakes that cost candidates in interviews

These are the patterns I keep seeing on AVL questions, in roughly the order they show up.

Stale heights after rotation. You rotate nodes y and z but forget to recalculate their height fields. The next balance factor check uses stale data and every decision downstream is wrong from that point on.
Top-down balance checking. You insert at a leaf and trace upward to find the first unbalanced ancestor. Starting from the root downward misses the actual imbalance point or applies a rotation at the wrong node.
Misidentified LR / RL cases. Under pressure it's tempting to see a left-heavy node and immediately right rotate. If the left child is right-heavy, a single right rotation makes things worse. Sketching the three nodes on paper before choosing the rotation takes five seconds and avoids a cascading error that's painful to debug mid-interview.

Codeintuition's Binary Search Tree course walks the balance invariant from first principles. If the four-case table still feels like four separate things to memorise, the BST course traces balance factor computation across multiple tree shapes before any rotation code appears.

I wrote a longer version on my blog that walks deletion with the upward rebalance loop and includes the AVL vs Red-Black tradeoff matrix.

Which AVL rotation case took the longest to internalise for you, and what was the problem or sketch that finally made it click?

I Mapped 450+ FAANG Problems: Amazon, Google, and Meta Don't Test the Same DSA Patterns

Prakhar Srivastava — Tue, 12 May 2026 15:23:46 +0000

The most common DSA prep mistake I see at the FAANG band isn't undertraining or overtraining. It's training as if Amazon, Google, and Meta all sample from the same pattern bag. They don't. After mapping company tags across 450+ handpicked interview problems, the gap between Amazon's pattern footprint and Google's is larger than most candidates expect, and materially changes how prep time should be allocated.

TL;DR: Amazon spans 11+ distinct DSA pattern families, the broadest of any major company. Google has narrower coverage but a distinctive emphasis on predicate search (binary search on the answer space, not on a sorted array). Seven patterns appear at six or more companies and form the universal baseline that every FAANG candidate has to own before specialising.

The seven patterns every FAANG round assumes you can run

Before company specific differences matter, there's a universal baseline. Seven patterns appear at six or more major companies in the data set. Skipping any of them, regardless of target company, is a structural error in the prep plan.

Company-specific prep matters. But only after the universal baseline is genuinely automatic.

The most heavily tagged is LRU Cache, at 19 companies. That's every FAANG member, plus DoorDash, Oracle, Zoom, PayPal, Twilio, TikTok, eBay, Yandex, LinkedIn, Zillow, Intuit, and Cloudera. The reason it spreads that far is structural: a single problem tests hash table mechanics, doubly linked list manipulation, and design composition at once. No alternative problem covers the same combination at the same difficulty.

The remaining six universal patterns:

Counting (hash table): 9 companies. Frequency counts, anagram grouping, character buckets. Most broadly tested hash table pattern.
Backtracking: 8 companies. Generate parentheses through N-Queens. Tests recursive state and pruning.
Prefix Sum: 8 companies. Range queries, subarray sums, equilibrium problems. Almost always undertaught relative to its testing rate.
Binary Search: 7 companies. The classic sorted array variant. Includes rotated array and boundary problems.
Fixed Sliding Window: 7 companies. Window of fixed size with frequency tracking inside it.
Variable Sliding Window: 6 companies. Different triggers from fixed: a contracting mechanism that has to fire on a condition, not on a counter.

Prefix Sum is the one that gets shortchanged most. Eight companies tag it. Most prep plans treat it as a footnote because it doesn't have a flagship problem the way LRU Cache or Two Sum do. That's a mismatch worth correcting: it gives disproportionate company coverage relative to the time required to learn it well.

The highest ROI interview patterns are often the ones without famous flagship problems.

Predicate search: the pattern Google tests that nobody calls by name

Google shares the universals, but the pattern that distinguishes Google interviews from the rest is predicate search. This is binary search applied not to a sorted array but to the answer space itself. You define a range of possible answers, then binary search that range by checking feasibility at each midpoint.

The classic shape is the minimum ship capacity problem. You're given package weights and D days. Find the smallest ship capacity that lets you ship everything in D days.

Instead of trying every capacity from 1 upward, you frame the search range:

Low: the heaviest single package (you have to lift it on day one)
High: the sum of all weights (one giant day)

Then binary search inside that range:

def min_ship_capacity(weights, days):
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        day_count, current_load = 1, 0
        for w in weights:
            if current_load + w > mid:
                day_count += 1
                current_load = 0
            current_load += w
        if day_count <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo

The mechanical shift from classic binary search is small, but the mental shift is large. In classic binary search, the search space is given to you (a sorted array). In predicate search, you construct the search space from the constraints, then run binary search on your own abstraction. You're searching for the minimum value that satisfies a feasibility predicate, not a value already sitting somewhere in the input.

LeetCode tags these problems "Binary Search" alongside sorted array problems. The tag isn't wrong, but it hides the model shift. If your only model for binary search is "find a value in a sorted array," predicate search will freeze you because the starting assumption doesn't match. Google asks predicate search variants more than any other company in the data set: punctual arrival speed, trip completion frenzy, calculate square root, capacity to ship within D days, all the same shape.

Most candidates know binary search on arrays. Far fewer recognise when the answer itself is the search space.

A useful test before practising binary search problems: can you state, in one sentence, what the search range is and what the feasibility check is? If yes, you're doing predicate search. If you reach for mid = (left + right) // 2 without that explicit framing, you're guessing.

Why Amazon's pattern coverage is wider than anyone else's

Amazon's problem set covers Counting, Fixed and Variable Sliding Window, Prefix Sum, LRU Cache, Randomised Set, Binary Search, 2D Binary Search, Staircase Search, Maximum Predicate Search, Queue Design, and Backtracking. That's 11+ pattern families against Google's 7-8 and Meta's 6-7.

The practical effect on prep is concrete. A Google candidate who goes deep on predicate search, counting, and graphs covers a meaningful slice of what they'll actually see. An Amazon candidate who goes equally deep on three families has blind spots across the other eight. The "study three patterns deeply and hope you land in your zone" strategy has a lower hit rate at Amazon than anywhere else.

The Bar Raiser round amplifies the breadth requirement. The Bar Raiser is an interviewer pulled from outside the hiring team, with veto power, and they're not bound to the team's domain. They can sample any pattern family Amazon tests. If the round happens to land on a category you skipped, the heuristic of "the team usually asks X" doesn't catch you.

Going deep still matters. But at Amazon the breadth axis carries more weight than at the narrower companies, and the prep allocation should reflect that.

Meta, Microsoft, Apple: where the rest of the picture sits

Meta concentrates on Sliding Window (both Fixed and Variable), Prefix Sum, Counting, and design problems (LRU Cache, Randomised Set). Maximum Predicate Search shows up too. Compared to Google, Meta places less weight on searching variants and more on hash table depth and design implementation. If Amazon tests breadth and Google tests reasoning depth, Meta wants hash table fluency in a tighter band.

Microsoft is distinct for 2D Binary Search and Staircase Search. These are multi dimensional search problems where the input is a sorted matrix and the search has to respect both axes. Most prep plans skip them entirely because they don't appear at Google or Meta. If Microsoft is your target, weight 2D search higher and variable sliding window lower.

Apple tilts toward fundamentals tested deeply. Five Counting problems carry Apple tags, alongside Binary Search, Prefix Sum, and Backtracking. Apple's data signals a preference for candidates with strong basics over candidates with broad pattern coverage. The advanced design problems (Randomised Set, Queue Design) that Amazon tests don't appear in Apple's tags.

What a company doesn't test matters as much as what it does. Every hour spent on patterns your target company doesn't emphasise is an hour that could've gone to one they do. Google shows minimal tags for Queue Design and 2D Binary Search. Meta shows lower coverage of searching variants. Microsoft shows fewer tags for Variable Sliding Window. Apple barely tests advanced design at all. If you're prep-allocated against the wrong company's profile, you're optimising the wrong axis.

Allocating prep time once you know your target

Three rules fall out of the data, in this order:

Cover the universals first, regardless of target. LRU Cache, Counting, Backtracking, Prefix Sum, Binary Search, Fixed Sliding Window, Variable Sliding Window. Skip none of them.
Specialise second. Predicate search for Google. Design breadth and Bar Raiser follow up depth for Amazon. Design depth and sliding window fluency for Meta. 2D and staircase search for Microsoft. Counting and fundamentals depth for Apple.
Cut what doesn't match. Targeting Google and not Amazon? Queue Design can wait. Targeting Meta and not Microsoft? Staircase Search can wait. Prep time is finite.

Two patterns are worth flagging again. Prefix Sum is undertaught relative to its 8-company tag count. Almost no popular prep plan gives it the time it deserves. And LRU Cache is the one problem you genuinely shouldn't walk into any FAANG round without being able to write cold, including the doubly linked list helpers. Nineteen company tags, no exceptions.

Most prep platforms organise problems by data structure (Hash Table, Tree, Graph), which buries the company-level signal entirely. The more useful filter is patterns by company tags. Once you can answer "which 6-8 patterns has my target company asked across 450+ problems," the allocation question gets concrete and fast.

I wrote a longer version with the per company breakdown and the FAQ on my own blog covering the patterns each company genuinely deemphasises (Google's quiet skip on Queue Design, Apple's near absence of advanced design).

If you've interviewed at more than one of these five companies, which pattern came up that you weren't expecting based on the company's reputation?

The Amazon Bar Raiser Isn't Testing Your Solution. It's Testing the Follow Up.

Prakhar Srivastava — Mon, 11 May 2026 14:32:57 +0000

You're 15 minutes into an Amazon coding round. You've identified the pattern, your solution handles the examples, you're about to submit. Then the interviewer changes a constraint. Sorted input is now unsorted. The complexity ceiling drops from O(n log n) to O(n). Your original solution collapses, and the rest of the round is now about whether you can reconstruct the approach from the invariant rather than from memory.

That moment, the constraint shift after the working solution, is where the Bar Raiser's evaluation lives. Most prep treats it as a bonus question. The Bar Raiser treats it as the round.

TL;DR: Amazon's Bar Raiser is an independent interviewer with veto power who tests the same problems as a regular round but probes the follow up much harder. Two things make Amazon prep different from Google or Meta prep: the pattern coverage is broader (eleven plus pattern families vs. six or seven), and the round's evaluation centres on whether you can adapt your solution after a constraint changes, not on whether you can produce the optimal solution first.

What the Bar Raiser is, in one paragraph

Amazon's Bar Raiser is an interviewer pulled from outside the hiring team. Their job is to evaluate the candidate against Amazon's company wide hiring bar, independent of how badly the team wants to fill the seat. They can veto a hire that everyone else approved. They can also push a borderline candidate over the line if they see genuine depth.

In practice, you don't know which of your interviewers is the Bar Raiser. Amazon keeps that ambiguous through the loop. What you do know is that at least one round will be a Bar Raiser round, and that round usually includes a coding problem.

The problem itself looks the same as any other Amazon technical screen. The difference is what happens after you produce a working answer. A standard interviewer often moves on once you've solved it. A Bar Raiser keeps going. They'll change a constraint, ask you to optimise, ask why your solution is correct (not just whether it works), or walk you through the failure case you didn't test.

The initial solution gets you to the conversation. The follow up is the conversation.

The solution gets you into the round. The adaptation decides the round.

Why Amazon's pattern coverage is wider

Every FAANG company has favourite pattern categories. Google leans heavily on predicate search (binary search on the answer space). Meta concentrates on sliding window and design. Amazon doesn't have a tight central focus the way those two do. Its problem set spans counting, fixed and variable sliding window, prefix sum, LRU style design, randomised set design, binary search and its 2D / staircase variants, queue design, and backtracking.

That's eleven plus pattern families versus roughly seven or eight for Google and six or seven for Meta.

What this means for prep is concrete: the strategy of going deep on two or three pattern families and hoping the round lands in your zone has a lower hit rate at Amazon. A Google candidate who deeply understands predicate search, counting, and graphs covers a meaningful fraction of what they'll see. An Amazon candidate who goes equally deep on three families has blind spots across the other eight.

The Bar Raiser amplifies this. Because they're not bound to the hiring team's domain, they can pull a problem from any of those families. If the round happens to land on a category you skipped, the safety net of "the team usually asks X" doesn't catch you.

The broader your pattern coverage, the smaller the chance any single Bar Raiser pick puts you in unfamiliar territory. Going deep matters too, but at Amazon the breadth axis carries more weight than at the narrower companies.

What the follow up is testing

The interviewer isn't asking the follow up to be cruel. They're testing whether you understood the mechanism of your solution or just the solution itself. If your initial answer was a recalled template for the problem, the constraint change exposes that. If your initial answer was constructed from an invariant, the constraint change is something you can adapt to.

Strong candidates optimise from understanding. Weak candidates optimise from memory.

A worked example makes this concrete. LRU Cache is one of Amazon's most reliably tested problems. The standard solution composes a hash map (O(1) key lookup) with a doubly linked list (O(1) insert and removal at any node when you have the node reference). The hash map maps key to list node. Operations look like:

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}                     # key -> ListNode
        self.head = ListNode()            # most recently used end
        self.tail = ListNode()            # least recently used end
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = ListNode(key, value)
        self._add_to_front(node)
        self.map[key] = node
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

That's the answer the Bar Raiser expects you to land. Now the follow up: each entry has a TTL. Reads on an expired entry must return -1. The cache must still operate at expected O(1) per call.

The candidate who memorised LRU starts redesigning from zero. The candidate who built it from the invariant asks one question first: which invariant did the doubly linked list maintain, and does that invariant still hold under TTL?

The list maintained an ordering invariant: nodes near the head were used more recently than nodes near the tail. Eviction removed the tail because tail was the least recently used. With TTL, the eviction criterion changes from "least recently used" to "expired or least recently used." The list ordering by recency is still useful for the second clause, but the first clause needs a different signal. Two choices land:

Lazy expiry: on get, if the node's expiry timestamp has passed, treat it as a miss, remove the node, return -1. On put, when the cache is full, evict the tail as before. Simple, keeps the data structure unchanged. Worst case has expired entries lingering until they're touched.
Eager expiry: maintain a second ordered structure keyed by expiry time (a min heap or a second linked list ordered by expiry). On every get or put, sweep expired entries off the front of the expiry structure. More memory, tighter behaviour on memory pressure.

The Bar Raiser doesn't necessarily care which one you pick. They care whether you can articulate which invariant you're preserving and which one you're modifying. The candidate who answers "the recency ordering still holds, I'm adding an eviction predicate that checks expiry first" has demonstrated something about reasoning that solving twenty more problems wouldn't have.

The three signals the round is graded on

Three threads run through what separates a "hire" rating from a "no hire" in a Bar Raiser coding round, and they correspond to the three places the round lives.

Clean reasoning under loose constraints. The problem statement is often deliberately under specified. Inputs might or might not be sorted. Sizes might be zero. Negative numbers might appear. The candidate who immediately asks the clarifying questions, defines assumptions on a whiteboard area, and only then starts coding signals the kind of structured thinking Amazon values. Jumping into code without defining the problem space reads as someone operating from pattern memory rather than from understanding.

Adaptation across the follow up. This is the LRU + TTL example above. The follow up isn't a new problem. It's the same problem with a constraint flipped. The candidate who can isolate which part of the previous solution depended on the changed constraint passes. The candidate who scraps and restarts shows that the previous solution was lookup, not construction.

The follow-up is usually testing whether your first solution was constructed or recalled.

Articulation of why. Bar Raisers listen for the explanation that goes past "I'm using a hash map here." They want to hear what invariant the hash map maintains, what would break with an array, what tradeoff you accepted. A candidate who can talk through the load bearing reasoning is a candidate who would raise the team's average performance, which is the literal evaluation Amazon writes down.

The four mistakes the round punishes

These are not coding mistakes. They're prep mistakes that compound under the format.

Solving silently. You finish in fifteen minutes and present the answer. The Bar Raiser has nothing to evaluate beyond the output. Your reasoning made no observable trace. Narrate the structural choices as you go: why a hash map and not a sorted array, why an O(n) first pass instead of trying for O(log n), what edge case you'll come back to. The round is graded on observable reasoning, not just output.
Chasing the optimal solution before the working one. Some candidates spend twenty minutes thinking before writing a line, hunting for the optimal solution out of the gate. Then the follow up arrives at minute thirty five and there's no time for it. Get a correct O(n^2) or O(n log n) working first, confirm edge cases, then improve when the Bar Raiser asks. The follow up is part of the round's grade. Running out of time on it is a soft fail you didn't have to take.
Treating the follow up as a new problem. When the constraint changes, the instinct is to discard the previous solution and start fresh. That's almost always wrong. The follow up is testing whether you understand the structural relationship between the constraint and your approach. Ask which part of your solution depended on the constraint that just changed, then modify only that part. If the original used binary search because the input was sorted and the follow up removes the sort guarantee, you change the search mechanism, not the algorithm.
Skipping edge cases until prompted. Empty input, single element, duplicate values, integer overflow boundaries. Walking through two of these unprompted before the interviewer asks signals thoroughness and pre empts the follow up that targets the case you skipped. Reactive edge case handling reads as a candidate who optimises for the example and not for the input space.

What this changes about how to prep

The standard FAANG prep approach is to go deep on two or three pattern families and hope the interview lands in their zone. That works at companies with narrower coverage. For Amazon's breadth it leaves too many uncovered surfaces, and for the Bar Raiser in particular it leaves you with no recovery path if the chosen pattern isn't one you went deep on.

Two adjustments help.

The first is interleaving over blocking. Block practice is a week on sliding window, a week on dynamic programming, a week on graphs. Interleaved practice rotates between pattern families inside the same study session. Cognitive science research on interleaved practice consistently shows that mixing problem types during study improves your ability to identify which pattern applies to a new problem. Mixed practice is harder while you're doing it (you can't lean on the priming of "this week is sliding window, every problem is sliding window") and that's the point. The harder identification work during practice is the same identification work the Bar Raiser's follow up will require.

The second is practising the follow up explicitly. After every problem you solve, ask: what's the constraint change that would invalidate this solution most? Implement the modified version. The constraint change is the rep that builds the adaptation skill, and adaptation is what the Bar Raiser scores. If LRU Cache is the practice problem, "add TTL" is the rep. If sliding window with at most K distinct characters is the problem, "K varies based on the substring contents" is the rep.

You can do both of these without any platform: a pattern list, a notebook of constraint flips per problem, and a habit of running the second pass before moving on. The reason most prep skips it is that there's no immediate signal it's working. The signal arrives in the round when the Bar Raiser shifts a constraint and you reach for the invariant instead of the template.

If you're preparing for Amazon and your practice still stops after finding the optimal solution, you're missing the part the Bar Raiser actually evaluates.

I wrote a longer breakdown covering:

Amazon's highest frequency pattern families
how the Bar Raiser evaluates coding rounds
and the follow up drills that build adaptation under constraint shifts

Full breakdown here

The day of the loop

A few logistical things candidates often get wrong, worth noting because they're outside your technical preparation but inside the Bar Raiser's evaluation surface.

The onsite loop is typically four or five rounds across a single day or consecutive virtual sessions. One is system design for senior candidates. Two or three are coding rounds. One is behavioural, focused on the Leadership Principles. The Bar Raiser participates in at least one of these, and you won't know which until after the process ends.

Coding rounds are about forty five minutes. Five to ten minutes go to introductions and the problem statement. Twenty five to thirty minutes go to the initial solution. The last ten to fifteen are where the follow up happens. If your first solution takes thirty five minutes because you were reaching for the optimal answer from the start, you've already lost the follow up window.

Each round is evaluated independently. A weak round one doesn't doom you if rounds two and three are strong, and the Bar Raiser considers performance across the loop. Don't mentally rehearse what just happened in the breaks. Reset and walk into the next round.

The debrief happens without you. All interviewers, including the Bar Raiser, meet afterward. If the hiring manager wants to extend an offer and the Bar Raiser objects, the Bar Raiser's veto stands.

Three months from now

The Bar Raiser round isn't a fundamentally different format. It's the same problem solving test with a higher evaluation standard and broader pattern coverage. Two things move the needle for it: pattern breadth across families that gets exercised by interleaved practice, and the ability to adapt your solution when the constraint shifts in the follow up.

I wrote a longer version with the full pattern breakdown across Amazon's tested families on my own blog, including how the loop's other rounds factor into the Bar Raiser's overall judgement.

What's a follow up question from a real interview that changed how you think about the problem itself, not just the solution?

Arrays vs Linked Lists: Why Big-O Alone Doesn't Explain the Tradeoff

Prakhar Srivastava — Sun, 10 May 2026 10:58:45 +0000

The complexity table for arrays and linked lists is the most memorised, least understood reference in interview prep. Arrays give O(1) access. Linked lists give O(1) insertion. That's the answer on every flashcard. The table doesn't lie. It's incomplete. The missing piece, once you have it, makes every entry in that table feel obvious.

TL;DR:

Arrays and linked lists differ for one reason: contiguous memory vs scattered memory.

Every entry in the complexity table follows from that single fact.

Two O(n) operations aren't equal in practice. A million element array scan can often run an order of magnitude faster than the equivalent linked list traversal because of cache locality.

Linked lists win when your algorithm already holds a pointer to the mutation point. They lose when you have to traverse to find it first.

The right question on any problem isn't "which has better Big-O?" It's "which operation does this algorithm perform most?"

What the table tells you, and where it stops

The standard table has six or seven rows: access by index, search, insert at start, insert at end, insert at known position, delete at known position, memory overhead. Each row has two cells. Most engineers memorise the cells and stop there.

The table is correct. Arrays really do give you O(1) index access. Linked lists really do give you O(1) insertion at a known node. The cells aren't wrong. They describe outcomes without explaining why those outcomes happen, which means you can't generalise to a problem you haven't seen.

Memorising complexity tables teaches conclusions. Understanding memory layout teaches reasoning.

If your interviewer asks "which would you use here?" on an unfamiliar problem, a memorised table doesn't help. You need the mechanism underneath.

Memory layout is the root cause

Both data structures store the same thing: a sequence of values. They differ in exactly one way: where those values live.

An array is a single block of contiguous memory. Element 0 sits at the base address. Element 1 sits at base + element_size. Element i sits at base + (i * element_size). The address of any element is a single arithmetic expression. That arithmetic is what makes index access O(1). It's also what makes insertion in the middle O(n): to make room at index 2 of a 5 element array, every element from index 2 onward has to shift right.

A linked list is a chain of nodes that can live anywhere in memory. Node 0 might be at address 1000. Node 1 at address 7500. Node 2 at address 3200. The only way to find node 2 is to start at node 0 and follow the next pointers. That traversal is what makes index access O(n). It's also why insertion at a known node is O(1): you allocate a new node, point it at the next node, and update the previous node's pointer. Two pointer assignments. No shifting.

Every entry in the complexity table is a consequence of these two facts. The math gives you the cells. The layout tells you why.

When the same Big-O isn't the same: cache locality

This is what the table can't show. Both arrays and linked lists are technically O(n) for a full traversal. In practice, an array traversal of a million integers can often run an order of magnitude faster than the equivalent linked list traversal. Same Big-O. Very different wall clock time.

The reason is the CPU cache.

When the CPU reads element 0 from an array, it doesn't fetch just that one integer. It loads an entire cache line, typically 64 bytes, into the L1 cache. For a 4 byte integer array, that single fetch pulls in the next 15 elements alongside arr[0]. Iterating through them costs nanoseconds per access because they're already on chip. The CPU prefetcher notices the access pattern and starts loading the next cache line before you ask for it.

Linked list nodes are scattered across the heap. Each node.next dereference points at an unrelated address. Each pointer chase is a potential cache miss, and a cache miss is roughly a 100 nanosecond round trip to main memory. Multiply that by a million nodes and the gap is enormous.

# Both loops are O(n). The constants differ by ~10x in practice.

# Array: cache friendly contiguous reads
total = 0
for x in arr:
    # next 15 ints already in L1 after the first read
    total += x          

# Linked list: cache hostile pointer chases
total = 0
node = head
while node:
    total += node.value

    # node.next probably triggers a cache miss
    node = node.next

I keep noticing this is what surprises engineers most when they first see it. They've quoted O(n) for traversal in both cases for years. The constant factor never came up because Big-O hides it.

This is the reason ArrayList in Java and Python's built in list are array backed. You're paying the occasional O(n) resize cost in exchange for cache friendly iteration on every operation between resizes. That trade is almost always worth it on real workloads, even ones that involve frequent appends.

If you mention this in an interview, you've shown that you understand the hardware level, not just the math. Two candidates can both quote O(n) for traversal. Only one knows that one of those O(n)s is dramatically slower in practice.

Big-O tells you how growth behaves. Hardware tells you what actually feels fast.

When linked lists actually win

Honest credit where it's due: linked lists are the right structure in a narrow set of cases. Don't read the cache argument as "always pick arrays."

Mutation at a known position: if your algorithm already holds a pointer to the node where you're inserting or deleting, linked lists are O(1) and arrays are O(n). The keyword is "already holds." The standard LeetCode example is LRU Cache, where a hash map gives you O(1) access to the relevant node and a doubly linked list gives you O(1) reordering on every access. Neither structure alone solves the problem.
Pointer only manipulation: reversing a segment, splitting a list at a node, merging two sorted sequences. None of these require moving data, they're pure pointer reassignment. The singly linked list course on my own site covers seven distinct patterns built on this property.
No reallocation cost: dynamic arrays double their capacity when full, which involves copying every element. Linked lists grow one node at a time. For genuinely unbounded streaming workloads with random insertion, the linked list's amortised cost can come out ahead.

The most frequent mistake I watch beginners make is reaching for a linked list the moment they see "insert" or "delete" in a problem, without checking whether they already hold a pointer to the position. Without that pointer, you traverse first (O(n)) and then insert (O(1)). The traversal eats the advantage. Total cost is O(n), same as the array shift, with worse constants because of cache misses.

An O(1) operation that requires O(n) setup is still O(n).

How to choose without memorising the table

Once memory layout is your mental model, the choice becomes a small set of questions you can ask on any problem:

Does the algorithm need random access by index, or binary search? Pick an array. Linked lists can't do O(log n) binary search because finding the middle requires traversal.
Does the algorithm scan the whole structure repeatedly, where speed matters? Pick an array. Cache locality is doing real work in your favour.
Does the algorithm hold direct pointers to nodes it mutates (head, tail, hash map mapped)? A linked list might genuinely win.
Does the algorithm reverse, split, or merge segments by relinking? Linked lists are the natural fit.
Does the algorithm need both random access and frequent reordering at known positions? You probably want both: a hash map of keys to linked list nodes. LRU Cache is the canonical example.

Almost every interview problem involving a sequence of mutations is either an array problem (because access dominates) or a hash map plus linked list problem (because both operations matter). Pure linked list only problems are surprisingly rare in interview banks. They mostly show up when the problem itself is testing whether you can do pointer manipulation cleanly.

An aside on the table itself: the complexity tables you see everywhere aren't useless, even if they're incomplete. They're a fast lookup once you know what's underneath. The point isn't to throw the table out. It's to stop treating it as the answer when it's the symptom.

If Big-O tables still feel like facts you memorise rather than intuitions you can derive, I wrote a longer breakdown covering:

stacks and queues from the same memory model
adjacency lists vs matrices
and why some O(n) operations feel dramatically faster in practice

Full breakdown here

What's a problem where you reached for a linked list and only realised mid implementation that an array would have been cleaner?

Am I Ready for FAANG? A Better Test Than Solving More LeetCode

Prakhar Srivastava — Sat, 09 May 2026 12:40:03 +0000

You've solved 200 problems. Mediums you've already seen take fifteen minutes. The next one you haven't seen freezes you cold inside of five. And every time you ask yourself if you're ready for a FAANG loop, the honest answer is "I don't know."

The "I don't know" isn't a feeling problem. It's that you've been asking a feelings question about a performance outcome.

TL;DR

Self assessed readiness is unreliable because confidence swings with every session.

Solving a familiar problem and constructing a solution to a novel one are different skills.

The fix is a measurable test: an unseen medium in a pattern family you've studied, under timed conditions, with a hard cap on execution attempts.

Pass three of those across three different families and you likely have the level of transfer real interviews actually reward. Fail one and you know exactly where to work.

The signal isn't the count. It's whether the recognition holds when the problem name is hidden.

Why "do I feel ready" is the wrong question

Solving a problem you've seen before and reasoning your way through one you haven't are different skills. Practice on the same patterns repeatedly builds recognition. Recognition only fires on shapes you've encountered. The interview gives you a shape you haven't, and asks you to construct the approach from the constraints alone.

That's the gap between near transfer and far transfer. Near transfer is what 300 problems will buy you, applying what you've practised to similar setups. Far transfer is what FAANG selects for, applying what you've understood to genuinely new ones.

There's a second issue with self assessed confidence. It swings with your last session. Crush five tree problems on Saturday morning and you feel ready. Freeze on an unfamiliar graph problem on Saturday afternoon and the confidence evaporates. Neither data point reflects your stable ability across the families an interview actually draws from.

The result is a loop. You prep, you feel uncertain, you prep more, you still feel uncertain. The method of evaluation is wrong. You're asking a feelings question about a performance outcome.

Interview readiness isn't confidence. It's repeatable performance under unfamiliar conditions.

The three pattern family test

Readiness is a performance threshold you can measure. The protocol takes about two hours and produces a binary answer.

Pick an unseen medium from a family you've studied. Sliding window, tree traversal, graph BFS, DP subsequence. The problem has to be genuinely novel. You haven't solved it, browsed its discussion thread, or read hints for it.
Solve it under real interview constraints. Twenty minute timer. The problem name covered or aliased so you can't reverse engineer the family from the title. No hints. A hard cap on code execution attempts so you can't trial and error your way through. You have to identify the approach, build it, and trace it before running code.
Repeat across two more families you've studied but haven't over practised. One pass isn't signal. Three passes across different families confirms the readiness is broad, not narrow.

Pass means: solve within twenty minutes with fewer than two failed execution attempts. Anything else is useful data.

If you pass three across different families and you likely have the level of transfer real interviews actually reward. If you fail one, you know precisely where to work.

What that looks like on graph BFS

Pick the worst case for this exercise: a medium graph BFS problem you haven't seen. The constraints describe a grid, an adjacency list, or some traversal where shortest distance is the answer.

Two minutes in, you've identified the family. Not from the problem title because that's hidden. From the constraints: shortest distance, unweighted edges, layered exploration. That recognition came from training what makes BFS the right approach, not from spotting "BFS" in the problem name.

The solution builds from BFS's invariant. At any moment, the queue contains every node whose shortest distance from the source is exactly the distance you're currently processing. You aren't recalling "this one used a deque." You're reasoning: enqueue the start at distance zero, expand neighbours level by level, return as soon as you pop the target.

from collections import deque

def shortest_path(graph, start, target):
    queue = deque([(start, 0)])
    visited = {start}
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        for nbr in graph[node]:
            if nbr in visited:
                continue
            visited.add(nbr)
            queue.append((nbr, dist + 1))
    return -1

Before you run anything, you trace it on a four node example. Walk the queue. Check visited. Verify the returned distance matches what you'd expect for a path you can see in your head. The mental dry run catches bugs the random test and submit loop misses, and it's the exact behaviour interviewers watch for: verifying correctness without leaning on the compiler.

You submit. It passes. Eight minutes still on the timer. Not because you rushed, but because identification took two minutes instead of fifteen, and the construction followed the invariant rather than trial and error.

Recognition under pressure matters more than recall in comfort.

That is what FAANG ready looks like. Not "I feel confident." A repeatable, observable performance.

A second pass on a different family

Now you change family. Pick a variable sliding window problem you haven't seen. The constraint shape: a contiguous range over an array or string, a flexible boundary that grows and shrinks, an objective that asks for the longest, shortest, or maximum window meeting some condition.

The recognition again happens within the first three minutes, before any code. The constraints match the variable sliding window's three triggers, you can name the invariant the window has to maintain, and you write the same expand then contract skeleton you'd write for any problem in the family.

def variable_window(arr, valid):
    left = 0
    best = 0
    state = init_state()
    for right in range(len(arr)):
        state = include(state, arr[right])
        while not valid(state):
            state = exclude(state, arr[left])
            left += 1
        best = max(best, right - left + 1)
    return best

You fill in init_state, include, exclude, and valid for the specific problem. The skeleton stays the same. That's the marker of a pattern that's actually generalised in your head: you write the skeleton first, then specialise.

When a pattern generalises, you stop memorising solutions and start specialising frameworks.

If you pass this one too, you've got two of three. One more, on a third family you haven't over practised, decides it.

When you fail the test

Most engineers don't pass all three on the first attempt. That's expected. A clean three for three on the first try usually means the families were too comfortable.

One family failed. You know the pattern at a surface level but haven't internalised the identification triggers or the construction skeleton. Go back to the foundational material for that family. Don't just grind more problems in it. Study what makes the pattern applicable, the constraint combinations that point to it, the invariant every problem in the family shares. Once you can articulate that without notes, retest with a different unseen problem.
Two families failed. You likely have one strong area where you've over practised and shallow gaps everywhere else. Common for engineers who spent months on arrays or trees because the work felt productive. Broaden the coverage. Spend focused time on the families where the understanding is thin.
All three failed. The preparation has been building near transfer without building far transfer. That's a method gap, not a talent gap. Shift from solving high volumes to studying fewer problems more deeply. Focus on identification and constraint analysis rather than just reaching a correct solution.

One catch. Don't retake the test with the same problems. A retest on a problem you've already seen, even if you failed it, measures recall instead of reasoning. Find a different unseen problem in the same family.

The four signals most engineers use instead

Before the test, it helps to name the signals you've probably been using, and why each one lies.

Problem count. Tells you nothing about how the problems were solved. Someone at 120 problems with genuine pattern depth outperforms someone at 400 who relied on hints for half of them.
Topic completion. You finished sliding window two months ago and haven't touched it since. Completion isn't retention. Spacing matters. The performance you had on week three doesn't survive without revisits.
Speed on familiar problems. Two Sum in two minutes feels like fluency. It's actually retrieval of a stored solution. The moment a novel problem looks similar but has different constraints, the speed evaporates.
Peer comparison. Your friend got into Google in six months. That ignores their background, their pattern coverage, how they practised, and what level they interviewed for.

The three family test bypasses all four. It doesn't care about the count, the completion checkmarks, the recall speed, or anyone else's timeline. It measures one thing: can you construct a solution to a novel problem, under pressure, across families.

Setting up the conditions yourself

The hardest part of the test is replicating real interview conditions. Solving at your desk, documentation a tab away, with the timer optional, doesn't replicate a forty five minute FAANG round.

What you actually need: a source of unseen mediums in the families you've studied (the variable sliding window lesson covers one family if you haven't been through it before), a way to hide the problem name (a friend covering it, or a browser extension that aliases the title), a kitchen timer set to twenty minutes, and the discipline to stop after two failed runs. The conditions matter. The test fails the moment you peek at hints or let the timer slide.

I keep noticing the same two things across engineers who run this test for the first time. The ones who fail one family and immediately know why aren't far from ready, they're a couple of weeks of focused study away. The ones who fail all three and panic into more volume usually need to step away from the problem bank for a week and re read the foundational material on identification and invariants. The diagnostic is more useful than the score.

If you're stuck in the “I've solved a lot but still don't know if I'm ready” phase, the problem usually isn't effort.

It's measurement.

I wrote a longer breakdown covering:

per family readiness signals
common failure patterns
and what to fix when one family collapses under pressure

Full breakdown here

What's the specific moment you knew you weren't ready yet? A particular problem, a frozen minute in a mock, or the cumulative shape of practice that just felt off?

Algorithmic intuition matters more than problem count in coding interviews

Prakhar Srivastava — Thu, 07 May 2026 12:31:30 +0000

Two engineers prep for the same cycle. One solves more than 500 problems and freezes when the medium doesn't look like anything from the practice list. The other solves a fraction of that and works the problem out from scratch on the screen. The variable that decides which way it goes isn't volume.

TL;DR

Volume practice builds memory of specific problems. It builds little of the skill that recognises which technique applies to a problem you've never seen.

Learning science calls these near transfer (familiar problems) and far transfer (unfamiliar ones). Volume practice mostly trains near transfer.

Real interviews test far transfer because the problem isn't labelled and won't match anything in the practice bank.

Recognition is trainable. The training is explicit: read the problem for triggers, name the pattern, then write code.

On the next problem you face, the recognition pass takes 30 seconds before you touch the keyboard. That pass is the gap.

Disclosure up front: I built Codeintuition, a structured learning platform for coding interviews. This post is about the recognition skill that decides whether volume practice converts to interview readiness, not about the product. The closing link goes to the longer version on my own blog.

What 500 problems actually trains you to do

Most coding interview advice tells you to solve more problems. There's a real reason this advice exists. Volume builds fluency: you stop being confused by syntax, you stop misreading constraints, and the interview minutes that used to go to typo-hunting start going to the actual problem. Past a few hundred problems, those skills are usually solid.

What volume doesn't reliably build is the ability to read a problem you've never seen and decide which technique applies. That's a different skill, and the way most engineers practise actively trains around it. You attempt the problem, get stuck, glance at the LeetCode tags, notice it says stack, and read a solution. The next time a stack problem shows up, you might recognise it. The time after, you might not. Recognition is being built by accident, not by design.

In an interview the tag is gone. The problem statement isn't labelled stack or sliding window or dynamic programming. So the skill that's been built by accident has to do work it's never been explicitly trained for. That's where the freeze comes from.

Near transfer vs far transfer

There's a useful piece of language for this from the learning sciences, and it's worth borrowing because it predicts the failure mode precisely.

Near transfer is when you can solve a problem because it resembles one you've practised. You solved Two Sum with a hash map. The interviewer hands you Two Sum II with a sorted array. The visible details changed but the underlying idea is close enough that recognition fires.

Far transfer is when you can solve a problem that doesn't resemble anything in your practice set, by reading the structure of the problem and constructing the approach from first principles. You see "minimum window of an array containing all characters of a target string" and you've never solved a window problem with a character constraint. You read the structure and construct a variable sliding window from scratch.

Grinding 500 problems builds near transfer well. It does much less for far transfer. Whether far transfer is reliably teachable is a debate the research on transfer of learning hasn't fully settled, but the evidence does support one specific intervention. Explicit instruction in when and why a method applies, not just how to execute it, produces more transfer than practice alone.

A worked example: monotonic stack on stock span

Here's the kind of problem where the gap shows up. You're given an array of stock prices. For each day, find how many consecutive days before it had a price less than or equal to that day. The constraints don't mention "stack" anywhere.

If you've practised the technique without practising the recognition, you'll probably try a nested loop first, hit O(n^2), and try to remember which problems you've seen with this shape. If recognition is trained, you read the problem's structure and three triggers fire:

"For each day" means you need an answer per element. Element-wise, not aggregate.
"Consecutive days before it" means a directional search to the left.
"A price less than or equal to" means a comparison condition between the current element and what's to its left.

Three triggers point at one technique: the previous closest occurrence pattern, implemented with a monotonic stack. The triggers are what you read off the problem statement. The pattern is what you write in code.

def stock_span(prices):
    stack = []
    spans = []
    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] <= price:
            stack.pop()
        span = i - stack[-1] if stack else i + 1
        spans.append(span)
        stack.append(i)
    return spans

The implementation is short and well documented across the internet. The bottleneck isn't writing the loop. It's noticing that "for each element, find the previous element satisfying a comparison condition" is one recognisable shape that always uses this technique. That's the recognition skill, and it's the part most prep doesn't train.

What a recognition drill looks like

Before solving a problem, do a 30 to 60 second pass on the statement alone. No code. The output of the pass is a name: which pattern, and why.

For each technique you've learned, you should be able to name the two or three observable features of a problem statement that signal it applies. A few common ones from the techniques most coding interviews lean on:

Variable sliding window: contiguous subarray or substring, plus a condition that holds across the window, plus an optimisation on window length. When all three appear, it's almost always this technique.
Two pointers: a sorted array (or one you can sort) and a search for a pair or triple satisfying a target. The pointers move from the ends inward.
Monotonic stack: per element answer, plus a directional search left or right, plus a comparison condition. Stock span fits. Next greater element fits.
Backtracking: enumerate combinations or paths under a constraint, with the option to abandon a partial candidate when the constraint is violated.

When you start a problem, the drill is: read the constraints, list the features you see, name the technique, then start coding. If you can't name a technique in 60 seconds, you don't start coding. You re-read the constraints with the trigger checklists in front of you and try again. If you still can't, mark the problem and learn the missing feature before moving on.

The first time, this feels artificial. After 30 problems, it stops feeling artificial because the features start firing automatically as you read.

The other thing prep tends to skip

A bit of honesty before the close. Recognition isn't the only thing prep tends to skip. The conditions you practise under matter at least as much, and the default LeetCode loop is much friendlier than an interview.

The default loop has the title visible, the difficulty visible, the company tags visible, the discussion section a click away, and no clock. None of those are present in the actual interview. If your reads of the problem have always been informed by the tag, the moment the tag disappears the read gets harder.

A reasonable practice protocol for the last few weeks before an interview cycle:

Cover the problem name with a sticky note before reading the constraints. Many problem names give away the technique.
Set a 25 minute clock per medium. If you blow past it, that's data: the problem went to "still working" rather than "solved", and the next pass focuses on what slowed you down.
Skip the discussion section on the first attempt. Read it after, only if your attempt didn't converge.
Mix techniques. Three sliding window problems in a row trains nothing about recognition because the third is obvious by inertia. Three problems from different techniques force you to read the constraints.

You can run all of this against any problem bank. It's a practice protocol, not a feature.

When grinding more is the right move

Volume practice is the right call in two cases. First, when your fundamentals on a specific data structure or algorithm are weak enough that you can't implement it cleanly even with the technique handed to you. There, more reps fix the bottleneck directly. Second, when you're a few weeks out from an interview cycle and the goal is speed, not depth. The features you've already internalised get faster with reps.

The cases where volume stops working are different. When implementation is solid but recognition under unfamiliar problems is the bottleneck, more reps don't move the needle because they aren't training what's broken.

What the next problem looks like with this trained

Six months out, you open an unfamiliar problem on a phone screen. The description mentions "for each element, count how many elements to the right are strictly greater before reaching one that's less or equal." Nothing in your practice list looks like it.

Reading for features gets you somewhere. "For each element" is element-wise. "To the right" is directional. "Strictly greater" is a comparison condition. All three match a monotonic stack, written from the right toward the left. You're 30 seconds in and writing the loop.

That's a trained skill. Volume helped, structure helped more, recognition is what closed the gap.

If unfamiliar mediums still freeze you even after hundreds of problems, the bottleneck usually isn't implementation.

It's recognition.

I wrote a longer breakdown covering:

feature checklists for six major interview patterns
near transfer vs far transfer
and the exact recognition drills that made unfamiliar problems feel solvable again

Full breakdown here

Which technique's features finally clicked for you only after seeing it on a problem the explanations had skipped?

How to Prove Your Algorithm Works in a Coding Interview

Prakhar Srivastava — Wed, 06 May 2026 14:00:00 +0000

An interviewer asks you to convince them your algorithm works. You walk through [2, 1, 5, 1, 3, 2] with K=3, get 9, and stop. The interviewer waits. You realise that what you did was test one input, not prove correctness, and you don't have anything else to say.

TL;DR: Proving your algorithm works in interviews isn't a formal induction. It's two things: state what property your loop maintains at each step (the invariant), then check initialization, termination, and edge cases. Tracing one example is testing, not proving. The invariant is what bridges one input to all of them.

What "prove your algorithm is correct" actually means in an interview

If you took a discrete math course, you spent weeks on induction proofs with formal notation. That isn't what an interviewer wants. They want what a senior engineer does in code review: read the loop, ask "what's true at each iteration?", and check whether that property forces the right answer.

The two are related. They share the invariant idea. But the academic version is a paper proof, and the interview version is a 90 second verbal walkthrough. Mixing them up is why most candidates either freeze or write something that looks like exam notation.

When the interviewer says "convince me this works," they want three things in order: the property your loop holds, evidence it holds at every step, and a check that the final state gives the right answer. Doing this clearly is rare, and noticeable when you can.

The two checks

Two checks carry the whole method.

State and verify the loop invariant. Before tracing any code, write down what's supposed to be true at the start of each iteration. Then trace 3 to 4 iterations, confirming the property after each one.
Check boundaries and termination. The invariant covers the loop body. Boundaries cover what happens before the loop starts, after it ends, and on degenerate inputs (empty array, single element, all identical values, maximum size).

Most candidates skip step 1 and jump straight into tracing a specific input. That's testing. Testing tells you it works for that input. The invariant tells you it works for every input.

The difference matters when an interviewer asks about an input you didn't trace. "My sliding window maintains the sum of exactly K elements at each step, and the update adds the new element and subtracts the leaving one" lets the interviewer check the mechanism. "I ran it on [2, 1, 5, 1, 3, 2] and got 9" leaves them wondering about everything else.

A worked example: fixed sliding window

Take the classic problem: given an array and a window size K, find the maximum sum of any contiguous subarray of length K.

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

Step 1: State and verify the invariant

The invariant: at the start of each iteration, window_sum equals the sum of elements in the current window of K elements.

Trace it on arr = [2, 1, 5, 1, 3, 2] with K = 3:

Before the loop: window_sum = 2 + 1 + 5 = 8. The window covers indices 0..2. The invariant holds.
i = 3: window_sum = 8 + arr[3] - arr[0] = 8 + 1 - 2 = 7. The window is now [1, 5, 1], and 1 + 5 + 1 = 7. Holds.
i = 4: window_sum = 7 + arr[4] - arr[1] = 7 + 3 - 1 = 9. Window is [5, 1, 3], sums to 9. Holds.
i = 5: window_sum = 9 + arr[5] - arr[2] = 9 + 2 - 5 = 6. Window is [1, 3, 2], sums to 6. Holds.

The reason the invariant is maintained matters more than the trace itself. The update adds the element entering the window and subtracts the one leaving. That's the mechanism, not just the result.

Step 2: Check boundaries and termination

Initialization: the code computes the sum of the first K elements directly, so the invariant holds before the loop runs.

Termination: the loop runs from K to len(arr) - 1, so the final window covers the last K elements. max_sum has tracked the maximum across every window the loop visited.

Edge cases:

K == len(arr): the loop body never runs, and the initial window_sum is already the answer.
All negative numbers: the invariant doesn't depend on sign, so it still holds.
K == 1: each window is one element. The update shifts by one position correctly.

That's a complete interview-grade correctness argument. You stated what's true at every step, you explained why the update preserves it, and you confirmed the final state gives the right answer.

Where most candidates lose the argument

Five ways correctness reasoning falls apart, all avoidable:

"It works on my example" fallacy. Tracing one input is a single data point. You haven't proven anything about the inputs you didn't trace. The invariant is what generalises.
Not articulating the invariant. You probably have an intuitive sense of what each iteration does. Without putting that into a checkable sentence, the interviewer hears handwaving at the code, not a claim.
Skipping boundary checks. The invariant covers the loop body. It doesn't tell you what happens on an empty array, a single element, or when K equals the array length. Each of those needs separate verification.
Proving termination, not correctness. "The loop runs n times and exits" tells the interviewer the algorithm halts. It says nothing about whether the output is right. Termination and correctness are independent properties.
Overcomplicating the argument. If your reasoning takes three paragraphs, your algorithm might be too complex. Simpler algorithms have simpler invariants. That's part of why interviewers prefer elegant solutions.

Invariants change shape across patterns

The sliding window invariant tracks one running variable. Other patterns produce invariants with different shapes, and recognising those shapes is half of what makes the skill transfer.

Pattern	Invariant shape
Sorted two pointers	The answer, if it exists, lies within `[left, right]`. Each step shrinks the search space without skipping a valid pair.
Binary search	The target, if present, lies within `arr[low..high]`. Every iteration halves the range while preserving that guarantee.
BFS on unweighted graph	When a node is dequeued, its recorded distance equals the shortest path from the source. This depends on FIFO ordering and equal edge weights.
Topological sort via DFS	A node is added to the result only after all its descendants have been added. Reversing the post-order produces a valid ordering.
0/1 knapsack DP	`dp[i][w]` equals the maximum value using items `0..i` with capacity `w`. Each cell depends only on previously computed cells.

The two step structure is the same across all of them. State the property, verify the boundaries. What changes is what the invariant looks like and how many variables it tracks.

Practising under time pressure

Knowing the method and producing one in 45 minutes are different. The bottleneck isn't understanding what an invariant is. It's stating one quickly for an algorithm you just designed.

A drill that works: pick a problem you've already solved. Set a timer for 60 seconds. Try to state the loop invariant in one sentence. If you can't, that's a signal you solved the problem by pattern matching, not by understanding what made it work. Re-read the code and figure out what property the algorithm depends on.

Run that drill on five problems across five different patterns each week. After a month, two things change. First, articulating invariants becomes reflexive. Second, your debugging gets faster, because checking whether the invariant still holds at each step pinpoints the broken iteration faster than tracing the full execution.

A second drill is wrong invariant spotting. Take a correct algorithm. Write down an invariant that sounds plausible but is subtly wrong. Find the iteration where it breaks. This trains the gap between invariants that describe what the code does and invariants that guarantee correctness. Most interview mistakes live in that gap.

I keep watching this play out across engineers I see prep. The ones who can articulate invariants under pressure are usually the ones who solved fewer problems but understood each one more deeply. The ones who froze had solved more but couldn't say what made any single algorithm work.

If you want a worked walkthrough of why the variable sliding window update preserves the invariant before you ever solve a problem with it, the variable sliding window lesson walks through it step by step.

Two halves of the same skill

Correctness reasoning and mental dry running pair together. The dry run gives you the trace. The invariant gives you the claim to verify against the trace. Practising them apart leaves a hole that interview pressure exposes. Practising them together is what makes the reasoning hold up when the algorithm is one you just designed.

The same idea shows up in dynamic programming. When you derive a recurrence, you're implicitly stating an invariant: dp[i] represents the optimal answer for the first i elements. Proving that recurrence correct uses the same two step structure, just with a table-shaped invariant instead of a scalar one.

If you’ve ever frozen when an interviewer said “prove your algorithm works,” the missing piece usually isn’t more problems.

It’s learning to articulate the invariant.

I wrote a longer breakdown covering:

nested loop invariants
wrong invariant drills
DP correctness reasoning
and how to structure interview-grade proofs without formal notation

Which algorithm did you finally feel confident in only after you could state its invariant out loud?

AlgoExpert vs NeetCode: The Interview Skill Neither One Actually Trains

Prakhar Srivastava — Tue, 05 May 2026 22:31:58 +0000

A few years back I worked through both AlgoExpert and NeetCode while preparing for interviews. The 100 polished videos and the 400+ free walkthroughs were useful for what they covered. The interview round that broke me wasn't a problem either platform had skipped. It was a problem they both had a clean walkthrough for, where I could read either solution after the round and recognise the technique, but in 25 minutes against a whiteboard I couldn't see it.

The problem was Longest Palindromic Substring. Both platforms have a video. Both derive expand around centre cleanly. After watching either, the technique makes sense. The issue was the interviewer didn't say "this is a palindrome expansion problem." The prompt said "find the longest substring that reads the same forwards and backwards." That gap, between the technique I could follow on a video and the technique I could spot from a description, is what neither platform set out to train.

TL;DR: AlgoExpert wins on video depth per problem. NeetCode wins on breadth and free access. Both teach how techniques work after you've named the technique. Neither teaches the recognition before the technique gets named, and that recognition is what an unseen medium problem tests.

What AlgoExpert is good at

Clement's videos are clean. There's no other word for them. He picks 100 problems, records each one, walks brute force to optimal in a consistent visual style, and the editing makes the reasoning easy to follow. The single instructor consistency is underrated. After three videos you've adapted to his vocabulary, his pacing, and his shorthand for tradeoffs. From video four onward you spend less time adapting and more time absorbing.

The browser IDE inside AlgoExpert is also the best of any platform I tried that leads with video. After watching the walkthrough you have a workspace already loaded with the function signature, the tests, and the language template. The transition from passive watching to active solving costs you no setup, which matters more than it sounds.

The bundle is the other thing the platform gets right. SystemsExpert and FrontendExpert sit beside AlgoExpert under one account. If you're prepping across DSA, system design, and frontend rounds, paying once for three coordinated curriculums is a real saving in cognitive load alone. The argument that "100 problems is too few" misses what AlgoExpert is going for. The platform aims for depth on a small set, not coverage of everything. On that goal it lands.

What NeetCode does well

NeetCode's free tier is the best reason to start there. The YouTube channel covers more problems than most paid platforms, and the production quality has improved year over year. NeetCode 150 is the most widely shared curated list in the prep community for a reason. You get a defensible problem ordering without any commitment.

The community momentum is the second thing NeetCode does that almost nobody else matches. Engineers swap solutions in the YouTube comments, swap timelines on the subreddit, swap notes in Discord. Studying alone is the failure mode for most preparation. A platform that pulls you into a group of people preparing in parallel is doing real work, even if the work isn't a feature on a comparison sheet.

The mapping to LeetCode is also worth naming. The problems you practise on NeetCode are the same problems Big Tech screening tools serve, which means your practice environment matches your screening environment. AlgoExpert's IDE is more polished, but NeetCode's environment matches what you'll actually face when a recruiter sends you a Codility or HackerRank link.

The shared gap, made concrete

Take Longest Palindromic Substring. The interview prompt is one sentence: given a string, return the longest substring that reads the same forwards and backwards. AlgoExpert's video derives expand around centre cleanly. NeetCode's video does the same with a slightly different style. Watch either and the solution makes sense.

What neither video sets you up to do is the move that happens before the technique gets named. The move is reading the prompt, noticing that a substring is being asked for, noticing the symmetry constraint, and reaching for expand around centre rather than DP because of those two visible features. In an interview, no one labels the problem for you. Your search for a technique starts from the description, not from a category tag.

The pattern repeats across topics. Take a tree problem like Binary Tree Maximum Path Sum. Both platforms have walkthroughs. After watching either you can reproduce the postorder helper that returns the local max while updating a global. What neither walkthrough installs is the recognition that "any node, any path, any direction" signals the helper-with-side-effects pattern. The walkthrough teaches the pattern. The recognition is a separate skill the walkthrough assumes you'll pick up by exposure.

What recognition is, mechanically

Recognition is a small set of features you can name on the prompt before any code is written. For expand around centre, the features are roughly:

The output is a substring of a string.
The constraint involves symmetry, palindromes, or some "reads the same in both directions" property.
Other approaches bottom out at quadratic, so the technique you're looking for is O(n^2) or O(n log n), not O(n) or sub-linear.

When all three apply, expand around centre is the candidate technique to try. Longest Palindromic Substring matches all three. Palindromic Substrings (count, not length) matches the first two. Both fall under the same recognition rule.

This is the part neither AlgoExpert nor NeetCode targets directly. Their walkthroughs assume you've already arrived at the technique, then explain it. The arriving is the work no one is helping you do.

Why volume alone doesn't close it

The cognitive science name for this is the generation effect. Producing an answer from first principles, even imperfectly, builds stronger memory and stronger transfer than recognising a familiar solution. Watching a walkthrough builds recognition of an answer you've been shown. Interviews ask for generation, where you produce the technique from a description you haven't seen.

What you watch and what you generate aren't the same skill. Watching ten variants of expand around centre gives you a strong recognition memory for variants close to what you watched. The interview problem is rarely close enough. It tends to look just different enough that the recognition memory misses, and you stall on what to try next.

The transfer of learning literature splits this into near transfer and far transfer. Near transfer is solving problems that look like ones you've already solved. Far transfer is reasoning through problems that look different but follow the same underlying pattern. Volume in the AlgoExpert / NeetCode mode produces near transfer reliably. Far transfer comes from a different practice shape, where the recognition gets trained on its own.

A recognition protocol you can run this week

If you've worked through either platform's content and unfamiliar mediums still freeze you, the move isn't another fifty walkthroughs. It's a tighter loop on recognition first.

Pick one technique a week. Expand around centre, sliding window, two pointer, monotonic stack, postorder with side effects.
Write down the trigger features for that technique. Three or four specific features you can see in a problem statement that, when they all apply, make this technique the candidate. Write them in your own words, not from a cheat sheet.
Read five problems that use this technique without solving them. For each, name the triggers you can see in the prompt before reading any constraints in detail.
Solve three or four problems on the technique with the problem name and category tag hidden. The cover-the-name move is what forces you to recognise the technique before coding starts.
Once a week, do one pressure session. Cover the title, set 25 minutes, talk through your reasoning out loud, and don't open the IDE until you've named the technique you intend to use.

A technique a week, eight or ten weeks of focused work. That replaces the hundred-plus mediums where the signal you actually need gets buried under details that don't matter.

Both AlgoExpert and NeetCode are reasonable choices for the watching part of this loop. Once you've watched the technique once or twice, the work that compounds is the recognition reps the walkthroughs don't include.

If you’ve already watched hundreds of walkthroughs but still freeze on unfamiliar mediums, the problem usually isn’t knowledge.

It’s recognition.

I wrote a longer breakdown comparing AlgoExpert and NeetCode on:

depth vs breadth
passive watching vs active recall
and the recognition drills that finally fixed this for me

When did the recognition click for a pattern you used to watch and re-watch without spotting on a fresh problem, and what was the specific problem that broke it open?

The 90 Day FAANG Prep Plan That Actually Works

Prakhar Srivastava — Mon, 04 May 2026 20:30:50 +0000

You count the weeks between today and your on site. Twelve. You pull up a 90 day FAANG prep plan and the structure looks reasonable: easy problems for two weeks, mediums for six, hards for the rest. Six weeks in, you hit binary trees and realise your recursion is shaky. Two weeks later you try a DP problem and can't formulate the recurrence. Suddenly the 12 week plan is a 6 week plan with 6 weeks of rework.

Difficulty isn’t the problem. Order is.

TL;DR: A 90 day FAANG plan works when topics are ordered by dependency, not by difficulty or popularity. The typical "easy then medium then hard" plan ignores that DP needs recursion, recursion needs the call stack, and the call stack needs array fundamentals. Sequence by what each topic requires, not by how hard it feels.

What "wrong order" actually looks like

The failure mode in most 90 day plans is the same shape every time. The plan groups topics by surface difficulty: arrays first because they are easy, DP last because it is hard. Or the plan groups by frequency: arrays first because they appear most, then strings, then trees, then DP. Both shapes ignore that DSA topics have hard prerequisites.

You can't reason about binary tree traversal without recursion. You can't build recursive intuition without the call stack. You can't pattern-match on hash table problems until you have internalised what O(1) amortised lookup actually buys you. These gaps don't show up in Week 2. They show up around Week 5 or Week 7, deep enough into the plan that you've already built a lot on top of unstable ground.

When that happens, the plan quietly stops working. You either skip the prerequisite to "stay on schedule," which compounds the gap into every later topic, or you stop and rebuild, which eats two of the remaining weeks. Either way, the timeline collapses.

The order that actually works

Here's the dependency order that emerges after watching dozens of engineers prep:

Weeks 1 to 2: Arrays and linked lists. Two pointers, sliding window, interval merging on arrays. Reversal, fast and slow pointers, merge patterns on linked lists. About fifteen patterns. Everything else builds on these.
Weeks 3 to 4: Hash tables and stacks. Hash tables unlock counting, prefix sum, and the harder variants of sliding window. Stacks unlock monotonic stack, sequence validation, expression evaluation. Both are prerequisites for tree traversal.
Weeks 5 to 6: Queues, binary trees, BSTs. Queues for level order BFS. Trees for preorder, postorder, root to leaf paths. BSTs for sorted traversal and range operations. Pattern density picks up fast here.
Weeks 7 to 8: Heaps, recursion, backtracking. Heaps for top K and comparator patterns. Recursion formalises head recursion, tail recursion, and multiple recursion. Backtracking introduces enumeration and constraint search.
Weeks 9 to 10: Graphs, sorting, searching. DFS, BFS, Dijkstra, topological sort. Quickselect and custom compare. Binary search variants including predicate search on the answer space.
Weeks 11 to 12: Dynamic programming and review. DP last, because DP is what every previous topic was preparing you for.

The Wikipedia article on the spacing effect summarises why this order also helps retention: practice distributed across weeks, with each week building on the last, produces stronger durable recall than the same volume crammed late. The dependency order isn't only logical, it's also how you keep the early weeks from fading by Week 12.

Why DP belongs at Week 11, not Week 3

Take Coin Change, a standard DP interview problem. To derive the solution rather than memorise it, you need three things lined up:

A recurrence relation. Built on top of recursion fluency.
Recognition of overlapping subproblems. Built on top of seeing how multiple recursive calls share state.
Memoization. Built on top of understanding how cached results map to subproblem states.

Now imagine an engineer who reaches DP in Week 3. They've covered arrays, maybe linked lists. They have not internalised the call stack, they have not seen recursion expressed as a recurrence, they have not seen overlapping subproblems show up anywhere. The Coin Change solution they study isn't reasoning, it's a string of four lines they're supposed to remember:

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

The engineer who reaches the same problem in Week 11 sees this differently. They've spent four weeks with recursion. They've built backtracking on top of multiple-call recursion. They've seen the same dp[i] shape applied to climbing stairs, then to longest increasing subsequence, then to Coin Change. The recurrence dp[a] = min(dp[a], dp[a - c] + 1) doesn't have to be remembered, because they can re-derive it from the invariant: dp[a] is the minimum number of coins to make amount a, and the only way to make a is to make a - c for some coin c and add one.

That's the difference dependency order produces. Not more knowledge. Knowledge that holds together under interview pressure because every piece supports the one above it.

When to add timed pressure (load-bearing)

It is easy to practise in comfort conditions for eleven weeks and then panic in your first mock interview. The gap between "I solved this at my desk with no timer" and "I solved this in 20 minutes with no hints" is wider than most engineers expect. The right time to introduce timed practice is after the foundations are solid but before the advanced topics start. Around Week 6.

By Week 6, you've covered arrays, linked lists, hash tables, stacks, queues, and started binary trees. That's enough pattern coverage to attempt timed problems honestly. You won't know every pattern yet, but you know enough to practise the skill of solving under pressure separately from the skill of learning new patterns.

From Week 6 to Week 8, attempt previously completed problems under a timer. Twenty minutes for mediums, thirty for hards. No hints, no notes. The goal isn't a clean pass rate, it's training the feeling of working without the safety of references while the material is still fresh in your mind.

From Week 9 to Week 12, switch to multi problem assessments under a 50 minute timer, the way actual rounds work. You'll have covered enough of the patterns by then to simulate realistic interview coverage.

Productive struggle vs spinning

Plans break. You'll have a week where work blows up, or you'll hit a topic that takes longer than expected. The better question isn't "how do I avoid falling behind," it's "how do I tell whether I'm stuck productively or just spinning."

The two look similar from the inside but feel different in one specific way:

Productive struggle. You can name what you don't understand. "Merge sort is O(n log n), but the reason the divide step doesn't add extra cost isn't clicking." That's a specific gap you can target with a specific lesson, problem, or question.
Spinning. You're re-reading the same material without forming new questions. You've watched the same walkthrough three times and still can't reproduce the logic from a blank screen.

If you're spinning, change the input. Try solving a strictly simpler variant. Try writing the solution from memory without any reference, even if you produce something wrong. Try explaining the concept out loud as if to a junior. The act of generating an attempt, even a broken one, surfaces the missing piece more clearly than another round of passive review. This is the generation effect doing real work for you.

Concrete checkpoints (because vague progress isn't progress)

Vague progress signals like "things are starting to click" don't survive interview-week stress. Use concrete checkpoints at each month boundary. If three or more items at any checkpoint don't describe you, don't move to the next month. Spend an extra week on the weak areas. A 13 week plan that's solid beats a 12 week plan with holes.

By Week 4, you should be able to:

Solve array two pointer and sliding window problems without looking up the pattern.
Trace linked list reversal mentally, tracking pointer state at each step.
Explain why a hash table lookup is O(1) amortised, not just that it is.
Identify which stack pattern applies from the problem statement alone.

By Week 8:

Trace a binary tree postorder traversal on paper, tracking state at each node.
Reason about BST problems through the sorted traversal invariant.
Write a recursive solution and walk through how the call stack unwinds.
Have attempted ten or more problems under timed conditions, with a pass rate above 50%.

By Week 12:

Identify DP subproblems and formulate recurrences for problems you haven't seen.
Choose between BFS and DFS for a graph problem and explain why.
Complete a 50 minute multi problem assessment with at least one correct solution.
Hit the timer without reaching for the solution tab first.

If you can't honestly check most of these, your plan needs an extra week, not a heroic weekend.

Your final week

Week 12 isn't for new material. If you're still covering fresh topics with seven days to go, something earlier broke. The final week is for consolidation under realistic conditions.

Days 1 to 3 are targeted weak spot practice. Look back at the timed results from Weeks 9 to 11. Which topics had the lowest pass rate? Which patterns did you fail to identify within the first five minutes? Spend three days isolating those specific patterns and attempting two or three problems that test exactly that pattern. Don't re-study the entire topic. Isolate the gap.

Days 4 to 5 are full simulation rounds. Two complete mock interview simulations. Forty five to fifty minutes, two problems, no IDE autocompletion, talk out loud as you write. If you don't have a partner, record yourself. The recording forces the same "someone is watching" pressure that slows people down in real interviews. Pay attention to time allocation. The most common failure pattern is spending thirty minutes on the first problem and having fifteen for the second. Practise the discipline of checking your progress at the 20 minute mark and making a deliberate decision about whether to keep debugging or move on.

Days 6 to 7 are rest and review. Stop solving new problems. Review your notes on the three or four patterns you found hardest. Get enough sleep. The difference between a well rested engineer who's covered 90% of the material and an exhausted engineer who's crammed 100% is measurable in interview performance. Fatigue degrades pattern recognition speed before it degrades anything else, and recognition speed is exactly what interviews test.

The order is the advantage

Compressing the whole roadmap into one rule: study what each topic requires, not what feels hardest. The Coin Change recurrence at Week 11 holds together because every layer below it (recursion in Week 7, stack mechanics in Week 4, array fundamentals in Week 1) was built before it was needed. An engineer who jumps to DP in Week 3 isn't ahead, they're standing on nothing.

If you want the full version of this roadmap with exact problem lists, pattern breakdowns, and weekly schedules I’ve written it here

This post gives you the structure.

The full guide gives you the execution.

What’s the topic in your prep where the dependency chain finally clicked—and which week did it happen?