Coding Interview Patterns

Read time and space cost straight off code, use the input limits to rule approaches in or out, and turn a new problem into a short list of candidate patterns before you write a line.

Solve pair, partition and palindrome problems in linear time by moving two indices under a rule that safely throws away whole groups of candidates.

Trade memory for speed: remember what you have already seen, so a lookup costs one step instead of a scan.

Pointer surgery on chains of nodes: reverse, merge, remove and rewire a list in place without ever losing the rest of it.

Two pointers that walk the same sequence at different speeds, which find cycles, cycle entrances and middles in one pass and O(1) extra space.

A running summary of a contiguous stretch that is repaired, not rebuilt, as the stretch moves, which turns "check every subarray" into one O(n) pass.

Throw away half of the candidates with every comparison — in sorted arrays, rotated arrays and ranges of possible answers — and write the loop without off-by-one bugs.

Hold unfinished work in the order you will finish it — matching brackets, evaluating expressions, and answering "next greater" questions in one pass with a monotonic stack.

Use a heap whenever you need the smallest or largest item of a collection that keeps changing — top K, k-way merge, scheduling and the running median — and know when a sort or quickselect is the simpler answer.

Sort a list of start–end pairs by the correct endpoint, then merge, insert, remove overlaps and count rooms in one sweep — and settle whether touching intervals overlap before you write a single comparison.

Precompute running totals once, so every question about a contiguous range becomes one subtraction — and, with a hash map, count or measure subarrays in a single pass.

Solve tree problems by deciding what each node hands back to its parent — then walk depth-first or level by level, in O(n) time, with the base cases and recursion limits under control.

Store words so that a prefix question costs the length of the prefix, not the size of the dictionary, and use that to build autocomplete, wildcard search and multi-word grid search — and know when a plain hash set is the better choice.

Model relations, grids and dependencies as graphs, and solve them with BFS, DFS, topological sort, Union-Find and Dijkstra — picking the right one from the shape of the problem.

Generate every subset, ordering and valid arrangement with one choose–explore–undo template, skip duplicate answers, and prune dead branches before they cost you.

Turn a slow recursion into a fast table: define the state, write the transition, then go from brute force to memoisation, tabulation and a space-saving loop on the problems interviewers ask most.

Commit to the locally best choice and never look back — and learn to prove that choice is safe, or break it with a small counter-example, before you write a line of code.

Use sorting as a tool — to make a hard question local, to define a custom order, to select one element without sorting everything, or to count out-of-order pairs during a merge — and know exactly what each sort costs.

Read numbers as rows of bits, and use AND, OR, XOR and shifts to cancel pairs, count and reverse bits, add without `+`, and list every subset — with the Python-specific care that unbounded integers need.

Solve the problems whose difficulty is an arithmetic or geometric fact — matrix index games, fast powers, primes, GCD and points on a line — while staying in exact integer arithmetic and avoiding overflow and floating-point traps.