Algorithms and Data Structures Glossary

A

Adjacency list and adjacency matrix

Category: data structures. Complexity: list uses O(V + E) space, matrix O(V²); edge lookup is O(degree) vs. O(1).

The two standard ways to store a graph. An adjacency list keeps, for each vertex, the list of its neighbours (a hash map of vertex to list, or an array of lists). An adjacency matrix is a V × V table with a 1 (or a weight) where an edge exists.

Use an adjacency list by default; it is compact for sparse graphs and iterates neighbours efficiently, which is what BFS and DFS need. Say so explicitly when the input is an edge list: "I will first build an adjacency list in O(V + E)". A matrix fits only dense graphs or when you need O(1) "is there an edge?" checks. See also "Graph".

Amortised analysis

Category: complexity.

Averaging the cost of an operation over a long sequence of operations, so that an occasionally expensive step is spread over the cheap ones. Appending to a dynamic array is O(1) amortised: most appends are O(1), and the occasional resize that copies all n elements happens rarely enough that the total for n appends is O(n). Union-find with path compression and the monotonic stack are other examples.

Say "amortised O(1)" rather than "O(1)" for dynamic array appends, hash table inserts and stack-based algorithms where each element is pushed and popped at most once. Amortised is not the same as average case: it is a guarantee over any sequence, not a probability. See also "Big-O notation".

Array (static and dynamic)

Category: data structures. Complexity: index access O(1); append O(1) amortised; insert or delete in the middle O(n); search O(n), or O(log n) if sorted.

A contiguous block of memory holding elements of the same size, accessed by index. A static array has a fixed length; a dynamic array (Python list, Java ArrayList, C++ vector, JavaScript array) grows by allocating a bigger block and copying when it fills up.

The default container. Know what is cheap (index, append, pop from the end, iteration) and what is not (insert or delete at the front or middle, searching unsorted data). When you need fast removal from the front, switch to a deque; when you need fast membership tests, add a hash set. Many "array" questions are really about sorting, two pointers, sliding windows, prefix sums or binary search. See also "Deque" and "Hash table".

A-star search

Category: graph algorithms. Complexity: depends on the heuristic; worst case exponential, in practice far fewer nodes than Dijkstra.

A shortest-path search that extends Dijkstra's algorithm with a heuristic estimate of the remaining distance to the goal (for example straight-line distance on a map). It expands the node with the lowest known cost plus estimate first. If the heuristic never overestimates, A-star finds the optimal path.

Rarely required, but worth naming when a question is about path finding on a map or a game grid with a single target. Dijkstra or BFS is the expected answer in most cases; A-star is the "and if we need it faster" follow-up.

B

Backtracking

Category: techniques. Complexity: exponential in general, e.g. O(n · 2ⁿ) for all subsets, O(n · n!) for all permutations; pruning decides how fast it is in practice.

Building a solution one choice at a time with depth-first recursion, and undoing (backtracking from) a choice as soon as it cannot lead to a valid answer. The template: choose, recurse, un-choose. Used to generate permutations, combinations, subsets, to solve N-queens and Sudoku, and for word search in a grid.

The expected approach when the question says "all", "generate", "every possible" or "count the ways" and the input is small (up to about 20 elements). Write the recursive helper with the current path and the start index, explain how duplicates are skipped (sort first, then skip equal neighbours) and where you prune. State the exponential complexity honestly. See also "Recursion" and "Bitmask DP".

Balanced binary search tree (AVL, red-black, treap)

Category: data structures. Complexity: search, insert and delete O(log n) guaranteed.

A binary search tree that rebalances itself after every insert and delete so that its height stays O(log n). AVL trees keep heights of sibling subtrees within one of each other; red-black trees use a looser rule with cheaper rebalancing and back Java's TreeMap and C++'s std::map; treaps and skip lists reach the same bounds with randomisation.

Nobody expects you to implement one; you are expected to know that your language's ordered map or set is one and gives O(log n) insert, delete, lookup, predecessor, successor and range queries. Reach for it when you need a sorted collection that changes, where a heap (no arbitrary deletion or search) or a sorted array (O(n) insert) is not enough. See also "Ordered map" and "Binary search tree".

Bellman-Ford algorithm

Category: graph algorithms. Complexity: O(V · E) time, O(V) space.

A single-source shortest-path algorithm that relaxes every edge V − 1 times. Unlike Dijkstra it handles negative edge weights, and a further round that still improves a distance proves a negative cycle. A variant with a limit on the number of rounds answers "cheapest path with at most k stops".

Name it when edge weights can be negative or when the path length is capped at k edges (cheapest flights within k stops). Otherwise Dijkstra is faster and expected. See also "Dijkstra's algorithm" and "Shortest path".

BFS (breadth-first search)

Category: graph algorithms. Complexity: O(V + E) time with an adjacency list; O(V) space for the queue and the visited set.

Exploring a graph level by level from a start node using a queue: visit the start, then all its neighbours, then their neighbours, marking nodes as visited when they are enqueued. In an unweighted graph the first time BFS reaches a node is along a shortest path, which is why BFS is the shortest-path algorithm when every edge costs the same.

The answer to "shortest path", "minimum number of steps" or "nearest" in an unweighted graph, grid or state space (word ladder, knight moves, open the lock). Write it with a queue and a visited set, process one level at a time when the distance matters, and mark visited on enqueue, not on dequeue, to avoid duplicates. Variants: multi-source BFS (start with all sources in the queue, e.g. rotting oranges), bidirectional BFS for large state spaces, and 0-1 BFS with a deque for edges of weight 0 or 1. See also "DFS" and "Queue".

Big-O notation (time and space complexity)

Category: complexity.

An upper bound on how the running time or memory of an algorithm grows with the input size n, ignoring constants and lower-order terms. The common classes, fastest to slowest: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic, O(n³), O(2ⁿ) exponential, O(n!) factorial. Big-Θ (tight bound) and big-Ω (lower bound) are the precise relatives; in interviews "big-O" is used loosely to mean the tight bound of the worst case.

State time and space complexity for every solution, before and after optimisation, and justify them ("one pass over n elements with O(1) work each, plus a hash map of up to n entries"). Know the complexity of your language's built-ins (sorting is O(n log n); list membership is O(n); string concatenation in a loop is O(n²)). Use the input size to guess the target: n up to 10⁵ usually means O(n log n) or better. See the "Complexity Cheat Sheet" below. See also "Amortised analysis".

Binary search

Category: searching. Complexity: O(log n) time, O(1) space.

Finding a value in a sorted array by repeatedly comparing with the middle element and discarding the half that cannot contain the target. Each step halves the search space, hence O(log n). The same idea works on any monotonic predicate: find the first index where a condition becomes true (lower bound) or the last where it is still false.

Use it whenever the data is sorted or the search space is monotonic. Write it carefully: choose a convention (lo and hi inclusive or half-open), compute mid as lo + (hi − lo) / 2 to avoid overflow in languages with fixed-size integers, and make sure the loop shrinks the range on every iteration. Know your library's bisect_left and bisect_right (Python), Collections.binarySearch (Java) and lower_bound (C++). Variants: first or last occurrence, rotated sorted array, search in a 2D sorted matrix, peak element. See also "Binary search on the answer".

Binary search on the answer

Category: techniques. Complexity: O(log(range) · cost of the check).

When the answer is a number in a known range and a check "is x achievable?" is monotonic (if x works, every larger or every smaller x works too), binary search over the candidate answers and run the check for each midpoint. Examples: the minimum capacity to ship packages in D days, the minimum eating speed to finish bananas in h hours, the smallest divisor, splitting an array to minimise the largest sum.

Recognise it from phrases like "minimise the maximum", "maximise the minimum" or "the smallest value such that". Say explicitly why the check is monotonic, state the bounds of the search range and the complexity of the check. It turns a hard optimisation question into a feasibility question. See also "Binary search".

Binary search tree (BST)

Category: data structures. Complexity: search, insert and delete O(h), where h is the height: O(log n) when balanced, O(n) when degenerate.

A binary tree in which every node's left subtree holds smaller keys and the right subtree larger keys. An inorder traversal visits the keys in sorted order. Without rebalancing, inserting sorted input produces a chain and all operations degrade to O(n).

Common questions: validate a BST (pass down the allowed min and max range, or check that inorder is strictly increasing), find the k-th smallest (inorder with a counter), lowest common ancestor in a BST (walk down comparing values), insert and delete (delete replaces with the inorder successor), convert a sorted array to a balanced BST (recursive middle element). Always state whether you assume the tree is balanced when giving O(log n). See also "Balanced binary search tree" and "Tree traversals".

Binary tree (full, complete, perfect, balanced)

Category: data structures.

A tree in which every node has at most two children, called left and right. Full: every node has 0 or 2 children. Complete: all levels are filled except possibly the last, which is filled from the left (the shape of a binary heap, which is why a heap fits in an array). Perfect: all levels completely filled, 2ʰ − 1 nodes. Balanced: the heights of the two subtrees of every node differ by at most one, so the height is O(log n).

Most tree questions are recursive: define what the function returns for a node in terms of its children (height, diameter, maximum path sum, whether it is balanced), handle the null base case, and state O(n) time and O(h) space for the recursion stack. Know the terms because questions use them ("given a complete binary tree, count the nodes in less than O(n)"). See also "Tree traversals" and "Recursion".

Bipartite graph (two-colouring)

Category: graph algorithms. Complexity: O(V + E).

A graph whose vertices can be split into two groups so that every edge connects the two groups; equivalently, a graph with no odd-length cycle. Checked by BFS or DFS, colouring each node the opposite colour of its parent and failing when an edge joins two nodes of the same colour.

Appears as "can the people be split into two groups given who dislikes whom" or "is the graph two-colourable". Run the colouring from every unvisited node, because the graph may be disconnected. See also "BFS" and "Graph".

Bit manipulation

Category: techniques. Complexity: O(1) per operation on fixed-width integers; O(number of bits) for loops over bits.

Operating directly on the binary representation of integers with AND, OR, XOR, NOT and shifts. Useful identities: x ^ x = 0 and x ^ 0 = x (so XOR of all elements cancels pairs and leaves the single one); x & (x − 1) clears the lowest set bit (counting set bits, checking for a power of two); x & −x isolates the lowest set bit; 1 << k is the k-th bit as a mask; checking, setting and clearing bit k with masks.

Expected for questions such as single number, counting bits, power of two, reverse bits, adding without the plus operator, and for representing subsets as bitmasks. Mention two's complement when negative numbers or arithmetic shifts come up, and the fixed width of integers in Java and C++ versus arbitrary precision in Python. See also "Bitmask DP".

Bitmask DP (subset DP)

Category: dynamic programming. Complexity: typically O(2ⁿ · n) or O(2ⁿ · n²) time and O(2ⁿ) or O(2ⁿ · n) space.

Dynamic programming in which the state includes a bitmask describing which of n items have been used, so there are 2ⁿ states. It solves problems over small sets exactly: travelling salesman on up to about 20 cities, assigning n tasks to n workers at minimum cost, counting ways to tile or match with constraints.

The signal is "n ≤ 20" (or so) together with a question about subsets or orderings that would be exponential anyway. Explain the state ("dp[mask][last] is the cheapest way to visit the cities in mask ending at last"), the transition (add one unused item) and iterate masks in increasing order so that smaller subsets are done first. See also "Dynamic programming" and "Bit manipulation".

Boyer-Moore majority vote

Category: array algorithms. Complexity: O(n) time, O(1) space.

Finding the element that appears more than n/2 times in one pass without extra memory: keep a candidate and a counter; when the counter is zero adopt the current element as candidate; increment on a match, decrement on a mismatch. The majority element, if one exists, survives. A second pass confirms it when existence is not guaranteed.

The O(1)-space follow-up to "find the majority element" after the obvious hash-map count. Explain why pairing off different elements cannot eliminate the majority. The generalisation finds elements appearing more than n/3 times with two candidates.

Brute force

Category: interview method.

The simplest correct solution, usually trying every possibility: all pairs, all subarrays, all subsets. It is often O(n²), O(n³) or exponential, and it is the starting point from which the optimised solution is derived by removing repeated work.

Always state the brute force and its complexity before optimising, even if you already see the clever solution; it shows you understand the problem and gives you something correct if the optimisation fails. Then ask "what work is repeated?" (a sorted order you could precompute, a sum you could keep as a window moves, a lookup you could do with a hash map, a subproblem you could memoize). See also "Space-time trade-off".

C

Call stack and recursion depth

Category: complexity.

Every function call takes a frame on the call stack until it returns. A recursive function that goes n levels deep uses O(n) stack space and, in most languages, crashes with a stack overflow after roughly 10,000 to 100,000 frames (Python's default limit is 1,000). The stack here is a region of memory, not the stack data structure, and the "heap" where objects live is not the heap data structure either.

Count the recursion depth in your space complexity ("O(h) for the recursion stack, O(n) in the worst case for a skewed tree"). When depth could be large (DFS over a 10⁶-node graph, a linked list of 10⁵ nodes), say you would convert the recursion to iteration with an explicit stack. See also "Recursion" and "DFS".

Coin change

Category: dynamic programming. Complexity: O(n · amount) time, O(amount) space.

Two classic DP problems. Minimum coins to make an amount: dp[a] = 1 + min over coins c of dp[a − c]. Number of ways to make an amount: dp[a] += dp[a − c], iterating coins in the outer loop so that each combination is counted once regardless of order. Both are forms of the unbounded knapsack.

Know both versions and why the loop order differs between "combinations" (coins outside) and "permutations" (amount outside). Greedy by largest coin fails for general coin systems (coins 1, 3, 4 and amount 6), which is the standard reason to reach for DP here. See also "Knapsack problem" and "Dynamic programming".

Combinatorics basics (permutations, combinations)

Category: mathematics.

Counting arrangements. Permutations of n items: n!; of k out of n in order: n!/(n − k)!. Combinations (choosing k out of n without order): C(n, k) = n!/(k!(n − k)!), with Pascal's rule C(n, k) = C(n − 1, k − 1) + C(n − 1, k). Subsets of n items: 2ⁿ. Factorials overflow 64-bit integers after 20!, so counts are usually asked modulo 10⁹ + 7.

Needed to state complexities of backtracking, to count paths in a grid (C(m + n − 2, m − 1)) and in questions about probability or arrangements. Compute C(n, k) with Pascal's triangle DP or multiplicatively, never with raw factorials. See also "Backtracking" and "Modular arithmetic".

Connected components

Category: graph algorithms. Complexity: O(V + E) with BFS or DFS; near O(V + E) with union-find.

The groups of vertices that are reachable from each other in an undirected graph. Found by running DFS or BFS from every unvisited vertex and counting the starts, or by union-find over the edges and counting the distinct roots.

Behind "number of islands", "number of provinces", "friend circles" and "can all nodes be reached". Choose DFS/BFS when the graph is given up front, union-find when edges arrive one by one and you must answer "how many groups now?" after each. See also "Union-find" and "Grid traversal".

Constant time (O(1))

Category: complexity.

An operation whose cost does not depend on the input size: indexing an array, pushing to a stack, inserting into or looking up a hash map (on average), reading the top of a heap, arithmetic on fixed-width integers. "O(1) extra space" means the memory used beyond the input is constant.

The target for per-operation costs in design questions (LRU cache, min stack, insert-delete-getRandom) and the reason hash maps appear everywhere. Be precise: hash map operations are O(1) on average and amortised, not in the worst case; appending to a dynamic array is O(1) amortised. See also "Big-O notation" and "Amortised analysis".

Counting sort, radix sort and bucket sort

Category: sorting. Complexity: counting sort O(n + k) for keys in a range of size k; radix sort O(d · (n + b)) for d digits in base b; bucket sort O(n) average for uniformly spread data.

Sorts that do not compare elements and so can beat the O(n log n) lower bound of comparison sorting when the keys are small integers, fixed-length strings or evenly spread values. Counting sort tallies occurrences of each key; radix sort applies a stable counting sort digit by digit; bucket sort scatters values into ranges and sorts each range.

Use counting sort when values are bounded (ages, letters, 0/1/2 colours); use bucket sort for "top k frequent elements" in O(n) by bucketing on frequency. Mention them when an interviewer asks whether you can beat O(n log n). See also "Sorting algorithms".

Cycle detection (graphs)

Category: graph algorithms. Complexity: O(V + E).

In an undirected graph, DFS finds a cycle when it meets a visited vertex that is not the parent of the current one; union-find finds it when an edge joins two vertices already in the same set. In a directed graph, DFS with three colours (unvisited, in progress, done) finds a cycle when it reaches an in-progress vertex; alternatively, Kahn's topological sort leaves vertices unprocessed if there is a cycle.

The core of "course schedule" (can all prerequisites be satisfied), deadlock detection and "redundant connection". Say which graph type you have, because the undirected trick (parent check) is wrong for directed graphs. See also "Topological sort" and "Fast and slow pointers" for cycles in linked lists.

Cyclic sort

Category: array algorithms. Complexity: O(n) time, O(1) space.

A pattern for arrays containing numbers in the range 1 to n (or 0 to n − 1): place each number at its own index by swapping until every position holds the right value, then scan for positions that are wrong. It finds missing, duplicate or misplaced numbers in O(n) without extra memory.

The intended O(1)-space solution for "find the missing number", "find all duplicates", "first missing positive" and similar questions when the values are bounded by the array length. Mention the alternative of marking visited indices by negating values. See also "In-place algorithms".

D

Deque (double-ended queue)

Category: data structures. Complexity: push and pop at either end O(1); index access O(1) in array-based implementations.

A queue that allows insertion and removal at both the front and the back: Python's collections.deque, Java's ArrayDeque, C++'s std::deque. It serves as a queue (BFS), a stack, and the basis of the sliding window maximum.

Use it for every queue you write (Python lists are O(n) for pop from the front), and for the monotonic deque pattern. See also "Queue" and "Monotonic deque".

DFS (depth-first search)

Category: graph algorithms. Complexity: O(V + E) time; O(V) space for the visited set and the stack.

Exploring a graph by going as deep as possible along each branch before backtracking, implemented with recursion or an explicit stack and a visited set. It finds connected components, detects cycles, produces topological orders, and underlies backtracking and most tree algorithms.

Choose DFS for exhaustive exploration, path existence, component counting, cycle detection and anything on trees; choose BFS when you need the shortest path or the level structure. Write the visited check before recursing, and say how deep the recursion can go. On a grid, DFS from each unvisited land cell is the standard "number of islands" solution. See also "BFS", "Backtracking" and "Call stack and recursion depth".

Dijkstra's algorithm

Category: graph algorithms. Complexity: O((V + E) log V) with a binary heap; O(V²) with an array for dense graphs.

Single-source shortest paths in a graph with non-negative edge weights. Keep a min-heap of (distance, vertex); repeatedly pop the closest unfinalised vertex and relax its edges, pushing improved distances. A popped entry whose distance is worse than the recorded one is skipped (lazy deletion). It fails with negative edges.

The expected answer for weighted shortest paths: network delay time, cheapest path with weights, minimum effort path (where the "distance" is the maximum edge on the path). Explain the heap, the relaxation step and why a vertex is final when popped. For negative weights name Bellman-Ford; for unweighted graphs say BFS is enough. See also "Shortest path" and "Heap".

Directed acyclic graph (DAG)

Category: data structures.

A directed graph with no cycles. Its vertices can be ordered so that every edge points forward (a topological order), which makes dependency problems, scheduling and many DP-on-graph problems tractable. Trees are DAGs; prerequisite graphs and build dependencies are typical DAGs.

Say "this is a DAG" when the problem has dependencies, then propose topological sort and DP over the order (longest path in a DAG, number of paths, earliest completion time). Longest-path questions that are NP-hard on general graphs are linear on a DAG. See also "Topological sort".

Divide and conquer

Category: techniques. Complexity: given by a recurrence, e.g. T(n) = 2T(n/2) + O(n) = O(n log n).

Splitting a problem into independent subproblems of the same kind, solving them recursively and combining the results: merge sort, quicksort, binary search, counting inversions, the closest pair of points, Strassen's matrix multiplication, and "construct a tree from traversals".

Name it when the subproblems do not overlap (if they do, you want dynamic programming instead). Write the recurrence and solve it with the master theorem to get the complexity. See also "Master theorem", "Merge sort" and "Dynamic programming".

Dutch national flag (three-way partition)

Category: array algorithms. Complexity: O(n) time, O(1) space.

Rearranging an array into three groups in one pass with three pointers: low, mid and high. Elements smaller than the pivot go to the front, larger to the back, equal ones stay in the middle. Named after the three bands of the Dutch flag.

The one-pass answer to "sort colours" (0s, 1s and 2s) and the partition step that makes quicksort efficient with many duplicate keys. Explain the invariant of each pointer. See also "Quicksort" and "Invariants".

Dynamic programming (DP)

Category: dynamic programming. Complexity: number of states × cost of a transition.

Solving a problem by breaking it into overlapping subproblems, solving each once and storing the result. It applies when the problem has optimal substructure (the best answer is built from the best answers to subproblems) and overlapping subproblems (the same subproblem is needed many times). Two styles: top-down memoization (recursion plus a cache) and bottom-up tabulation (fill a table in dependency order). Common shapes: 1D over a sequence (climbing stairs, house robber, maximum subarray), 2D over two sequences or a grid (LCS, edit distance, unique paths), knapsack over items and capacity, interval DP over ranges (burst balloons, matrix chain), state-machine DP (buying and selling stock with cooldown), tree DP, bitmask DP.

Recognise it from "minimum", "maximum", "number of ways", "longest", "is it possible" over choices that build on each other. Then do four things out loud: define the state precisely in words, write the transition, give the base cases, and state the order of evaluation and the complexity. Start top-down if it is easier to see, then convert to bottom-up and compress space (rolling arrays) if asked. See also "Memoization vs. tabulation", "Knapsack problem" and "Bitmask DP".

E

Edge cases

Category: interview method.

Inputs at the boundaries of the problem where naive code breaks: empty input, one element, all elements equal, already sorted or reverse sorted, negative numbers and zero, the maximum size, duplicates, a single node or a null tree, a disconnected graph, a cycle, Unicode or empty strings, integer overflow.

Ask about them while clarifying ("can the array be empty? can values repeat?"), then test your code against two or three of them at the end by tracing it by hand. Handling the empty case first in the code is cheap insurance. See also "Integer overflow and floating-point pitfalls".

Edit distance (Levenshtein distance)

Category: dynamic programming. Complexity: O(m · n) time; O(min(m, n)) space with a rolling row.

The minimum number of single-character insertions, deletions and substitutions that turn one string into another. dp[i][j] is the distance between the first i characters of one string and the first j of the other: equal last characters cost nothing, otherwise 1 plus the best of the three operations.

The model for 2D string DP; one-edit-distance, spell checking and "delete operations for two strings" are variants. Draw the table for two short words, write the recurrence, and mention space compression. See also "Longest common subsequence" and "Dynamic programming".

Euclidean algorithm (GCD)

Category: mathematics. Complexity: O(log(min(a, b))).

Computing the greatest common divisor by repeated remainders: gcd(a, b) = gcd(b, a mod b) until b is 0. The least common multiple is a · b / gcd(a, b). The extended version also finds integers x and y with a·x + b·y = gcd(a, b), which gives modular inverses.

Needed for fraction simplification, "can the water jugs measure z litres" (possible when z is a multiple of the gcd and no more than the total), array rotations and some gcd-of-array questions. Write the iterative version; it is three lines. See also "Modular arithmetic".

Eulerian path (Hierholzer's algorithm)

Category: graph algorithms. Complexity: O(E).

A path that uses every edge exactly once (an Eulerian circuit if it returns to the start). It exists in a connected graph when zero or two vertices have odd degree (undirected) or when in-degrees and out-degrees match with at most one start and one end exception (directed). Hierholzer's algorithm finds it by DFS, appending each vertex to the answer when all its edges are used, then reversing.

Behind "reconstruct itinerary" (use all tickets, lexicographically smallest route) and "valid arrangement of pairs". Rare, but when it appears nothing else works. See also "DFS".

Exponential and factorial time (O(2ⁿ), O(n!))

Category: complexity.

Costs that double, or worse, with each extra input element: enumerating all subsets (2ⁿ), all permutations (n!), naive recursive Fibonacci (about 1.6ⁿ), bitmask DP (2ⁿ · n). Feasible only for small n: about 20 to 25 for 2ⁿ, about 10 to 12 for n!.

If your solution is exponential, say so and say why it is unavoidable (the output itself is exponential, or the problem is NP-hard) or how you would cut it down (memoization, pruning, a different state). An exponential recursion with repeated subproblems is the classic sign that dynamic programming is intended. See also "Backtracking", "Bitmask DP" and "NP-completeness".

Exponentiation by squaring (fast power)

Category: mathematics. Complexity: O(log n) multiplications.

Computing xⁿ by squaring: xⁿ = (x²)^(n/2) for even n and x · xⁿ⁻¹ for odd n, so the exponent halves each step. Works for any associative operation, including matrix multiplication, which gives the n-th Fibonacci number in O(log n) via matrix exponentiation.

The expected answer to "implement pow(x, n)" (handle negative n and the overflow of −n in fixed-width integers) and to "count ways" problems with a huge n and a fixed-size recurrence. Combine with a modulus to keep numbers small. See also "Modular arithmetic".

F

Fast and slow pointers (Floyd's cycle detection)

Category: linked list algorithms. Complexity: O(n) time, O(1) space.

Two pointers that move through a linked list (or a sequence defined by a function) at different speeds, typically one step and two steps at a time. If there is a cycle the fast pointer laps the slow one and they meet; the middle of a list is where the slow pointer is when the fast one reaches the end. After a meeting inside a cycle, moving one pointer back to the head and advancing both one step at a time finds the cycle's start.

The O(1)-space answer to linked list cycle, cycle start, middle of the list, palindrome linked list (find the middle, reverse the second half), happy number, and "find the duplicate number" treated as a linked list over indices. Explain why the pointers must meet. See also "Linked list" and "Two pointers".

Fenwick tree (binary indexed tree)

Category: data structures. Complexity: prefix sum query and point update O(log n); O(n) space; build O(n log n) naively or O(n) with a linear pass.

An array-based structure that keeps prefix sums under point updates. Each index covers a range determined by its lowest set bit, so a query or an update touches O(log n) entries by repeatedly adding or clearing that bit. Smaller and simpler to code than a segment tree, but limited to invertible operations such as sums and counts.

Use it for "count of smaller numbers after self", range sum with updates, and counting inversions with coordinate compression. If the operation is min or max, or the updates are over ranges, use a segment tree instead. See also "Segment tree" and "Prefix sum".

Fisher-Yates shuffle

Category: randomised algorithms. Complexity: O(n) time, O(1) extra space.

Producing a uniformly random permutation in place: for i from n − 1 down to 1, swap element i with a random element at an index from 0 to i inclusive. Every permutation is equally likely, which naive "swap each element with any random index" does not achieve.

The answer to "shuffle an array" and the base of "random pick" questions; explain why the random index must include i itself and why each of the n! permutations gets probability 1/n!. See also "Reservoir sampling".

Floyd-Warshall algorithm

Category: graph algorithms. Complexity: O(V³) time, O(V²) space.

All-pairs shortest paths by dynamic programming over intermediate vertices: for each k, for each pair (i, j), dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Handles negative edges (not negative cycles, which it can detect via a negative diagonal) and is a few lines long.

Use it when the graph is small (up to a few hundred vertices) and you need distances between many pairs, for example "find the city with the fewest reachable neighbours within a threshold". For a single source, Dijkstra or Bellman-Ford is cheaper. See also "Shortest path".

G

Graph

Category: data structures.

A set of vertices (nodes) connected by edges, which may be directed or undirected and weighted or unweighted. A tree is a connected graph with no cycles and exactly V − 1 edges. Graphs arrive as edge lists, adjacency lists, adjacency matrices, grids (each cell a vertex, neighbours by direction) or implicitly as states with moves (a word and its one-letter changes, a lock and its turns).

Many questions are graphs in disguise: dependencies, friendships, flights, grids, state transitions. Say "I will model this as a graph where the nodes are ... and the edges are ...", choose the representation, then pick the algorithm by the question: reachability or components (DFS/BFS/union-find), shortest unweighted path (BFS), shortest weighted path (Dijkstra), ordering (topological sort), cheapest connection of everything (MST). See also "Adjacency list and adjacency matrix" and "Directed acyclic graph".

Greedy algorithms

Category: techniques. Complexity: usually O(n log n) because of a sort, or O(n).

Making the locally best choice at each step and never revisiting it. Correct only when the problem has the greedy-choice property, which is usually argued with an exchange argument (any optimal solution can be transformed into the greedy one without getting worse). Classic cases: interval scheduling by earliest end time, jump game, assigning cookies, fractional knapsack, Huffman coding, Dijkstra, Kruskal and Prim.

Greedy is tempting and often wrong; when you propose it, give the reason it works or a quick counter-example search. If the interviewer's question allows choices with lasting consequences ("number of ways", 0/1 items), it is probably DP instead. Sorting the input first is the usual enabler. See also "Dynamic programming" and "Interval problems".

Grid traversal (flood fill)

Category: graph algorithms. Complexity: O(rows · cols) time and space.

Treating a 2D grid as a graph where each cell connects to its four (or eight) neighbours, and running BFS or DFS from a cell to visit the region it belongs to: flood fill, number of islands, max area of island, surrounded regions, shortest path in a binary matrix. Boundary checks and a visited marker (often overwriting the cell itself) are the main details.

Write a direction array of (dr, dc) pairs and a helper that checks bounds, then BFS or DFS. Use BFS when the shortest distance is asked, multi-source BFS when distance from the nearest of many sources is asked (walls and gates, rotting oranges), and DFS or union-find for components. See also "BFS", "DFS" and "Connected components".

H

Hash table (hash map, hash set)

Category: data structures. Complexity: insert, lookup and delete O(1) average and amortised, O(n) worst case; O(n) space.

A structure that stores key-value pairs (map) or keys (set) in an array indexed by a hash of the key, giving constant-time operations on average. Collisions are handled by chaining (a list per bucket) or open addressing (probing for the next free slot); the table resizes when its load factor grows. Keys must be hashable and immutable (a tuple, not a list, in Python). Python dict and set, Java HashMap and HashSet, C++ unordered_map and unordered_set, JavaScript Map and Set. Iteration order is not sorted (Python keeps insertion order; Java's HashMap does not).

The most common optimisation tool: it turns an O(n) search into O(1), so an O(n²) pair search becomes O(n). Frequency counts, two-sum complements, grouping anagrams by a sorted key, visited sets in graph search, memoization caches, and index lookups all use it. Say "hash map" when you use one and mention the average-case caveat once. When you need sorted order or range queries, use an ordered map instead. See also "Two-sum pattern", "Set" and "Ordered map".

Heap (priority queue)

Category: data structures. Complexity: push and pop O(log n); peek at the minimum or maximum O(1); build from n elements O(n); O(n) space.

A complete binary tree stored in an array (children of index i at 2i + 1 and 2i + 2) in which every parent is smaller (min-heap) or larger (max-heap) than its children, so the extreme element is always at the root. It does not keep elements sorted and does not support search or arbitrary deletion efficiently (lazy deletion is the workaround). Python's heapq is a min-heap (negate values for a max-heap), Java's PriorityQueue and C++'s priority_queue accept comparators.

Reach for it when you repeatedly need the smallest or largest of a changing collection: top-k elements, k-th largest, merge k sorted lists, task scheduling, Dijkstra, the running median (two heaps), meeting rooms (min-heap of end times). A heap of size k gives O(n log k) for top-k, better than sorting everything. See also "Top-K elements", "K-way merge" and "Two heaps".

I

In-place algorithms

Category: complexity.

Algorithms that transform the input using only O(1) (or sometimes O(log n)) extra memory, writing the result into the input itself: reversing an array, rotating a matrix, removing duplicates from a sorted array, quicksort, heapsort, cyclic sort. "In place" is about extra space, not about whether the input is modified; a recursive in-place algorithm still uses stack space.

When a question says "in place" or "O(1) extra space", the trick is usually one of: two pointers (read and write indices), swapping, encoding extra information in the existing values (negation, bit packing), or reusing the input as the visited marker. Confirm whether modifying the input is allowed. See also "Two pointers" and "Cyclic sort".

Integer overflow and floating-point pitfalls

Category: mathematics.

Fixed-width integers wrap around: a 32-bit signed int holds up to 2³¹ − 1 (about 2.1 × 10⁹), a 64-bit long up to 2⁶³ − 1 (about 9.2 × 10¹⁸). Products of two large ints, sums over large arrays, factorials beyond 20! and mid = (lo + hi) / 2 can overflow in Java, C++ and JavaScript's bitwise operations; Python integers grow without limit. Floating-point numbers cannot represent most decimals exactly, so equality checks on them fail; compare with a tolerance or work in integers (cents, not złoty).

Say which integer width you assume, use lo + (hi − lo) / 2 in binary search, take results modulo 10⁹ + 7 when the question asks, and reach for 64-bit types for sums and products. Reverse-integer and atoi questions are explicitly about overflow checks. See also "Modular arithmetic".

Interval problems (merge intervals, sweep line)

Category: techniques. Complexity: O(n log n) because of the sort.

Questions about ranges on a line: merge overlapping intervals, insert an interval, meeting rooms (can one person attend all, or how many rooms are needed), the maximum number of overlapping intervals, non-overlapping intervals to remove, employee free time. The standard move is to sort by start, then sweep left to right while keeping the current merged interval or a min-heap of end times. The sweep line generalises it: turn each interval into +1 at its start and −1 at its end, sort the events, and keep a running count.

Sort first, then state what you keep while sweeping. Be explicit about whether touching intervals ([1, 3] and [3, 5]) overlap, and about processing ends before starts at the same coordinate. See also "Greedy algorithms" and "Heap".

Invariants

Category: interview method.

A condition that stays true at every step of an algorithm, such as "everything left of the write pointer is the final answer so far", "the stack holds indices with decreasing values" or "the target, if present, is in [lo, hi]". Invariants are how you convince yourself and the interviewer that a loop is correct, and how you decide the loop's update and termination.

When writing two-pointer, binary search, sliding window or partition code, say the invariant out loud; it prevents the classic off-by-one errors and lets you fix a bug by reasoning rather than by guessing. See also "Binary search" and "Dutch national flag".

K

Kadane's algorithm (maximum subarray)

Category: dynamic programming. Complexity: O(n) time, O(1) space.

Finding the contiguous subarray with the largest sum in one pass: at each position keep the best sum ending here (either extend the previous best or start fresh at the current element) and the best seen overall. It is a one-dimensional DP with the state compressed to one variable.

The reference answer for maximum subarray and the base for maximum product subarray (track both max and min because of negatives), circular subarray (total minus minimum subarray) and "best time to buy and sell stock" (maximum subarray of daily differences). State that it handles all-negative arrays by returning the largest element. See also "Dynamic programming" and "Prefix sum".

KMP algorithm (string matching)

Category: string algorithms. Complexity: O(n + m) time for a text of length n and pattern of length m; O(m) space.

Finding a pattern in a text without re-scanning: a precomputed failure (prefix) table says, for each prefix of the pattern, the length of its longest proper prefix that is also a suffix, so that on a mismatch the pattern shifts as far as possible without missing a match. Naive matching is O(n · m).

Say "KMP or Rabin-Karp" when asked to implement string search in better than O(n · m), and know that library functions (find, indexOf) are the practical answer. The failure table alone solves "shortest palindrome" and "repeated substring pattern". See also "Rabin-Karp" and "Strings".

Knapsack problem

Category: dynamic programming. Complexity: O(n · W) time for n items and capacity W (pseudo-polynomial); O(W) space with a 1D array.

Choosing items with weights and values to maximise value within a capacity. The 0/1 version (each item once) uses dp[w] = max(dp[w], dp[w − weight] + value), iterating capacities downwards so each item is used at most once; the unbounded version iterates upwards. Subset sum, partition into equal subsets, target sum and coin change are the same DP with different questions.

Recognise it from "choose a subset under a limit to maximise or to reach a target". Explain the loop direction (down for 0/1, up for unbounded); it is the detail interviewers check. The complexity depends on the numeric capacity, so it is exponential in the number of bits of W, which is why the general problem is NP-hard yet solvable here. See also "Coin change" and "Dynamic programming".

K-way merge

Category: techniques. Complexity: O(N log k) for N total elements across k sorted inputs.

Merging k sorted lists by keeping one element from each in a min-heap: pop the smallest, append it to the output, push the next element from the same list. Also solved by repeatedly merging pairs (divide and conquer), with the same complexity.

The approach for "merge k sorted lists", "smallest range covering elements from k lists", "k-th smallest in a sorted matrix" and "find k pairs with smallest sums". Say what tuple goes into the heap (value, list index, position) and why the heap holds only k entries. See also "Heap" and "Merge sort".

L

Linear time (O(n))

Category: complexity.

Work proportional to the input size: one or a constant number of passes over the data. Scanning for a maximum, building a hash map, two pointers, sliding window, prefix sums, Kadane, BFS and DFS (O(V + E)), counting sort, building a heap.

The usual best possible for problems that must read all the input, and the follow-up target after an O(n log n) solution ("can you avoid the sort?"). When you claim O(n), make sure no step hides an inner loop: string concatenation, list membership tests and slicing inside a loop are common culprits. See also "Big-O notation" and "Sliding window".

Linked list

Category: data structures. Complexity: access by index O(n); insert or delete at a known node O(1); O(n) space with per-node overhead.

A chain of nodes each holding a value and a pointer to the next (singly linked) or to both neighbours (doubly linked). Insertions and deletions in the middle are O(1) once you hold the node, which arrays cannot do, but there is no random access and poor cache behaviour. Questions usually involve pointer manipulation with a few variables.

Use a dummy head node to avoid special cases at the front, draw the pointers before coding, and rehearse the standard moves: reverse a list (iteratively, three pointers), reverse in groups, merge two sorted lists, remove the n-th from the end (two pointers n apart), detect and locate a cycle, find the middle, reorder, add two numbers, copy a list with random pointers (hash map or interleaving). See also "Fast and slow pointers" and "LRU cache".

Logarithmic time (O(log n))

Category: complexity.

Work that grows by a constant when the input doubles, because each step discards a constant fraction of what remains: binary search, operations on balanced BSTs and heaps, Fenwick and segment tree queries, exponentiation by squaring, the height of a balanced tree. For n = 10⁶, log₂ n is about 20.

When a question demands better than linear time per query, the answer almost always involves halving: binary search on sorted data or on the answer, or a tree-shaped structure. The base of the logarithm does not matter inside big-O. See also "Binary search" and "Heap".

Log-linear time (O(n log n))

Category: complexity.

Linear work repeated a logarithmic number of times, or logarithmic work done n times: comparison sorting, n heap operations, n binary searches, merge sort's recursion tree, Dijkstra on a sparse graph. Only slightly slower than linear in practice (about 20 times for n = 10⁶).

The default achievable target for n up to about 10⁶. A solution that sorts and then does linear work is O(n log n); say so and name the sort as the dominant step. See also "Sorting algorithms" and "Big-O notation".

Longest common subsequence (LCS)

Category: dynamic programming. Complexity: O(m · n) time; O(min(m, n)) space with rolling rows.

The longest sequence of characters that appears in both strings in order, not necessarily contiguously. dp[i][j] is the LCS length of the first i and first j characters: 1 + dp[i − 1][j − 1] when the characters match, otherwise max(dp[i − 1][j], dp[i][j − 1]).

The template for two-sequence DP: edit distance, shortest common supersequence, "delete to make equal", diff tools. Distinguish it from the longest common substring, which must be contiguous and resets to zero on a mismatch. See also "Edit distance" and "Subarray, subsequence and subset".

Longest increasing subsequence (LIS)

Category: dynamic programming. Complexity: O(n²) with plain DP; O(n log n) with patience sorting and binary search.

The longest subsequence whose elements strictly increase. The O(n²) DP sets dp[i] to the best LIS ending at i. The O(n log n) method keeps an array where tails[k] is the smallest possible tail of an increasing subsequence of length k + 1; each element replaces the first tail that is not smaller (binary search) or extends the array. The length is the array's length (the array itself is not the subsequence).

Give the O(n²) DP first, then the n log n refinement if asked. It underlies "Russian doll envelopes" (sort by width ascending and height descending, then LIS on heights) and "maximum number of non-overlapping chains". See also "Binary search" and "Dynamic programming".

Lowest common ancestor (LCA)

Category: tree algorithms. Complexity: O(n) per query with a simple DFS; O(log n) per query after O(n log n) preprocessing with binary lifting.

The deepest node that is an ancestor of two given nodes in a tree. In a binary tree, recurse: if the current node is null or one of the targets return it; if both subtrees return non-null, the current node is the LCA; otherwise return the non-null side. In a BST, walk down from the root: both targets smaller go left, both larger go right, otherwise stop. With parent pointers, it reduces to the intersection of two linked lists.

A standard medium question with several variants (BST, parent pointers, nodes possibly missing, many queries). Know the recursive version cold and mention binary lifting only if many queries are asked. See also "Tree traversals" and "Binary search tree".

LRU cache

Category: data structures. Complexity: get and put O(1); O(capacity) space.

A cache of fixed capacity that evicts the least recently used entry. Implemented with a hash map from key to node plus a doubly linked list ordered by recency: a lookup moves the node to the front, an insert adds at the front and evicts from the back. Python's OrderedDict and Java's LinkedHashMap (with access order) give it almost for free.

One of the most common design questions. Explain why both structures are needed (the map for O(1) lookup, the list for O(1) reordering and eviction), use dummy head and tail nodes, and know the LFU follow-up (frequency buckets, each an ordered list, plus a minimum-frequency pointer). See also "Hash table" and "Linked list".

M

Master theorem

Category: complexity.

A rule for solving recurrences of the form T(n) = a · T(n/b) + O(nᵈ), which describe divide-and-conquer algorithms. Compare d with log_b a: if d is larger, T(n) = O(nᵈ); if equal, O(nᵈ log n); if smaller, O(n^(log_b a)). Examples: merge sort (a = 2, b = 2, d = 1) is O(n log n); binary search (a = 1, b = 2, d = 0) is O(log n); the naive "count nodes" of a complete tree by recursing into both halves (a = 2, b = 2, d = 0) is O(n).

Use it to justify the complexity of any recursive solution that splits the input; for recurrences such as T(n) = T(n − 1) + O(n) (which is O(n²)) or T(n) = 2T(n − 1) (which is O(2ⁿ)), reason directly instead. See also "Divide and conquer".

Matrix problems (rotation, spiral, search)

Category: techniques. Complexity: O(rows · cols) for traversals; O(rows + cols) for search in a row- and column-sorted matrix.

Questions on 2D arrays that are about index arithmetic rather than graphs: rotate an image by 90 degrees in place (transpose, then reverse each row), spiral order (shrink four boundaries), set matrix zeroes in O(1) space (use the first row and column as markers), search a sorted matrix (binary search on the flattened index, or start at the top-right corner and move left or down), diagonal traversal, and 2D prefix sums for submatrix sums.

Write boundary conditions carefully and trace a 3 × 3 example. For a matrix where rows and columns are each sorted, the "staircase" search from a corner is the expected O(m + n) answer. See also "Prefix sum" and "Grid traversal".

Memoization vs. tabulation

Category: dynamic programming.

Two ways to implement dynamic programming. Memoization is top-down: write the natural recursion and cache each result (a hash map or array; functools.lru_cache in Python), so each subproblem is computed once. Tabulation is bottom-up: fill a table from the base cases up in an order that guarantees dependencies are ready, with no recursion. Memoization only computes the subproblems that are needed and is easier to derive; tabulation avoids stack overflow and allows space compression to the last row or two.

Derive the recursion first, add memoization, then convert to tabulation if the interviewer asks for iterative code or less memory. Say the complexity is the same for both: number of states times transition cost. See also "Dynamic programming" and "Call stack and recursion depth".

Merge sort

Category: sorting. Complexity: O(n log n) time in all cases; O(n) extra space; stable.

Divide-and-conquer sorting: split the array in half, sort each half recursively, and merge the two sorted halves with two pointers. Its guaranteed O(n log n), stability and sequential access make it the choice for linked lists and external sorting; the merge step is reused in counting inversions and in "count of range sum".

Know it well enough to write it in a few minutes, including the merge. Mention when you would prefer it to quicksort (stability, worst-case guarantee, linked lists) and its O(n) memory cost. See also "Sorting algorithms", "Quicksort" and "K-way merge".

Minimax (game theory)

Category: techniques. Complexity: exponential in the depth without memoization; number of states × moves with it.

Deciding the best move in a two-player, turn-based game by assuming the opponent plays optimally: the maximising player picks the move with the highest value, the minimising player the lowest, recursively to the end of the game. Memoization over game states turns it into DP; alpha-beta pruning cuts branches that cannot change the result.

Appears as "predict the winner", "stone game", "can I win" and "guess number higher or lower II": define the state (the remaining range or set), the value from the current player's perspective, and memoize. Many such games have a closed-form or parity answer that you should check for first. See also "Dynamic programming".

Minimum spanning tree (Kruskal, Prim)

Category: graph algorithms. Complexity: Kruskal O(E log E) with sorting and union-find; Prim O(E log V) with a heap.

The cheapest set of edges that connects all vertices of a weighted undirected graph without cycles. Kruskal sorts the edges and adds each one that joins two different components (union-find). Prim grows a tree from one vertex, always adding the cheapest edge leaving it (heap). Both are greedy and both are correct.

The answer for "minimum cost to connect all points or cities" and "optimise water distribution" (add a virtual source). Use Kruskal when the edges are given as a list, Prim when the graph is dense or given by adjacency. See also "Union-find", "Greedy algorithms" and "Heap".

Modular arithmetic

Category: mathematics.

Doing arithmetic on remainders: (a + b) mod m = ((a mod m) + (b mod m)) mod m, and the same for subtraction (add m to avoid negatives) and multiplication. Division needs the modular inverse, which for a prime modulus p is b^(p − 2) mod p by Fermat's little theorem. Counting questions ask for answers modulo 10⁹ + 7 (a prime that keeps products of two reduced values within 64 bits).

Reduce after every addition and multiplication to prevent overflow, keep intermediate values non-negative, and do not apply the modulus to values you later compare for size (minimum or maximum). See also "Integer overflow and floating-point pitfalls" and "Exponentiation by squaring".

Monotonic deque (sliding window maximum)

Category: techniques. Complexity: O(n) time, O(k) space for a window of size k.

A deque that keeps candidate indices in decreasing order of value as a window slides: before pushing a new index, pop smaller values from the back (they can never be the maximum while the new one is in the window); pop from the front when its index leaves the window. The front is always the current maximum. Each index is pushed and popped at most once.

The O(n) solution to "sliding window maximum" and to DP transitions of the form "best over the last k values" (jump game VI, constrained subsequence sum). A heap gives O(n log n) and is the acceptable first answer. See also "Deque", "Monotonic stack" and "Sliding window".

Monotonic stack

Category: techniques. Complexity: O(n) time, O(n) space.

A stack whose values stay increasing or decreasing from bottom to top. Scanning the array, pop every element that violates the order before pushing the new one; each pop answers a "next greater" or "next smaller" question for the popped element. Each element is pushed and popped at most once, hence O(n).

The intended solution for next greater element, daily temperatures, largest rectangle in a histogram, maximal rectangle, trapping rain water (one of the methods), remove k digits, and "sum of subarray minimums". The signal is any question about the nearest larger or smaller element to the left or right. See also "Stack" and "Monotonic deque".

N

NP-completeness (P vs. NP)

Category: complexity.

P is the class of problems solvable in polynomial time; NP is the class whose solutions can be verified in polynomial time. NP-complete problems (satisfiability, travelling salesman decision, subset sum, graph colouring, Hamiltonian path, general knapsack, clique) are the hardest in NP: a polynomial algorithm for any one of them would give one for all, and none is known. Whether P equals NP is open.

Recognising an NP-hard core tells you to stop looking for a polynomial exact algorithm and to use backtracking with pruning, bitmask DP (for small n), pseudo-polynomial DP (when numbers are small), a greedy approximation, or to ask whether the constraints make the instance special (a DAG, a tree, bounded values). See also "Backtracking" and "Bitmask DP".

O

Ordered map (TreeMap, std::map, sorted containers)

Category: data structures. Complexity: insert, delete, lookup, floor, ceiling and range queries O(log n).

A map or set kept in key order, backed by a balanced BST or skip list: Java's TreeMap and TreeSet, C++'s std::map and std::set, and in Python the third-party sortedcontainers (the standard library has only bisect on a plain list, which gives O(log n) search but O(n) insert). It supports predecessor and successor queries and iteration in order, which hash maps cannot do.

Use it when you need "the smallest key greater than x" or "the largest key at most x" in a changing set: calendar booking, "my calendar", contains-duplicate-III, stock price fluctuations, range module, exam room. Say which structure your language provides and its complexity. See also "Balanced binary search tree" and "Hash table".

P

Palindromes (expand around centre, Manacher)

Category: string algorithms. Complexity: expand around centre O(n²) time and O(1) space; Manacher O(n); the DP table O(n²) time and space.

A string that reads the same backwards. Checking one is a two-pointer scan from both ends. Finding the longest palindromic substring: for each of the 2n − 1 centres (characters and gaps), expand outward while the characters match; the DP table dp[i][j] (is s[i..j] a palindrome) answers the same and counts palindromic substrings; Manacher's algorithm reaches O(n) but is rarely expected.

Expand around centre is the standard answer for longest palindromic substring and count substrings; the DP table is the base for palindrome partitioning (combined with backtracking or with a second DP for the minimum cuts). Clarify case and non-alphanumeric handling for "valid palindrome". See also "Two pointers" and "Dynamic programming".

Pigeonhole principle

Category: mathematics.

If n + 1 items go into n boxes, some box holds at least two. Simple, but it proves things such as "an array of n + 1 integers in the range 1 to n contains a duplicate", "among any n integers some subset sums to a multiple of n", and it bounds answers in bucket-based algorithms (maximum gap).

Use it to justify why a duplicate must exist (and therefore why Floyd's cycle method applies to "find the duplicate number") or why a bucket argument works. See also "Fast and slow pointers" and "Cyclic sort".

Prefix sum (and difference array)

Category: techniques. Complexity: O(n) to build, O(1) per range query; the 2D version O(rows · cols) to build and O(1) per submatrix query.

An array where prefix[i] is the sum of the first i elements, so the sum of any range [l, r] is prefix[r + 1] − prefix[l]. Combined with a hash map of seen prefix sums it counts subarrays with a given sum in O(n). The difference array is the inverse: to add a value to a range, add it at the start and subtract it after the end, then take prefix sums once to apply all range updates.

The first optimisation to consider for any question about range sums, subarray sums equal to k, or many range updates followed by one read (car pooling, corporate flight bookings). It also works for products, XOR and counts. For range queries with updates, move to a Fenwick or segment tree. See also "Sliding window" and "Fenwick tree".

Prime numbers (sieve of Eratosthenes)

Category: mathematics. Complexity: sieve O(n log log n) time and O(n) space; trial division per number O(√n).

The sieve lists all primes up to n by marking multiples of each prime starting from its square. Trial division up to the square root tests one number. Prime factorisation by trial division is O(√n) per number.

"Count primes" expects the sieve; questions about gcd-based grouping, "ugly numbers" and factorisation use trial division or a smallest-prime-factor table. Know that 10⁹ + 7 is prime because modular inverses depend on it. See also "Modular arithmetic".

Q

Quadratic time (O(n²))

Category: complexity.

Work proportional to the square of the input: every pair of elements, nested loops over the input, naive string building, insertion and bubble sort, many 2D dynamic programs (edit distance, LCS over two strings of length n), expand-around-centre palindromes. Fine for n up to a few thousand; too slow for 10⁵.

Usually the brute force. Ask what the inner loop recomputes and replace it with a hash map (pairs), a prefix sum or window (subarrays), sorting plus two pointers, or a monotonic stack (nearest larger or smaller). When the problem genuinely needs all pairs (three-sum's O(n²) after sorting), say why no better bound is known. See also "Brute force" and "Two pointers".

Queue

Category: data structures. Complexity: enqueue and dequeue O(1).

A first-in, first-out collection: elements are added at the back and removed from the front. Implemented with a linked list, a circular array or a deque. It drives BFS, level-order traversal, task scheduling and producer-consumer patterns; a circular queue of fixed size is a classic "design" question.

Use your language's deque (Python collections.deque, Java ArrayDeque), not a list with pop(0). "Implement a queue with two stacks" (amortised O(1)) and "implement a stack with queues" are standard warm-ups. See also "Deque", "BFS" and "Stack".

Quickselect

Category: selection. Complexity: O(n) average, O(n²) worst case; O(1) extra space.

Finding the k-th smallest element without fully sorting: partition the array around a pivot as in quicksort, then recurse only into the side that contains position k. A random pivot makes the expected time linear; the median-of-medians pivot guarantees O(n) but is slow in practice.

The follow-up to "k-th largest element" after the heap solution (O(n log k)): explain the partition, why only one side is explored, and the average-vs-worst trade-off. Also solves "k closest points" and "top k frequent" in average O(n). See also "Quicksort" and "Top-K elements".

Quicksort

Category: sorting. Complexity: O(n log n) average, O(n²) worst case (sorted input with a bad pivot); O(log n) stack space; in place; not stable.

Divide-and-conquer sorting that picks a pivot, partitions the array into elements smaller and larger than it, and recurses into both sides. Fast in practice because of in-place partitioning and good cache behaviour; random or median-of-three pivots avoid the quadratic case, and three-way partitioning handles many duplicates. C++'s std::sort uses introsort, a quicksort that falls back to heapsort.

Know the partition scheme (Lomuto or Hoare) well enough to write it, the worst case and how to avoid it, and when merge sort is preferred (stability, guaranteed bound, linked lists). See also "Merge sort", "Quickselect" and "Dutch national flag".

R

Rabin-Karp (rolling hash)

Category: string algorithms. Complexity: O(n + m) average, O(n · m) worst case with many hash collisions.

String matching by comparing hash values: compute the hash of the pattern and a rolling hash of each window of the text, updating it in O(1) as the window slides by removing the leftmost character and adding the new one (polynomial hashing modulo a large prime). Only windows whose hash matches are compared character by character. The same rolling hash finds repeated substrings and compares many substrings cheaply.

Mention it with KMP for substring search; prefer it when you need to search for many patterns at once or to detect repeated substrings of a fixed length (repeated DNA sequences, longest duplicate substring with binary search on the length). Say how you reduce collisions (large modulus, two hashes). See also "KMP algorithm" and "Hash table".

Randomised algorithms

Category: techniques.

Algorithms that use random choices, either to avoid worst cases (random pivot in quicksort and quickselect, random hash seeds) or because the task itself is random (shuffling, sampling, random pick with weight). Random pick with weight uses prefix sums of the weights and binary search on a random number; random pick from a stream of unknown length uses reservoir sampling; O(1) insert, delete and getRandom uses a hash map plus an array with swap-and-pop.

State the distribution you guarantee (uniform, proportional to weight) and the expected complexity. For these "design" questions, naming the combination of structures is most of the answer. See also "Fisher-Yates shuffle", "Reservoir sampling" and "Quickselect".

Recursion

Category: techniques. Complexity: number of calls × work per call; space O(maximum depth).

A function that calls itself on a smaller input until it reaches a base case. Every recursive solution needs a base case, progress towards it, and a clear statement of what the call returns. Recursion is the natural form of tree traversal, backtracking, divide and conquer and top-down DP; any recursion can be rewritten with an explicit stack, and tail recursion is not optimised in most interview languages.

Define the function's contract in one sentence before writing it ("returns the height of this subtree, or −1 if unbalanced"), handle null or empty first, and count the stack in your space complexity. If the recursion tree has repeated subproblems, add memoization. See also "Call stack and recursion depth", "Backtracking" and "Dynamic programming".

Reservoir sampling

Category: randomised algorithms. Complexity: O(n) time, O(k) space, one pass.

Choosing k items uniformly at random from a stream of unknown length: keep the first k items; for the i-th item after that, replace a random one of the kept items with probability k/i. Every item ends up chosen with probability k/n.

The answer to "random node from a linked list" or "random index of a target value" when the data cannot be stored or its length is unknown. Give the proof sketch for k = 1: the i-th item is kept with probability 1/i and survives all later steps with probability (i/(i + 1)) · ... · ((n − 1)/n) = i/n, so overall 1/n. See also "Randomised algorithms".

S

Segment tree

Category: data structures. Complexity: build O(n); range query and point update O(log n); range update O(log n) with lazy propagation; O(n) space (about 4n array slots).

A binary tree over array ranges in which each node stores an aggregate (sum, minimum, maximum, gcd) of its range. A query combines O(log n) nodes that cover the asked range; an update walks from the leaf to the root. Lazy propagation defers range updates to children until they are needed.

Needed when you have both range queries and updates, especially for non-invertible operations such as minimum and maximum: range minimum query with updates, "count of range sum", "falling squares", calendar booking with counts. For sums with point updates a Fenwick tree is shorter. State the recursive query and update clearly; implementing it is a 15-minute exercise, so mention it only when it is needed. See also "Fenwick tree" and "Prefix sum".

Set

Category: data structures. Complexity: hash set O(1) average for add, remove and contains; ordered set O(log n).

A collection of distinct elements with fast membership tests: a hash set (Python set, Java HashSet, C++ unordered_set) or an ordered set (TreeSet, std::set). Set operations (union, intersection, difference) run in time proportional to the sizes of the sets.

The tool for visited tracking, duplicate detection, "contains duplicate", intersection of arrays, and the O(n) "longest consecutive sequence" (only start counting from numbers whose predecessor is not in the set). Use a bitset or a boolean array when the elements are small integers. See also "Hash table" and "Ordered map".

Shortest path (which algorithm when)

Category: graph algorithms.

A decision guide. Unweighted graph or grid: BFS, O(V + E). Weights 0 and 1 only: 0-1 BFS with a deque. Non-negative weights: Dijkstra, O((V + E) log V). Negative weights or a cap on the number of edges: Bellman-Ford, O(V · E). All pairs on a small graph: Floyd-Warshall, O(V³). A DAG: relax edges in topological order, O(V + E), which also gives longest paths. A single target with a good heuristic: A-star.

Say which case you are in before naming the algorithm; choosing Dijkstra for an unweighted grid is correct but shows less judgement than BFS. See also "BFS", "Dijkstra's algorithm", "Bellman-Ford algorithm" and "Floyd-Warshall algorithm".

Sliding window

Category: techniques. Complexity: O(n) time; O(k) or O(alphabet) space.

Two indices that mark a contiguous range of an array or string, moved only forward: the right end grows the window, the left end shrinks it when a constraint is violated, and some running state (sum, counts in a hash map, number of distinct characters) is updated incrementally instead of recomputed. Fixed-size windows (maximum average subarray) and variable-size windows (longest substring without repeating characters, minimum window substring, minimum size subarray sum, fruit into baskets) are the two forms.

The signal is "contiguous subarray or substring" plus "longest", "shortest" or "count" under a condition that is monotonic as the window grows. State the invariant ("the window always satisfies the constraint") and why each index moves at most n times. It does not work when the constraint is not monotonic (negative numbers with a sum target: use prefix sums with a hash map). See also "Two pointers", "Prefix sum" and "Monotonic deque".

Sorting algorithms

Category: sorting. Complexity: comparison sorts at best O(n log n); counting-based sorts O(n + k).

The main ones: merge sort (O(n log n) always, stable, O(n) space), quicksort (O(n log n) average, in place, not stable), heapsort (O(n log n) always, in place, not stable), insertion sort (O(n²), but O(n) on nearly sorted input and good for tiny arrays), and the non-comparison sorts (counting, radix, bucket). Library sorts: Python and Java (for objects) use Timsort, a stable merge-insertion hybrid; C++ uses introsort; Java sorts primitives with dual-pivot quicksort. Any comparison sort needs Ω(n log n) comparisons in the worst case.

Call the library sort and state O(n log n); you are rarely asked to implement one, but you may be asked to compare them or to write merge sort or quicksort. Sorting first is the enabler for two pointers, greedy interval methods and binary search, so "can I sort?" is a question to ask yourself early. Use a custom comparator or key rather than hand-rolled logic. See also "Merge sort", "Quicksort", "Stable sort" and "Counting sort, radix sort and bucket sort".

Space-time trade-off

Category: complexity.

Spending memory to save time or the reverse: a hash map to avoid repeated searches, a prefix sum array to answer range queries, memoization to avoid recomputation, a precomputed table of results; or, in the other direction, recomputing values, in-place tricks and bit packing to meet an O(1)-space requirement.

Interviewers often ask for both: first "can you make it faster?" (usually spend memory), then "can you do it with O(1) extra space?" (usually spend time or use the input). Name the trade-off you are making each time you move. See also "Brute force" and "In-place algorithms".

Stable sort

Category: sorting.

A sort that keeps elements with equal keys in their original relative order. Merge sort, insertion sort, counting sort and Timsort are stable; quicksort and heapsort are not. Stability matters when sorting by one key after another (sort by name, then stably by department keeps names ordered within each department) and when ties must keep input order.

Mention it when sorting records by a secondary key, or when the question says "if two elements have the same value keep the one that appeared first". Library sorts in Python and Java (for objects) are stable; C++'s std::sort is not (use std::stable_sort). See also "Sorting algorithms".

Stack

Category: data structures. Complexity: push, pop and peek O(1).

A last-in, first-out collection: the most recently added element is removed first. Implemented with a dynamic array or a linked list. It models nesting and reversal: matching parentheses, evaluating expressions (shunting-yard, reverse Polish notation), undo, backtracking, simulating recursion, and the DFS frontier.

The signal is nested structure, "most recent unmatched" or "undo". Classic questions: valid parentheses, min stack (a second stack of running minima), evaluate RPN, decode string, simplify path, basic calculator, and the monotonic stack family. See also "Monotonic stack", "Queue" and "Call stack and recursion depth".

Strings (immutability and building)

Category: data structures. Complexity: indexing O(1); concatenation O(n) per operation; building a string of length n by repeated concatenation O(n²) unless a builder is used.

Strings are immutable in Python, Java and JavaScript, so every concatenation copies. Build results in a list and join at the end (Python), or use StringBuilder (Java). Comparison and hashing are O(length). Characters map to small integers, so frequency counts fit in an array of 26 or 128 entries, which is often faster than a hash map.

Most string questions are hash map, two pointer, sliding window or DP questions in disguise; the rest are parsing (state machines, stacks) or matching (KMP, rolling hash). Clarify the character set and case sensitivity, and avoid quadratic string building in loops. See also "Sliding window", "KMP algorithm" and "Palindromes".

Strongly connected components (Tarjan, Kosaraju)

Category: graph algorithms. Complexity: O(V + E).

In a directed graph, maximal sets of vertices that can all reach each other. Kosaraju's algorithm runs DFS to get a finishing order, then DFS on the reversed graph in that order; Tarjan's does it in one DFS with low-link values. Contracting each component to a node gives a DAG. Tarjan's low-link idea also finds bridges and articulation points in undirected graphs ("critical connections in a network").

Rare and advanced. Bring it up for "critical connections" (bridges) and for problems that become a DAG after contracting cycles. Know the names and the complexity; writing it is seldom required. See also "DFS" and "Directed acyclic graph".

Subarray, subsequence and subset

Category: fundamentals.

Three words that questions use precisely. A subarray or substring is contiguous (n(n + 1)/2 of them). A subsequence keeps the original order but may skip elements (2ⁿ of them). A subset ignores order entirely (2ⁿ of them). "Maximum subarray" is Kadane; "longest increasing subsequence" is DP; "subsets" is backtracking.

Repeat the word back when clarifying the problem, because the technique follows from it: contiguous usually means sliding window, prefix sums or Kadane; subsequence usually means DP; subset usually means backtracking, bitmasks or knapsack DP. See also "Sliding window", "Dynamic programming" and "Backtracking".

T

Top-K elements

Category: techniques. Complexity: O(n log k) with a heap of size k; O(n) average with quickselect; O(n) with bucket sort when frequencies are bounded by n.

Finding the k largest, smallest, most frequent or closest items. Keep a min-heap of size k while scanning (pop when it exceeds k), so the heap ends holding the k largest; use quickselect to partition around the k-th element; or, for frequencies, bucket items by count and read the buckets from the top.

Give the heap solution first (clear and O(n log k)), then quickselect or bucket sort as the linear-time follow-up. Say why the heap is a min-heap when you want the largest elements. Questions: k-th largest element, top k frequent elements or words, k closest points to origin, k closest elements in a sorted array (binary search plus two pointers is better there). See also "Heap" and "Quickselect".

Topological sort

Category: graph algorithms. Complexity: O(V + E).

An ordering of the vertices of a DAG such that every edge goes from earlier to later. Kahn's algorithm repeatedly removes vertices with in-degree zero using a queue, decrementing their neighbours' in-degrees; if some vertices are never removed, the graph has a cycle. The DFS version appends each vertex after its descendants are finished and reverses the result.

The answer to course schedule I and II, alien dictionary (build the graph from adjacent words first), build order, and "minimum height trees" (peel leaves layer by layer, a related idea). Say how you detect a cycle and that the order is not unique. See also "Directed acyclic graph" and "Cycle detection".

Tree

Category: data structures.

A connected graph with no cycles: n nodes and n − 1 edges, one path between any two nodes. Rooted trees have a root, parents, children, leaves, depth (distance from the root) and height (longest path down). Binary trees, BSTs, heaps, tries and segment trees are all trees; N-ary trees appear as org charts and file systems. An unrooted tree given as an edge list is handled with an adjacency list and a parent check instead of a visited set.

Most tree questions are solved by recursion on children with a null base case; many "graph" questions become easier once you notice the input is a tree (no visited set needed, DP over subtrees works). Know the vocabulary, because questions use it: diameter, balanced, complete, ancestor, subtree, level. See also "Binary tree", "Tree traversals" and "Graph".

Tree traversals (preorder, inorder, postorder, level order)

Category: tree algorithms. Complexity: O(n) time; O(h) space for depth-first traversals (O(n) worst case), O(w) for level order with w the maximum width.

The orders in which a binary tree's nodes can be visited. Preorder (node, left, right) copies or serialises a tree; inorder (left, node, right) visits a BST in sorted order; postorder (left, right, node) processes children before parents (delete a tree, compute subtree sizes, evaluate expression trees); level order (BFS with a queue) visits by depth. Each depth-first order can be written recursively or iteratively with an explicit stack; Morris traversal does inorder in O(1) space by temporarily threading the tree.

Many tree questions are "traversal plus a little state": level order variants (zigzag, right side view, level averages), reconstruct a tree from preorder and inorder, serialise and deserialise, flatten to a linked list, k-th smallest in a BST, validate a BST. Write the iterative inorder with a stack at least once before an interview. See also "BFS", "DFS" and "Binary search tree".

Trie (prefix tree)

Category: data structures. Complexity: insert, search and prefix lookup O(L) for a word of length L; space O(total characters × alphabet) in the worst case.

A tree in which each edge is a character and each node represents a prefix; a flag marks nodes that end a word. All words with a given prefix are in one subtree. Implemented with a node class holding a children map (or an array of 26) and an is-end flag.

The structure for autocomplete, word search II (prune a grid DFS with the trie), "design add and search words" (with wildcards by branching), replace words, longest common prefix over many strings, and maximum XOR of two numbers (a binary trie over bits). Write insert and search; they are short. See also "Strings" and "Backtracking".

Two heaps (running median)

Category: techniques. Complexity: O(log n) per insertion, O(1) per median query.

Keeping a max-heap of the smaller half of the numbers and a min-heap of the larger half, rebalanced so their sizes differ by at most one; the median is the top of the larger heap or the average of both tops. The same split handles "sliding window median" (with lazy deletion) and scheduling problems that balance two sets.

The expected answer to "find the median from a data stream". Explain the balancing rule and the invariant that every element in the max-heap is at most every element in the min-heap. See also "Heap".

Two pointers

Category: techniques. Complexity: O(n) time after an O(n log n) sort if needed; O(1) extra space.

Two indices moving through one or two arrays according to a rule: from both ends towards the middle (two-sum on a sorted array, container with most water, valid palindrome, three-sum after sorting), a slow writer and a fast reader (remove duplicates, move zeroes), or one index per array (merge sorted arrays, intersection). Each pointer moves at most n times, so the total is linear.

Use it when the input is sorted or can be sorted, or when the answer depends on a pair of positions that can be narrowed from the outside in. State why moving a pointer never discards the optimal pair. The sliding window and fast-and-slow patterns are two-pointer variants. See also "Sliding window", "Fast and slow pointers" and "Sorting algorithms".

Two-sum pattern (complement lookup)

Category: techniques. Complexity: O(n) time, O(n) space with a hash map; O(n log n) time with sorting and two pointers.

Finding two elements with a given sum by scanning once and checking whether the complement (target minus the current value) has already been seen in a hash map, which also records indices. Three-sum fixes one element and runs two pointers on the sorted rest in O(n²); four-sum and "k-sum" nest one more loop or use hashing of pair sums.

The first hash-map pattern everyone learns, and the model for "find a pair with property X": subarray sum equals k (prefix sums), pairs with difference k, count pairs that are divisible. Say whether duplicates and the same index twice are allowed. See also "Hash table" and "Two pointers".

U

Union-find (disjoint set union, DSU)

Category: data structures. Complexity: find and union in near-constant amortised time, O(α(n)) with path compression and union by rank or size, where α is the inverse Ackermann function; O(n) space.

A structure that keeps a partition of elements into disjoint sets, supporting "which set is x in?" (find, following parent pointers to the root) and "merge the sets of x and y" (union, attaching one root under the other). Path compression flattens the tree during find; union by rank or size keeps the trees shallow.

The tool for dynamic connectivity: number of connected components as edges arrive, redundant connection (the first edge that joins an already connected pair), accounts merge, Kruskal's MST, "number of islands II", and equality equations. Write find with path compression (two lines, iterative or recursive) and union with size. Say that it does not support splitting sets. See also "Connected components" and "Minimum spanning tree".

How to Use This Glossary

Each entry names its area, gives the time and space complexity where one applies, explains the term in plain language and then says, under "In interviews", when to use it, what to say and which follow-up to expect. Search for a term with the field at the top of the glossary; many entries list alternative names in the title (e.g. "Union-find (disjoint set union, DSU)" or "Fast and slow pointers (Floyd's cycle detection)"), so searching for either one works.

The areas are: fundamentals, complexity, data structures, sorting, searching, selection, techniques (the reusable patterns), dynamic programming, graph algorithms, tree algorithms, linked list algorithms, array algorithms, string algorithms, randomised algorithms, mathematics and interview method. The "techniques" and "dynamic programming" entries are the ones to study first; the named algorithms come up less often than the patterns.

A Structure for the Interview

A coding interview is usually 45 minutes with one or two problems. A sequence that works:

Clarify (2 to 3 minutes). Restate the problem, ask about input size, value ranges, duplicates, sortedness, empty input and the expected output format. Write a small example and an edge case.
Brute force (2 minutes). Describe the obvious solution and its complexity. Do not code it unless asked.
Optimise (5 to 10 minutes). Find the repeated work and match it to a pattern (see the next section). Explain the new approach and its complexity before writing code; agree with the interviewer that this is the version to implement.
Code (10 to 15 minutes). Write clean code with named helpers and clear variable names, talking through the invariants as you go. Handle the empty case first.
Test (5 minutes). Trace your code by hand on the example and on one edge case, line by line. Fix what you find without defensiveness.
Complexity and follow-ups. State the final time and space complexity and mention what you would change for a larger input, a stream, or an O(1)-space requirement.

Talk continuously but keep the content to decisions and reasons; silence while you think for twenty seconds is fine if you announce it.

From Problem to Pattern

Clues in the problem statement and the technique they usually point to:

Sorted input, or "in O(log n)": binary search. "Minimise the maximum" or "smallest value such that": binary search on the answer.
Contiguous subarray or substring with a condition: sliding window; with sums: prefix sum (plus a hash map for "equals k").
Pairs or triplets, especially in a sorted array: two pointers; a pair with a given sum in unsorted data: hash map.
"k largest", "k closest", "k most frequent", "merge k sorted": heap; the linear follow-up is quickselect or bucket sort.
"Next greater", "previous smaller", "largest rectangle": monotonic stack. Maximum or minimum of each window: monotonic deque.
"Number of ways", "minimum cost", "longest or shortest subsequence", "is it possible" with choices that build on each other: dynamic programming.
"All combinations", "all permutations", "all subsets", "all valid placements": backtracking.
Shortest path or fewest steps in a grid, maze or state space: BFS; with weights: Dijkstra; with negative weights: Bellman-Ford.
"Connected", "islands", "groups", "can reach": DFS, BFS or union-find; edges arriving one at a time: union-find.
Prerequisites, dependencies, ordering: topological sort.
Prefix matching, autocomplete, many strings: trie.
Counting, duplicates, grouping, complements: hash map or hash set.
Linked list cycle, middle, k-th from the end: fast and slow pointers; reversal: three pointers.
Overlapping ranges, meetings, bookings: sort by start then sweep, often with a heap of end times.
Parentheses, nesting, undo, expression evaluation: stack.
Range sums with updates: Fenwick tree; range minimum or maximum with updates: segment tree.
Numbers 1 to n, O(1) space: cyclic sort or index marking; "appears more than n/2 times": Boyer-Moore; "the single number": XOR.
Random element from a stream: reservoir sampling; weighted random choice: prefix sums plus binary search.
Choose the most non-overlapping items, earliest deadline, "jump game": greedy, with a reason why greedy is safe.

Complexity Cheat Sheet

Typical operation costs:

Dynamic array: index O(1), append O(1) amortised, insert or delete in the middle O(n), search O(n).
Linked list: access O(n), insert or delete at a known node O(1).
Hash map or set: insert, lookup, delete O(1) average.
Ordered map or set (balanced BST): all operations O(log n), including floor, ceiling and range scans.
Heap: push and pop O(log n), peek O(1), build O(n).
Stack, queue, deque: push and pop O(1).
Binary search: O(log n). Sorting: O(n log n). BFS and DFS: O(V + E). Dijkstra: O((V + E) log V). Union-find: near O(1) per operation. Trie: O(length of the word).
Backtracking: O(n · 2ⁿ) for subsets, O(n · n!) for permutations.

What the input size suggests, assuming roughly 10⁸ simple operations per second:

n up to about 10 or 12: O(n!) is acceptable.
n up to about 20 to 25: O(2ⁿ) or O(2ⁿ · n), i.e. bitmasks or backtracking.
n up to a few hundred: O(n³), e.g. Floyd-Warshall or interval DP.
n up to a few thousand: O(n²), e.g. simple DP over pairs.
n up to about 10⁵ or 10⁶: O(n log n), i.e. sorting, heaps, binary search.
n up to about 10⁷ or 10⁸: O(n), one or two passes.
Larger, or many queries: O(log n) or O(1) per query after preprocessing.

Growth for n = 1,000,000: log₂ n is about 20; n log n is about 2 × 10⁷; n² is 10¹², which is out of reach; 2ⁿ is unthinkable past n of about 40.

Fixed-width integers: 32-bit signed up to about 2.1 × 10⁹; 64-bit signed up to about 9.2 × 10¹⁸; 20! is the last factorial that fits in 64 bits.

Terms That Are Easy to Confuse

Big-O vs. big-Θ vs. big-Ω: upper bound vs. tight bound vs. lower bound. Interviews say "big-O" and mean the tight bound of the worst case.
Worst case vs. average case vs. amortised: the slowest single input vs. the expectation over inputs vs. the average over a sequence of operations on any input.
Stack (data structure) vs. call stack (memory), heap (data structure) vs. heap (memory): the structures you choose vs. the regions where a program keeps frames and objects.
Hash map vs. hash set vs. ordered map: key-value in O(1) vs. membership in O(1) vs. sorted keys in O(log n).
Binary tree vs. binary search tree vs. binary heap: a shape vs. an ordering of keys left-to-right vs. a parent-child ordering stored in an array.
Tree vs. graph vs. DAG: no cycles and connected vs. anything vs. directed without cycles.
BFS vs. DFS: level by level with a queue (shortest paths) vs. as deep as possible with a stack or recursion (components, cycles, orderings).
Dijkstra vs. BFS vs. Bellman-Ford: non-negative weights vs. unit weights vs. negative weights allowed.
Subarray vs. subsequence vs. subset: contiguous vs. ordered with gaps vs. unordered.
Permutation vs. combination: order matters vs. it does not.
Memoization vs. tabulation: top-down recursion with a cache vs. bottom-up table filling.
Greedy vs. dynamic programming: commit to each local choice vs. consider all choices and keep the best per state.
Divide and conquer vs. dynamic programming: independent subproblems vs. overlapping subproblems.
Stable vs. unstable sort: equal keys keep their order vs. may not.
In place vs. O(1) extra space: the input is modified vs. the extra memory is constant; recursion still uses stack space.
Queue vs. deque vs. priority queue: FIFO vs. both ends vs. by priority (a heap).
log n vs. n log n: one binary search vs. a sort or n binary searches.

For the vocabulary of system design interviews (caching, sharding, consistency, load balancing), see also the System Design Glossary. For the names and history of specific technologies, see the Tech Skills Glossary for Recruiters.