Algorithms & Data Structures
All 13 cards in this deck
The core interview toolkit — complexity, the right structure for the job, and the patterns behind most problems. Answer each question before you open it — then run the review above, which schedules every card with spaced repetition so it comes back right before you would forget it.
Big-O: what does it actually measure?
How runtime (or space) grows as input size grows — the shape of the curve, not the wall-clock. O(n²) eventually loses to O(n log n) no matter the constants.
Array vs linked list — the core trade?
Array: O(1) random access, O(n) insert/delete in the middle (shifting). Linked list: O(1) insert/delete given the node, O(n) to find it. Access vs mutation.
When is a hash map the answer?
When you need O(1) average lookup/insert by key — dedup, counting, "have I seen this?", or turning an O(n²) nested scan into one pass with a seen-set.
Stack vs queue?
Stack = LIFO (DFS, undo, matching brackets, call frames). Queue = FIFO (BFS, task scheduling, buffering). The ordering discipline is the whole distinction.
Two-pointers — when does it apply?
On a sorted array or linked list, when a brute-force pair/triple scan is O(n²): move two indices inward/forward to hit O(n). Also fast/slow for cycle detection.
Sliding window — the signature?
Longest/shortest/best contiguous subarray or substring under a constraint. Grow the window, shrink when the constraint breaks — O(n) instead of O(n²) substrings.
BFS vs DFS for shortest path?
Unweighted graph: BFS — first arrival is the fewest edges. Weighted (non-negative): Dijkstra. DFS finds *a* path, not the shortest.
Binary search — the one precondition?
The data (or the answer space) must be monotonic/sorted, so you can discard half each step. O(log n). "Binary search on the answer" applies it to a predicate.
The dynamic-programming tell?
Overlapping subproblems + optimal substructure — the same smaller problem recurs. Memoize (top-down) or build a table (bottom-up) to avoid recomputation.
Greedy vs DP — when does greedy fail?
Greedy takes the local best and never looks back; it fails when a locally worse choice enables a better global one. DP explores those trade-offs.
Heap — what is it for?
A priority queue: O(log n) insert, O(1) peek-min/max. Top-k, merge k sorted lists, Dijkstra, streaming medians (two heaps).
Union-Find — the use case?
Tracking connected components / disjoint sets with near-O(1) union and find (path compression + union by rank). Cycle detection, Kruskal's MST, grouping.
Why is quicksort O(n²) worst case but preferred?
A bad pivot on already-sorted input degrades to O(n²); randomized/median-of-three pivots make that rare, and its cache-friendly in-place passes beat merge sort in practice.