DSA Interview Prep

State and defend a time and space bound before you write code. Amortised analysis, the difference between worst and expected case, and why "O(n log n) because I sort" is a complete answer.

Restating the problem, extracting the constraints, and choosing a brute force you can actually explain. Most failed interviews are lost in the first four minutes.

Empty input, one element, all-equal, integer overflow, and the boundary you always get wrong. A checklist you run before saying you are done.

Tracing your own solution against an example without executing it, which is the only debugging tool you have in an interview.

Opposite ends, same direction, and fast/slow. Recognising when a sorted input lets you drop a nested loop.

Fixed and variable windows, and the "shrink while invalid" loop shape that makes variable windows one template rather than ten problems.

Turning repeated range queries into O(1) lookups, and the prefix-sum-plus-hashmap trick behind subarray-sum problems.

Grouping, deduplication, and the seen-set. Where a hash map turns quadratic into linear and where it quietly does not.

When paying n log n up front collapses the rest of the problem, plus custom comparators and stability.

The template that does not go out of bounds, searching rotated arrays, and binary searching a monotonic predicate rather than an array.

Matching, evaluation, and the next-greater-element family. Recognising a monotonic stack from the phrase "next larger".

BFS queues, circular buffers, and the sliding-window-maximum deque.

Reversal, cycle detection, merge, and the dummy-head idiom that removes half the special cases.

When a heap beats a sort, k-th largest, merging k lists, and the two-heap running-median trick.

Recursive and iterative traversals, level order, and the "return something from each subtree" recursion shape.

The BST invariant, in-order as a sorted walk, insertion and deletion, and why a degenerate BST is a linked list.

Prefix trees for autocomplete and word search, and the space trade you are making against a hash set.

Disjoint sets with path compression and union by rank — the structure that turns connectivity questions into near-constant time.

Turning a grid, a word list or a dependency description into nodes and edges, and choosing a representation.

Shortest path in an unweighted graph, connected components, and the visited-set discipline that stops infinite loops.

Kahn's algorithm and DFS colouring, and reading "can this schedule be satisfied?" as a cycle question.

Dijkstra with a priority queue, Bellman-Ford when edges can be negative, and why Dijkstra breaks on them.

Kruskal on top of union-find, Prim on top of a heap, and the problems that are secretly asking for an MST.

Choose, explore, un-choose. Permutations, subsets, and combination sums, plus pruning that turns exponential into tractable.

Adding a cache to a recursive solution and reading the state you cached as the DP state. The bridge between recursion and DP.

Linear DP over an array: Fibonacci-shaped recurrences, longest increasing subsequence, and rolling the table down to O(1) space.

Grid paths, edit distance, and the two-sequence table. Drawing the table before writing the loop.

0/1 and unbounded knapsack, subset sum, coin change — one recurrence wearing four different problem statements.

Interval scheduling, jump games, and the exchange argument that separates a correct greedy from a plausible one.

Narrating your approach, stating trade-offs, and asking clarifying questions that are actually useful. Silence reads as being stuck.

Practising under a clock with someone watching. The single highest-yield activity in this roadmap, and the one most people skip.

Designing a parking lot, an elevator or a deck of cards: classes, responsibilities, and the interfaces you would actually implement.

STAR-structured stories with real numbers, and having four of them ready rather than inventing one under pressure.

Reading a compensation package, comparing offers honestly, and negotiating without burning the relationship.