Data structures & algorithms

Amortized O(1) promises nothing about one call, which may cost O(n). It bounds the total cost of any n operations at O(n) — a worst-case guarantee over a whole sequence, not an average over likely inputs.

Doubling makes each resize twice as rare as the last, so the copies across n appends sum to 1+2+4+...+n, which stays under 2n. That is O(n) total work spread over n appends, hence O(1) per append on average over the sequence.

Target O(n log n) or better. Quadratic work at n = 100,000 is about 10^10 operations, far past the rough budget of 10^8 simple operations per second, while n log n lands near 1.7 million — comfortably inside it.

Each membership check scans everything kept so far, so the check at step k costs O(k), not O(1). Summing 1 through n gives O(n^2). A hash-based set makes each check expected O(1), so the whole pass becomes O(n).

Loops side by side add their trip counts: n + n = 2n, and constants drop, so it stays O(n). Nesting multiplies instead: the inner loop restarts in full for every outer step, giving n * n = O(n^2).

A dynamic array tracks two separate numbers: size, the elements in use, and capacity, the slots allocated. Removing elements lowers size only. The underlying buffer stays as large as it ever grew until something explicitly shrinks it.

Size is how many elements are stored; capacity is how many slots the underlying block can hold. Appending when size equals capacity forces allocating a larger block, copying every stored element into it, and releasing the old one.

In-place compaction never shrinks the array, so survivors occupy only a prefix and stale values still sit in the tail. The returned write count is the only signal of how many entries are valid.

Each swap places two elements at once, so n/2 swaps fix all n positions. Looping over every index instead swaps each pair twice, which undoes the reversal and hands back the original array.

A flat row-major buffer stores each row as width consecutive slots, so the cell at column x, row y lives at ywidth+x. Writing xwidth+y addresses the transposed cell: harmless-looking on square images, corrupting or overrunning everything else.

A linked list's nodes are separately allocated and scattered in memory, so there is no base address plus fixed stride to compute. Each node knows only where the next one lives, so reaching index k means following k links.

A dummy head is a permanent node placed before the first real element, so every real node has a predecessor. Deletion is always relink-the-predecessor, which means the first element needs no branch of its own.

Appending is O(n) when only a head reference is kept, because the last node is reachable only by walking the whole chain. Storing a tail reference alongside the head makes append O(1) in any of the three variants.

Walk two references, one hopping one node per step and one hopping two. If they meet, the list has a cycle; if the fast one runs off the end, it does not. A plain walk never reaches an end, so it spins forever.

A singly linked node stores only a forward link, so nothing inside it can change what points at it. Removal means rewriting the predecessor's link to skip the node, and locating that predecessor from the head costs O(n).

A deque supports push and pop at both ends, each constant time. Pushing and popping at the same end gives LIFO stack behavior; pushing at one end and popping at the other gives FIFO queue behavior.

Linked-node push is O(1) worst case: allocate a node and link it to the head. Array-backed push is O(1) amortized: usually one slot write, but a full buffer forces copying every element into a larger block.

Only when the outbound stack is empty. Pushing the inbound stack's contents onto a non-empty outbound stack puts newer arrivals above older ones and destroys first-in-first-out order. Standard implementations drain the inbound stack completely in that one transfer.

A queue hands nodes back in the order they were discovered, so every person at one depth is expanded before anyone a depth lower. A stack returns the most recent discovery first, which dives down a single reporting chain instead.

Removing the element at index 0 slides every remaining element one slot toward the front, so a single dequeue costs O(n). Draining a backlog of n items that way costs about n^2/2 moves in total.

A bloom filter's 'no' is certain: that item was never added. Its 'yes' means only 'probably present' — a fraction of queries for items that were never added still come back positive. Negatives are facts, positives are hints.

The hash map gives O(1) lookup from key to node but knows nothing about recency. The doubly linked list orders nodes by last use, so the eviction victim sits at a known end and unlinking it costs O(1).

An ordered map keeps its keys in sorted order, so it supports in-order iteration, range scans between two keys, and nearest-key lookups. You pay O(log n) on every insert, lookup and delete instead of a hash map's expected O(1).

Linear probing puts a colliding key in the next free slot, so lookup replays that walk: start at the home slot and step forward comparing keys, stopping only at an empty slot, never at the first non-matching key.

Both keys stay: the bucket holds a list, and the new entry is linked into that list. A lookup indexes the bucket in constant time, then walks the chain comparing full keys, so its cost grows with the chain's length.

The two hardcoded recursive calls become one loop over the children list, and the null-child check becomes an empty-children-list check. Every node is still visited exactly once, so a full traversal is still O(n).

A node's balance factor is its left subtree's height minus its right subtree's height. An AVL tree is valid when every node's factor is -1, 0 or +1 — a bound on heights, not on node counts.

Red-black rules — no red node has a red child, and every root-to-leaf path crosses equally many black nodes — cap height near 2·log n. That is bounded, not perfectly balanced: one branch may be twice as deep as another.

Depth counts edges from the root down to the node; height counts edges from the node down to its deepest descendant. Depth is fixed by where a node sits, while height depends on whatever hangs below it.

All three walk the left subtree before the right; only the position of the node's own visit moves — before both subtree walks (preorder), between them (inorder), or after both (postorder). All three are depth-first and all cost O(n).

Finding the minimum is O(1) — it sits at the root. Removing it costs O(log n): the last element is moved into the empty root slot and sifted down through the tree's height until the heap property holds again.

Bottom-up heapify turns an array of n items into a heap in O(n) time, while n successive inserts cost O(n log n) in the worst case. Same heap, lower cost, whenever every item is available up front.

A min-heap's array is not sorted. The property constrains only parent versus child, so every root-to-leaf path is non-decreasing while siblings may sit in any order. Only index 0 is guaranteed: it holds the minimum.

A priority queue supports three operations: insert an item with a priority, peek at the top-priority item, and extract that item. A FIFO queue hands back items in arrival order; a priority queue hands back the most urgent one first.

Give the queue a reversed comparison function, or push negated numeric keys. The reversed comparison is safer and self-documenting; negation works only for numeric keys and forces every read site to remember the flip.

A minimum spanning tree minimizes one global sum: the total weight of the edges keeping every node connected. It promises nothing about any specific pair, so its path between two nodes can cost more than a direct link.

An adjacency matrix reserves a cell for every pair of vertices, so its size depends only on V, never on the edge count. An adjacency list stores one entry per vertex plus one per actual edge, so it grows with E.

Each open cell is a node; an edge joins two cells one step apart, up, down, left or right. No edge list exists anywhere: a direction array plus a bounds-and-blocked check produces a cell's neighbors on demand.

After k passes over all edges, Bellman-Ford holds the best route that uses at most k edges. When no negative cycle exists, a best route never repeats a vertex, so it spans at most V-1 edges.

Dijkstra computes the minimum total travel time from one source to every reachable intersection - cheapest total weight, not fewest road segments. Vertices are finalized in non-decreasing distance order, so once one is popped its distance never changes.

Heapsort builds its max-heap inside the input array itself — nothing extra is allocated. The array splits into a heap prefix and a growing sorted suffix; each round swaps the root to the boundary and shrinks the heap by one.

Merge sort always halves the input until single-element runs remain, then merges back up. That gives about log2 n levels, and every level moves all n elements once, so the total is n log n whatever the input order.

Quicksort degrades to O(n^2) when every pivot splits off almost nothing — classically ordered input against a fixed first- or last-element pivot. Partitioning then peels one element per level, giving n levels of linear work instead of log n.

A bubble sort pass swaps out-of-order adjacent pairs, carrying the largest remaining value to the end. A selection sort pass scans the unsorted region for its minimum and places it with one swap.

Insertion sort's work is proportional to how far elements must move. Each element shifts past only the larger elements before it, so nearly-ordered input costs a few shifts per element; reversed input forces every element past every predecessor.

A lower bound search returns the first index whose element is greater than or equal to the target. For an absent key that index is exactly where the value would be inserted to keep the array sorted. It never reports failure.

A plain binary search returns the moment a midpoint matches, so which member of a run of equal keys comes back depends only on where the splits fell. The leftmost occurrence requires searching on after a hit.

Each comparison discards half of the remaining candidates, so the range shrinks n, n/2, n/4, down to one. The number of halvings needed to reach a single candidate is log2(n), so that many comparisons suffice.

Adding lo and hi can overflow a fixed-width signed integer once indices grow large, wrapping negative and yielding an out-of-range midpoint. Computing lo + (hi - lo) / 2 keeps every intermediate value inside the valid index range.

Linear search is O(n) because the bound is set by the worst case: a match in the last position, or no match at all, forces a scan of every element. Early exit improves lucky runs, not the growth rate.

Quicksort spends in the divide step: partitioning is a linear pass, and when the halves return there is nothing to combine. Merge sort splits by index in constant time and pays its linear pass when combining.

Divide-and-conquer splits a problem into two or more subproblems of the same kind on a fraction of the input, solves them independently, and combines their answers. A function that merely calls itself does none of that by default.

Subsets ask one yes/no question per item: n independent binary decisions, so 2^n outcomes. Orderings fill n positions from a shrinking pool: n choices, then n-1, then n-2, down to 1, which multiplies out to n!.

A cell is marked only to keep the path currently being built from reusing it. Once that branch returns, the cell is no longer on the path, so leaving it marked wrongly blocks every other path that needs to pass through it.

Testing only at the leaf still walks every branch to the bottom. Testing on entry deletes a whole subtree in one return: once the running total is over budget, more items can never bring it back down.

Every route into a cell takes its last step from either the cell above or the cell to its left. Those two sets of routes are disjoint and together cover every route, so the two counts simply add.

dp[i][w] is the best total value reachable using only the first i items within a capacity of w. The recurrence takes the larger of leaving item i out, dp[i-1][w], and taking it, value[i] + dp[i-1][w - weight[i]], when it fits.

dp[a] holds the fewest coins summing exactly to amount a: one plus the smallest dp[a - c] over each denomination c that fits. Amounts no combination reaches carry an infinity sentinel, never 0.

Greedy commits to a big slot before knowing what it blocks: taking a slot forbids both neighbours, so two merely good neighbours can outvalue one great slot. The take-or-skip recurrence best(i) = max(best(i-1), value(i) + best(i-2)) weighs both futures.

dp[i][j] is the edit distance between the first i characters of one name and the first j of the other — the indexes are prefix LENGTHS, not positions. Row 0 holds 0,1,2,...,j: turning nothing into a j-character prefix costs j insertions.

Prefix-free means no codeword is the beginning of another, so a decoder reading bits one at a time always knows exactly where a symbol ends. Without that property the same bit stream decodes several different ways.

Choosing the talk that finishes earliest leaves the largest possible remaining window for everything after it, and that rule is provably optimal. Shortest-duration is not: one short talk can straddle the seam between two longer talks and cost you a slot.

Reachability is monotone: standing on stone i makes every stone up to i + a[i] reachable too. So one pass keeping the maximum of i + a[i], abandoning the crossing as soon as the index passes that maximum, settles it in O(n).

An exchange argument starts from any optimal solution, finds the first point where it disagrees with greedy, and swaps greedy's choice in. The swap must stay feasible and no worse, so some optimal solution agrees with greedy.

Each nearest-stop pick is cheapest right now but reshapes what remains. Cheap early hops strand far-apart addresses for the end, so a chain of locally best moves need not add up to the best route.

Cyclic sort moves every value v to index v-1, so once placement finishes index i must hold i+1. The first index that breaks that rule names the absent value outright, with no extra lookup structure.

A singly linked chain has no backward pointers, so nothing can walk from the tail inward. The standard fix splits the chain at the middle, reverses the back half in place, then compares the two halves node by node.

Sorting by start guarantees any interval that could overlap the one being built arrives before the pass moves past it. In arrival order, an overlapping slot can appear after you already emitted an interval, so a single pass misses merges.

Two half-open intervals overlap exactly when a.start < b.end and b.start < a.end. That pair of strict comparisons is the negation of the only two ways intervals can miss each other: one finishing at or before the other begins.

A sweep line throws away the intervals and keeps only their boundaries: +1 at each login coordinate, -1 at each logout. Sort those events by coordinate, scan once with a running sum, and remember the largest sum seen.

Grant with OR: mask | FLAG. Revoke by ANDing the complement: mask & ~FLAG. Test membership with (mask & FLAG) != 0. XOR toggles rather than clears, so it is the wrong operator for revoke.

Two's complement gives the top bit a weight of -128, so the 256 patterns split into 128 negatives (-128 to -1) and 128 non-negatives. Zero uses one non-negative pattern, leaving only 127 positives — so -128 has no positive counterpart.

Use n = n & ~(1 << k). The shifted mask holds a single 1 at position k; inverting it gives all ones except there, so the AND forces that bit to 0 and leaves the rest unchanged.

The shift moves the field down to bit 0 so it reads as a number; the mask clears the neighbouring fields still sitting above it. Shift alone leaves garbage on top, mask alone leaves the value scaled.

Permutations count arrangements where order matters; combinations count selections where it does not. A ranked top-3 podium from 30 entrants gives 30 x 29 x 28 = 24,360 outcomes; an unordered shortlist of three gives only 4,060.

A usable plan names the constraints that actually bind (input size, memory ceiling, whether data can be re-read), the time and space class you are targeting, the concrete steps and the data you keep, and what you rejected and why.

A stated brute force proves you understood the problem, gives the interviewer a correct baseline to score, and becomes your fallback if the clever idea collapses. Silence while hunting for the optimal answer reads as being stuck.

Clarifying is the cheapest place to be wrong. A couple of minutes spent restating the task and asking about empty input, single elements, duplicates and negative values beats thirty minutes spent solving the wrong problem.

Compute the totals once and answer each query by lookup: q queries over n rows drop from O(q*n) to one O(n) pass plus O(1) per query. You pay extra memory, and staleness whenever the underlying rows change.

State each approach in a sentence or two, name the cost that separates them, say which one you would take and why, then ask the interviewer to confirm before you write a line of code.