DSA Interview Questions (Data Structures and Algorithms)

A data structure is a way of organizing and storing data so it can be accessed and modified efficiently. The right choice determines the time and space cost of operations like search, insert, and delete, which can be the difference between an algorithm that runs in milliseconds and one that times out. Interviewers care because picking the correct structure is often the core of solving a problem efficiently.

Big-O notation describes how an algorithm's running time or memory usage grows as the input size n grows, focusing on the dominant term and ignoring constants. Time complexity measures the number of operations performed, while space complexity measures the extra memory used beyond the input. Common classes from fastest to slowest are O(1), O(log n), O(n), O(n log n), O(n^2), and O(2^n).

Best case is the fastest an algorithm can finish on a favorable input, average case is the expected cost across the realistic distribution of inputs, and worst case is the slowest it can ever run. Production systems and interviews usually care about the worst case, because that is what decides whether a request times out. Quicksort is the standard example: O(n log n) on average but O(n^2) on an adversarial input.

Big-O is an upper bound — the algorithm grows no faster than this. Big-Omega is a lower bound, and Big-Theta is a tight bound that holds both above and below, meaning the growth rate is exactly that class. Saying merge sort is O(n^2) is technically true but useless; Theta(n log n) is the precise statement. Most interviews use O loosely to mean Theta, but knowing the distinction is the mark of someone who has studied the material rather than memorized it.

Amortized complexity spreads the cost of an occasional expensive operation across the cheap ones in a guaranteed sequence, whereas average case reasons about a probability distribution over inputs. A dynamic array append is amortized O(1): most appends are constant, and the O(n) resize is paid for by the n cheap appends that preceded it. The distinction matters because amortized bounds are deterministic — there is no unlucky input that breaks them.

Space complexity measures the auxiliary memory an algorithm needs beyond the input itself. That includes temporary arrays, hash maps, and — critically — the call stack of a recursive function, which is why a recursive traversal of a skewed tree is O(n) space rather than O(1). Candidates lose points by calling a recursive solution constant-space; if it recurses to depth d, it costs O(d) stack.

Big-O describes growth as n heads toward infinity, and in that limit the dominant term decides everything: 3n^2 + 500n + 9000 is Theta(n^2), because the n^2 term eventually dwarfs the rest. Dropping constants also makes the notation machine-independent, since a factor of two depends on hardware and compiler, not on the algorithm. The trade-off is that Big-O cannot tell you which of two O(n) algorithms is faster on real input sizes.

Multiply the iteration counts of the loops that are nested inside each other and add the counts of loops that run in sequence. Two independent loops over n are O(n) + O(n) = O(n); one loop over n containing a loop over n is O(n^2). Watch for loops whose bound depends on the outer variable — for j from i to n inside a loop over n gives n(n+1)/2 iterations, which is still O(n^2), and for loops where the counter doubles, which is O(log n).

Write a recurrence relation for the work done: merge sort is T(n) = 2T(n/2) + O(n), binary search is T(n) = T(n/2) + O(1). You then solve it by expanding the recursion tree and summing the work per level, or by applying the master theorem, which compares the cost of the recursive calls against the work done outside them. Merge sort resolves to O(n log n) because each of the log n levels does O(n) work.

Yes, and this is one of the most useful things to say in an interview. Big-O hides constants and cache behavior, so insertion sort beats merge sort on small arrays, and a linear scan of a contiguous array often beats a pointer-chasing O(log n) tree lookup because it never leaves the CPU cache. Real library sorts exploit this by switching to insertion sort below a threshold. Asymptotics decide what happens at scale; constants and memory locality decide what happens at the sizes you actually run.

Accessing an element by index is O(1) because the address is computed directly. Searching an unsorted array is O(n), while inserting or deleting at the end of a dynamic array is amortized O(1). Inserting or deleting at the beginning or middle is O(n) because the remaining elements must be shifted.

A dynamic array, such as a Python list or Java ArrayList, automatically grows when it runs out of capacity by allocating a larger block and copying the elements over. Most appends are O(1), but the occasional resize is O(n); spread across many appends the average cost per append is still constant, which is called amortized O(1). Doubling the capacity on each resize is what keeps the amortized cost constant.

Growing by a constant factor — typically 1.5x or 2x — makes the total copying work across n appends a geometric series that sums to O(n), giving amortized O(1) per append. Growing by a fixed number of slots instead forces a resize every k appends, so the copying work becomes O(n^2) overall. The factor is a memory-versus-copying trade-off: 2x wastes more space at the moment of the resize, 1.5x reuses freed blocks better.

Two pointers walk the array from opposite ends, or at different speeds from the same end, so a problem that looks quadratic collapses to a single O(n) pass with O(1) extra space. It works when the array is sorted or when the answer has a monotonic property — finding a pair that sums to a target, reversing in place, removing duplicates, or the container-with-most-water problem. The usual mistake is trying it on unsorted data where the invariant that lets you move a pointer does not hold.

A sliding window keeps a contiguous range defined by two indices, expanding the right edge to include new elements and contracting the left edge when a constraint is violated, so each element enters and leaves the window at most once and the whole scan is O(n). Fixed-size windows suit problems like the maximum sum of k consecutive elements; variable-size windows suit the longest substring with at most k distinct characters. It replaces the naive O(n^2) recomputation of every subarray.

Use the reversal trick: reverse the whole array, then reverse the first k elements, then reverse the remaining n minus k. That is O(n) time and O(1) extra space, versus the naive approach of rotating one step k times, which is O(n*k). Remember to take k modulo n first, otherwise a k larger than the length does needless work or breaks the index math.

Compute the expected sum n(n+1)/2 and subtract the actual sum; the difference is the missing value. That is O(n) time and O(1) space, and beats sorting or using a hash set. If overflow is a concern, XOR every index from 1 to n with every array element instead — the pairs cancel and the missing number survives.

The general answer is a hash set: scan once, and report any value already present, giving O(n) time and O(n) space. If the values are constrained to the range 1 to n you can do it in O(1) extra space by using the array itself as a marker — negate the value at index equal to the current value, and a value already negative signals a duplicate. Sorting first is a third option at O(n log n) time and no extra space if in-place sorting is allowed.

Most languages, including C, C++, Java, and NumPy by default, store 2D arrays in row-major order, meaning an entire row occupies contiguous memory. Iterating row by row therefore walks memory sequentially and hits the CPU cache on almost every access, while iterating column by column jumps by a full row stride each step and can be several times slower despite identical Big-O. This is one of the clearest cases where the constant factor, not the complexity class, decides performance.

Walk both arrays with one index each and repeatedly copy the smaller front element, which is O(n + m) and the merge step at the heart of merge sort. If one array has trailing free capacity — the common interview variant — fill from the back instead, comparing the largest remaining elements, so you never overwrite an element you have not yet read. Concatenating and re-sorting works but is O((n+m) log(n+m)) and throws away the sortedness you were given.

Immutability makes strings safe to share across threads and to cache, lets the runtime intern identical literals so they occupy one allocation, and allows the hash code to be computed once and reused — which is why strings are such good hash map keys. The cost is that every modification allocates a new string, so building a string by repeated concatenation is expensive. That is what StringBuilder in Java and str.join in Python exist to avoid.

It is O(n^2), because each concatenation allocates a new string and copies everything accumulated so far, and those copies sum to a quadratic total. Appending to a mutable builder — StringBuilder, a list of parts joined at the end, or a bytes buffer — is amortized O(1) per append and O(n) overall. This is one of the most common real-world performance bugs interviewers probe for.

Swap the characters at two pointers moving inward from the ends until they meet, which is O(n) time and O(1) extra space. In languages with immutable strings you must first convert to a character array or list, because there is nothing to mutate otherwise. Slicing tricks like s[::-1] are fine to mention but allocate a full copy, so say which one the question is really asking for.

Compare characters with two pointers moving inward from both ends and stop at the first mismatch, which is O(n) time and O(1) extra space. Normalize first if the question mentions phrases — lowercase everything and skip non-alphanumeric characters. Reversing the string and comparing gives the same answer but allocates a second copy, so the two-pointer version is the stronger response.

Count the characters of both strings into frequency maps and compare them, which is O(n) time and O(k) space for the alphabet size. Sorting both and comparing also works and needs no extra structure, but it is O(n log n). Check lengths first as a cheap early exit, and clarify whether case and whitespace should be ignored.

Use a sliding window with a map from character to its last seen index. Expand the right edge one character at a time, and when you hit a repeat, jump the left edge to just past the previous occurrence rather than sliding it one step at a time. Each character is processed once, giving O(n) time and O(k) space, where k is the alphabet size.

It computes a rolling hash of the pattern and of each window of the text, so moving the window one character is O(1) rather than O(m): you subtract the outgoing character's contribution and add the incoming one. When hashes match you still compare characters to rule out a false positive from a hash collision. Average case is O(n + m), worst case O(n*m) if collisions are adversarial, and its real strength is searching for many patterns at once.

Naive substring search restarts the pattern from scratch after a mismatch, which is O(n*m) in the worst case. KMP precomputes a failure function — for each prefix of the pattern, the length of the longest proper prefix that is also a suffix — so on a mismatch it shifts the pattern by the largest safe amount without ever moving the text pointer backwards. That gives O(n + m) total time with O(m) extra space.

An array stores elements in contiguous memory, giving O(1) access by index but O(n) cost to insert or delete in the middle because elements must shift. A linked list stores elements as nodes connected by pointers, so inserting or deleting at a known position is O(1), but accessing an element requires walking the list in O(n) and it uses extra memory for the pointers. Use arrays when you need fast random access and linked lists when you do frequent insertions and deletions.

A singly linked list gives each node one next pointer, so traversal is forward only. A doubly linked list adds a previous pointer, which allows backward traversal and O(1) deletion of a node you already hold, at the cost of an extra pointer per node. A circular linked list joins the tail back to the head, which suits round-robin scheduling and buffers; the doubly circular variant combines both.

Iteratively, keep three pointers — previous, current, and next — and on each step point current.next at previous, then advance all three; return previous at the end. That is O(n) time and O(1) space. The recursive version reads more neatly but costs O(n) stack space, so it can overflow on a long list; mention both and say which you would ship.

Use Floyd's tortoise and hare: move one pointer one node at a time and another two nodes at a time, and if they ever meet there is a cycle, while the fast pointer reaching null means there is not. It is O(n) time and O(1) space. The hash-set alternative — record every visited node — is also O(n) time but O(n) space, so the two-pointer version is the expected answer.

After the slow and fast pointers meet inside the cycle, reset one pointer to the head and advance both one node at a time; they meet exactly at the cycle entry. The reason is that the distance from the head to the entry equals the distance from the meeting point to the entry, going around the loop. Getting the derivation right, not just the recipe, is what interviewers are checking.

Advance a slow pointer one node and a fast pointer two nodes per step; when the fast pointer reaches the end, the slow pointer is at the middle. It is O(n) time and O(1) space and needs no length count. Decide up front which node counts as the middle for an even-length list, since the loop condition differs by one depending on the convention.

Advance one pointer n nodes ahead, then move both pointers together until the leading one falls off the end; the trailing pointer is on the answer. One pass, O(n) time, O(1) space, versus counting the length and walking again. Guard the case where n exceeds the list length before dereferencing.

Use a dummy head node and repeatedly attach whichever list has the smaller front value, advancing that list, then attach the remaining tail when one list runs out. It is O(n + m) time and O(1) extra space because you are relinking existing nodes rather than allocating new ones. The dummy head is the trick that removes all the special-casing around the first node.

Walk pointer A through list A then continue into list B, and pointer B through list B then into list A; both travel the same total distance, so they meet at the intersection node or both reach null. It is O(n + m) time and O(1) space. The alternative is to measure both lengths, advance the longer list by the difference, then step in lockstep — same complexity, more code.

Merge sort only needs sequential access and can relink nodes rather than move data, so it sorts a list in O(n log n) time with O(1) extra space in the iterative bottom-up form — the recursive form costs O(log n) stack. Quicksort and heap sort both rely on random access to be fast, which a linked list cannot provide. This is the mirror image of arrays, where quicksort usually wins on cache behavior.

A stack is a last-in, first-out (LIFO) structure where you push items onto the top and pop them off the top, both in O(1). It is used for function call management (the call stack), undo features, expression evaluation, and depth-first search. You can implement it with either an array or a linked list.

A queue is a first-in, first-out (FIFO) structure where you enqueue at the back and dequeue from the front, both in O(1). Unlike a stack, which removes the most recently added item, a queue removes the oldest item first. Queues are used for breadth-first search, task scheduling, and buffering; variants include the deque (double-ended) and the circular queue.

Scan the string pushing every opening bracket onto a stack, and on each closing bracket pop and check that it matches the expected partner. The expression is balanced only if every pop matches and the stack is empty at the end. It is O(n) time and O(n) space; the two failure modes people forget are a closing bracket with an empty stack and leftover openers at the end.

Keep an input stack and an output stack. Enqueue pushes onto the input stack; dequeue pops from the output stack, and when the output stack is empty you first pour the entire input stack into it, which reverses the order into FIFO. Each element is moved at most twice, so dequeue is amortized O(1) even though an individual dequeue can be O(n).

A deque, or double-ended queue, supports O(1) insertion and removal at both the front and the back, and is usually implemented as a doubly linked list or a ring buffer of blocks. It generalizes both a stack and a queue, and it is the right structure for a fixed-size sliding window, an undo/redo history, or a work-stealing scheduler. In Python it is collections.deque; in Java, ArrayDeque.

A circular queue stores elements in a fixed array and wraps the head and tail indices around with modulo arithmetic, so dequeued slots at the front are reused instead of leaking. Without the wraparound, a simple array queue keeps advancing its head until it runs out of space even when most of the array is empty. It is the standard structure behind ring buffers, producer-consumer pipelines, and fixed-capacity streaming buffers.

Keep a second stack that holds the running minimum: on every push, also push the smaller of the new value and the current minimum, and pop both stacks together. Every operation stays O(1), at the cost of O(n) extra space. A space-optimized variant stores only the values that changed the minimum, or encodes the difference from the previous minimum in a single stack.

A monotonic stack keeps its contents in strictly increasing or decreasing order by popping any element that would break the invariant before pushing. Because each element is pushed and popped at most once, a whole family of problems solves in O(n) instead of O(n^2): next greater element, daily temperatures, largest rectangle in a histogram, and trapping rain water. The tell is any question phrased as "for each element, find the nearest element to its left or right that is bigger or smaller".

For postfix, scan left to right pushing operands onto a stack, and on each operator pop the required operands, apply it, and push the result; the single remaining value is the answer, in O(n). Infix needs conversion first because precedence and parentheses make it impossible to evaluate in a single left-to-right pass. The shunting-yard algorithm does the conversion with an operator stack, popping higher-precedence operators before pushing a lower-precedence one.

A hash table stores key-value pairs by passing the key through a hash function that maps it to an index in an underlying array. This gives average O(1) time for insert, delete, and lookup. In the worst case, when many keys collide into the same bucket, operations can degrade to O(n), which is why a good hash function and resizing matter.

A collision occurs when two different keys hash to the same index. The two common resolution strategies are separate chaining, where each bucket holds a linked list (or tree) of entries that share the index, and open addressing, where the table probes for the next free slot using methods like linear or quadratic probing. Keeping the load factor low and resizing the table helps keep collisions rare.

It should distribute keys uniformly across the table so that no bucket is favored, be fast to compute since it runs on every operation, and be deterministic so the same key always lands in the same place. It must also depend on every part of the key — a hash that only looks at the first character clusters badly on real data. In practice you rarely write your own; you compose the language's built-in hashes and let the table handle the modulo.

The load factor is the number of stored entries divided by the number of buckets, and it is the main dial on the space-versus-collision trade-off. Once it crosses a threshold — 0.75 in Java's HashMap, around 0.66 in CPython's dict — the table allocates a larger array and rehashes every entry into it, an O(n) operation amortized across the inserts that caused it. Open addressing needs a lower threshold than chaining, because probe sequences lengthen sharply as the table fills.

Chaining tolerates load factors above 1, degrades gracefully, and makes deletion trivial, but every bucket is a pointer hop into scattered memory, which is cache-unfriendly and costs an allocation per entry. Open addressing keeps everything in one contiguous array, so it is faster on cache-friendly workloads and uses less memory per entry, but it degrades sharply as the table fills and deletion needs tombstones because removing an entry would break other keys' probe sequences.

It degrades when many keys land in the same bucket — from a weak hash function, a pathological key distribution, or a deliberate hash-collision denial-of-service attack where an attacker crafts colliding keys. Java 8 and later convert a bucket to a balanced tree once its chain exceeds eight entries, bounding the worst case at O(log n). Python and many others randomize the hash seed per process so an attacker cannot precompute collisions offline.

The table stores an entry in the bucket implied by the key's hash at insertion time. If you mutate the key afterwards, its hash changes, so a lookup probes a different bucket and the entry becomes unreachable even though it is still in the table. That is why Python requires hashable (effectively immutable) keys and why mutable objects used as Java map keys are a classic memory-leak-shaped bug.

If two objects are equal, they must return the same hash code; the converse need not hold, since unequal objects may legitimately collide. Overriding equals without overriding hashCode breaks lookups, because the map computes the wrong bucket and never reaches the equality check. Both should be derived from the same immutable fields, which is exactly what records in Java and dataclasses with frozen=True in Python generate for you.

A Bloom filter is a compact bit array with k hash functions that answers set membership with no false negatives but a tunable rate of false positives, in constant space per query regardless of element size. It is used as a cheap front door: a database checks it before touching disk, a crawler checks it before refetching a URL. The trade-offs are that you cannot delete from a standard Bloom filter and you cannot enumerate its contents.

A binary tree is a hierarchical structure where each node has at most two children, called left and right. A binary search tree (BST) adds an ordering rule: every node's left subtree contains only smaller keys and its right subtree only larger keys. That ordering makes search, insert, and delete run in O(log n) on a balanced tree, versus O(n) for an unordered binary tree.

If keys are inserted in sorted order, a plain BST becomes a long chain resembling a linked list, so operations degrade from O(log n) to O(n). Self-balancing trees fix this by restructuring after insertions and deletions to keep the height around log n. Common examples are AVL trees and red-black trees, the latter being used in many standard library map and set implementations.

Depth-first traversals visit nodes recursively in three orders: in-order (left, node, right), which yields sorted output for a BST; pre-order (node, left, right), useful for copying a tree; and post-order (left, right, node), useful for deleting a tree. Breadth-first traversal, also called level-order, visits nodes level by level using a queue. All four visit every node once, so they run in O(n).

Depth is the number of edges from the root down to the node, so the root has depth 0. Height is the number of edges on the longest path from the node down to a leaf, so every leaf has height 0 and the height of the tree is the height of its root. Interviewers ask because the two are easy to confuse, and an off-by-one here quietly breaks balance checks.

A full binary tree is one where every node has either zero or two children, never one. A complete binary tree has every level filled except possibly the last, which is filled left to right — this is the shape a binary heap maintains, and it is what lets a heap live in a flat array. A perfect binary tree has all internal nodes with two children and all leaves at the same depth, so it holds exactly 2^h+1 minus 1 nodes.

Use an explicit stack: push nodes while walking left as far as possible, then pop, visit the node, and move to its right child, repeating until both the stack and the current pointer are exhausted. It is O(n) time and O(h) space, where h is the height. The reason to know it is that recursion can overflow the call stack on a deep or skewed tree, and Morris traversal goes further by threading the tree to achieve O(1) space.

The diameter is the longest path between any two nodes, which may or may not pass through the root. Compute it in a single post-order pass: each recursive call returns the height of its subtree, and while unwinding you update a running maximum with left height plus right height plus two, the path through that node. That is O(n); the naive version that recomputes height at every node is O(n^2).

In a BST, walk down from the root: if both targets are smaller go left, if both are larger go right, and the first node that splits them — or equals one of them — is the LCA, in O(h). In a general binary tree there is no ordering to exploit, so you recurse and return the node where the two targets first appear in different subtrees, in O(n). If you need many queries, preprocess with binary lifting for O(log n) per query.

Recurse carrying a permitted (min, max) range, tightening it as you descend, and reject any node outside its range. The common wrong answer only compares each node to its immediate children, which accepts trees that violate the ordering two levels down. The alternative is an in-order traversal checking that the sequence is strictly increasing; both are O(n).

A tree is height-balanced when, for every node, the heights of its two subtrees differ by at most one, which keeps the overall height O(log n). Check it with a post-order traversal that returns the subtree height and short-circuits to a sentinel as soon as any node is unbalanced, giving O(n). Computing height separately at every node is the O(n^2) trap.

An AVL tree is a BST that stores a balance factor per node and requires the heights of every node's subtrees to differ by at most one. After an insert or delete it walks back up to the root and applies single or double rotations — left-left, right-right, left-right, right-left — to restore the invariant in O(log n). The strict balancing gives faster lookups than a red-black tree but more rotations on write-heavy workloads.

A red-black tree colors nodes red or black and enforces rules — the root and leaves are black, no red node has a red child, and every root-to-leaf path has the same number of black nodes — that keep the height within 2 log(n+1). It rebalances with at most a constant number of rotations per insert or delete, versus AVL's potentially longer cascade, so it is cheaper on mixed read-write workloads. That is why Java's TreeMap, C++'s std::map, and the Linux kernel scheduler use it.

A B-tree is a self-balancing search tree where each node holds many keys and many children, so the tree is very shallow — often three or four levels for millions of rows. That matters because database and filesystem storage is read in fixed-size pages, and a node sized to one page turns each level of the tree into exactly one disk or SSD read. A binary tree with the same data would need log2(n) reads instead of log_b(n), which is an order of magnitude more I/O.

A trie stores strings by their characters along tree edges, so a lookup or insert costs O(m) in the length of the key with no hashing and no collisions. It beats a hash map whenever you need prefix operations — autocomplete, longest-prefix routing, or listing every word starting with a given stem — because a hash map cannot answer those without scanning everything. The cost is memory: a naive trie allocates a child array per node, which compressed variants like a radix tree reduce.

A segment tree answers range queries — sum, minimum, maximum, or any associative operation — over an array in O(log n) while still supporting O(log n) point updates, using O(n) space. A prefix-sum array answers the same queries in O(1) but costs O(n) per update, so the segment tree is the right choice when updates and queries are interleaved. Lazy propagation extends it to range updates without losing the log bound.

A Fenwick tree, or binary indexed tree, supports prefix-sum queries and point updates in O(log n) using a flat array of size n and a handful of bit-manipulation operations on the lowest set bit. It is far smaller and faster in constant factors than a segment tree, and much shorter to write. The trade-off is generality: it needs an invertible operation such as addition, so it cannot answer range minimum queries the way a segment tree can.

A heap is a complete binary tree that satisfies the heap property: in a min-heap every parent is smaller than its children, and in a max-heap every parent is larger. This lets you find the minimum or maximum in O(1) and insert or remove the root in O(log n). Heaps are the standard implementation behind priority queues and are used in algorithms like Dijkstra's shortest path and heap sort.

A priority queue serves elements in order of priority rather than insertion order, exposing insert and extract-highest-priority. The standard implementation is a binary heap, giving O(log n) insert and extract with O(1) peek. A sorted array would give O(1) extract but O(n) insert, and an unsorted array the reverse — the heap is the balanced compromise, which is why it is the default everywhere.

Because a heap is always a complete binary tree, its shape is fully determined, so node i's children sit at 2i+1 and 2i+2 and its parent at (i-1)/2 with zero-based indexing. That removes all pointer overhead, keeps the whole structure in contiguous cache-friendly memory, and makes traversal pure arithmetic. It is the clearest example of a structural invariant buying you an implementation shortcut.

Inserting n elements one at a time is O(n log n), but Floyd's build-heap runs sift-down from the last internal node backwards to the root, and the cost of sift-down depends on the node's height, not the tree height. Half the nodes are leaves costing nothing, a quarter can sink one level, an eighth two levels, and that series sums to O(n). It is a favorite interview question precisely because the obvious bound is wrong.

Keep a min-heap of size k: push each element and pop the smallest whenever the heap exceeds k, so the heap always holds the k largest seen so far. That is O(n log k) time and O(k) space, which beats sorting at O(n log n) when k is small and works on a stream where you cannot hold everything. Quickselect gives O(n) average time if the data fits in memory and you can reorder it.

Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half, rebalancing after each insert so their sizes differ by at most one. The median is then the top of the larger heap, or the average of both tops when the sizes are equal. Each insert is O(log n) and the median read is O(1) — the key insight is that you never need the full sorted order, only the boundary between the halves.

Push the head of each list into a min-heap of size k, then repeatedly pop the smallest and push that list's next element. With N total elements that is O(N log k) time and O(k) space, versus O(N*k) for scanning all k heads each time. The alternative is pairwise merging in a tournament, which reaches the same O(N log k) bound.

Heap sort builds a max-heap in O(n), then repeatedly swaps the root to the end and sifts down, giving a guaranteed O(n log n) worst case with O(1) extra space — strictly better guarantees than quicksort and less memory than merge sort. In practice it is usually slower than quicksort because its access pattern jumps around the array and defeats the cache, and it is not stable. That is why libraries typically use it only as the fallback when quicksort recursion gets too deep.

A graph is a set of vertices (nodes) connected by edges, which may be directed or undirected and weighted or unweighted. The two common representations are an adjacency list, which stores for each vertex a list of its neighbors and is memory-efficient for sparse graphs, and an adjacency matrix, a two-dimensional array that gives O(1) edge lookups but uses O(V^2) space. Choose the list for sparse graphs and the matrix for dense graphs or frequent edge queries.

Breadth-first search (BFS) explores a graph level by level using a queue, and on an unweighted graph it finds the shortest path in terms of number of edges. Depth-first search (DFS) explores as far as possible along each branch before backtracking, using a stack or recursion, and is well suited to detecting cycles, topological sorting, and exploring connected components. Both run in O(V + E) time using an adjacency list.

A directed acyclic graph is a directed graph with no cycles, which means its vertices can be linearly ordered so every edge points forward — that ordering is a topological sort. DAGs model dependencies: build systems, task schedulers, course prerequisites, package managers, and the computation graphs behind automatic differentiation. The absence of cycles is what makes dynamic programming over a DAG well-defined.

Run BFS from the source, recording each node's parent as you first reach it; because BFS expands in order of edge count, the first time you touch a node you have reached it by a shortest path. It is O(V + E), and you rebuild the path by walking parents backwards from the target. Dijkstra would give the same answer but wastes a priority queue on edges that all weigh the same.

A topological sort is a linear ordering of a directed graph's vertices such that every edge goes from earlier to later, and it exists exactly when the graph is acyclic. Kahn's algorithm repeatedly removes a vertex with in-degree zero; the DFS variant pushes each vertex onto a stack after exploring its descendants and reverses the result. Both are O(V + E), and Kahn's doubles as a cycle detector — leftover vertices mean a cycle.

Run DFS with three colors: white for unvisited, gray for on the current recursion stack, black for finished. An edge to a gray vertex is a back edge and proves a cycle; an edge to a black vertex is fine. Using a simple visited set instead of tracking the recursion stack is the classic bug, because it wrongly flags a diamond-shaped DAG as cyclic. Kahn's algorithm gives the same answer by counting how many vertices it manages to emit.

DFS while passing the parent down, and treat any edge to an already-visited vertex that is not the parent as a cycle — otherwise every single edge looks like a two-node cycle. Union-find is the alternative: process each edge and report a cycle when both endpoints already share a root, which runs in near-linear time and needs no traversal order. Watch for parallel edges, which are genuine cycles and must not be excused by the parent check.

Union-find tracks a partition of elements into disjoint sets with two operations: find, which returns the representative of an element's set, and union, which merges two sets. It is the backbone of Kruskal's minimum spanning tree, undirected cycle detection, and connected-component counting on a stream of edges. With both optimizations applied, each operation is effectively constant time.

Union by rank (or size) always attaches the shallower tree under the deeper one, which stops the structure from degenerating into a long chain. Path compression flattens the tree during find by repointing every node on the path directly at the root. Applied together they give an amortized cost of O(alpha(n)), the inverse Ackermann function, which is below five for any input that fits in the universe — effectively constant.

Dijkstra greedily grows a set of vertices whose shortest distance from the source is final: it repeatedly extracts the unfinalized vertex with the smallest tentative distance from a min-heap and relaxes its outgoing edges. With a binary heap this is O((V + E) log V), and with a Fibonacci heap O(E + V log V). The greedy choice is only valid because adding an edge can never decrease a path length, which requires non-negative weights.

Dijkstra finalizes a vertex the moment it is popped, assuming no later path can be shorter — a negative edge breaks that assumption, so a vertex can be settled at the wrong distance and never revisited. Bellman-Ford handles negative weights by relaxing all E edges V-1 times in O(V*E), and a further relaxation pass that still improves something proves a negative cycle exists. If the graph is a DAG, relaxing edges in topological order is O(V + E) and handles negatives too.

Floyd-Warshall computes shortest paths between every pair of vertices with three nested loops over an intermediate vertex k, in O(V^3) time and O(V^2) space. It handles negative edges and detects negative cycles as a negative value on the diagonal. Use it when the graph is small and dense and you need all pairs; for sparse graphs, running Dijkstra from each source is usually faster.

A minimum spanning tree is a subset of edges that connects every vertex of a weighted undirected graph with no cycles and the smallest possible total weight. For a graph with V vertices it always contains exactly V-1 edges, and it exists only if the graph is connected. It answers questions like the cheapest way to lay cable or road between every site.

Kruskal sorts all edges by weight and adds each one unless it would create a cycle, using union-find to check — O(E log E), and it works naturally on a disconnected graph by producing a forest. Prim grows a single tree from a starting vertex, always adding the cheapest edge leaving the tree, using a min-heap — O(E log V). Kruskal is the better fit for sparse graphs and edge lists; Prim wins on dense graphs, where with an adjacency matrix it can run in O(V^2).

In an undirected graph, a connected component is a maximal set of vertices reachable from one another, found by running BFS or DFS from every unvisited vertex in O(V + E). In a directed graph the equivalent is a strongly connected component, where every vertex must reach every other following edge directions. Those need Kosaraju's two-pass algorithm or Tarjan's single-pass low-link algorithm, both still O(V + E).

A stable sort preserves the relative order of elements that compare equal. It matters because it lets you sort by several keys in sequence — sort by name, then by department, and equal departments stay alphabetized by name. Merge sort, insertion sort, and Timsort are stable; quicksort and heap sort are not, which is why Java uses Timsort for objects and a dual-pivot quicksort for primitives, where stability is unobservable.

An in-place sort rearranges the data using only O(1) or O(log n) extra memory beyond the input, rather than allocating a second array. Quicksort, heap sort, insertion sort, and selection sort are in-place; standard merge sort is not, since it needs an O(n) buffer to merge into. This is the main reason merge sort loses to quicksort in memory-constrained settings despite its better worst case.

Bubble sort repeatedly walks the array swapping adjacent out-of-order pairs, so the largest remaining element bubbles to the end on each pass, giving O(n^2) comparisons and O(n^2) swaps. With an early-exit flag it detects an already-sorted array in O(n). It survives only as a teaching example: insertion sort does the same work with far fewer writes and is the algorithm real libraries fall back to on small inputs.

Selection sort scans the unsorted remainder for the minimum and swaps it into position, which is O(n^2) comparisons regardless of input but only O(n) swaps — useful when writes are expensive, as on flash memory. Insertion sort instead shifts elements to slot each new value into the sorted prefix, which is also O(n^2) worst case but O(n) on nearly sorted data. Selection sort is unstable in its standard swap form; insertion sort is stable.

Its cost is proportional to the number of inversions, so an already-sorted array takes O(n) and a nearly sorted one is close to that. It is also in-place, stable, and has tiny constant factors with a sequential access pattern, which makes it faster than merge sort or quicksort below roughly 10 to 32 elements. That is exactly why production sorts switch to it for small subarrays, and why Timsort is built on runs of insertion sort.

Merge sort splits the array in half, recursively sorts each half, and merges the two sorted halves in linear time. It is O(n log n) in the best, average, and worst case, and it is stable — but it needs O(n) auxiliary space for the merge. Its predictability and stability make it the standard choice for sorting objects, linked lists, and data too large to fit in memory.

Quicksort picks a pivot, partitions the array so smaller elements sit left and larger sit right, and recurses on both sides. Average case is O(n log n) with excellent constants and O(log n) stack space, but if the pivot is consistently the smallest or largest element — as happens with a first-element pivot on already-sorted input — the partitions are maximally unbalanced and it degrades to O(n^2). It is in-place but not stable.

Both are O(n log n) on average, but quicksort partitions in place with sequential scans from both ends, so it touches memory in a cache-friendly pattern and does no allocation. Merge sort allocates an O(n) buffer and copies data back and forth, which costs bandwidth even though the comparison count is similar. The rule of thumb: quicksort for arrays of primitives, merge sort when you need stability or a guaranteed worst case.

Choose the pivot better — median-of-three, or a randomized pivot, which makes the bad case depend on the random seed rather than on the input. Recurse on the smaller partition and loop on the larger to bound stack depth at O(log n). Production implementations go further with introsort: they count recursion depth and switch to heap sort once it exceeds about 2 log n, which caps the worst case at O(n log n) while keeping quicksort's speed.

A comparison sort can be modeled as a decision tree where each internal node is one comparison and each leaf is one of the n! possible orderings. A binary tree with n! leaves has height at least log2(n!), and by Stirling's approximation that is Omega(n log n). So any algorithm that learns about the data only by comparing pairs needs at least that many comparisons in the worst case.

They sidestep the comparison lower bound by using the values themselves as indices. Counting sort is O(n + k) for integers in a small known range k, radix sort is O(d * (n + k)) for d-digit keys, and bucket sort is O(n) on average for values uniformly distributed over a known interval. The catch is that they need extra memory proportional to the key range and only apply to keys you can bucket — they are useless for arbitrary comparable objects, and counting sort on 64-bit integers would allocate an impossible array.

Python's sorted and Java's Arrays.sort for objects use Timsort, a stable hybrid that finds existing runs, extends short ones with insertion sort, and merges them — it is O(n) on already-sorted data, which is common in the real world. C++'s std::sort uses introsort: quicksort, insertion sort for small ranges, and a heap sort fallback when recursion goes too deep. The pattern to notice is that every real implementation is a hybrid, because each pure algorithm loses in some regime.

Binary search repeatedly halves the search interval by comparing the target against the middle element, giving O(log n) time and O(1) space in the iterative form. It requires random access and a sorted collection — on a linked list you lose the O(1) midpoint, and on unsorted data the comparison tells you nothing. If you must sort first, the O(n log n) sort dominates, so binary search only pays off across many searches.

When the data is unsorted and you are searching once, since sorting to enable binary search costs more than the single O(n) scan. It is also better on very small collections, where binary search's branch mispredictions outweigh the fewer comparisons, and on linked structures with no random access. Linear search also works on any iterable, including a stream you cannot rewind.

Computing the midpoint as (low + high) / 2 can overflow on large indices; use low + (high - low) / 2 instead. The loop condition must match the interval convention — while (low <= high) with an inclusive high, while (low < high) with an exclusive one — and mixing them causes an infinite loop or a missed last element. Failing to move a bound past the midpoint in one of the branches is the other common way to hang the loop.

Instead of returning on a match, record the index and keep searching the left half for the first occurrence, or the right half for the last. This is the lower-bound and upper-bound pattern that most standard libraries expose directly — bisect_left and bisect_right in Python, lower_bound and upper_bound in C++. It stays O(log n), and subtracting the two bounds gives the count of occurrences in the same time.

At every step, one of the two halves around the midpoint is guaranteed to be sorted; identify which by comparing the midpoint against the low element, then check whether the target falls inside that sorted half and discard the other. That preserves O(log n). With duplicates the comparison can become ambiguous, and the worst case degrades to O(n) — say so, because it is the follow-up the interviewer is waiting for.

When the answer is a number and there is a monotonic predicate — a feasibility check that is false up to some threshold and true after it — you can binary search the answer space instead of an array. Problems like the minimum capacity to ship packages in D days, or splitting an array to minimize the largest sum, become O(n log(range)) with a linear feasibility check inside the loop. The skill being tested is recognizing the monotonicity, not writing the search.

Recursion is a function solving a problem by calling itself on a smaller instance. Every recursive function needs a base case that returns without recursing, and a recursive case that provably moves toward that base case. Missing or unreachable base cases are what produce infinite recursion and a stack overflow, so state the base case first when you write one in an interview.

Recursion mirrors the structure of self-similar problems — trees, divide and conquer, backtracking — so the code is shorter and closer to the definition. Iteration avoids call overhead and uses O(1) stack rather than O(depth), so it cannot overflow. Any recursion can be rewritten iteratively with an explicit stack; do it when the depth can grow with the input, and keep the recursion when the depth is bounded by log n.

Each call pushes a frame holding parameters, locals, and the return address, and the thread stack is a fixed size — around 512KB to 1MB by default — so recursion deeper than a few thousand frames exhausts it. Python compounds this with a default recursion limit near 1,000. Avoid it by converting to iteration with an explicit stack, by reducing depth (recursing on the smaller half), or by processing the data in chunks; raising the limit only postpones the crash.

A call is tail recursive when the recursive call is the very last operation, so the current frame has nothing left to do and could be reused instead of pushed. Compilers for functional languages, and C and C++ compilers at higher optimization levels, do exactly that, turning the recursion into a loop with O(1) stack. Java, Python, and JavaScript engines in practice do not guarantee it, so tail recursion still overflows there — which is why depth matters more than form on the JVM or in CPython.

Backtracking builds a solution incrementally and abandons a partial candidate as soon as it cannot possibly extend to a valid answer, then undoes the last choice and tries the next. Brute force enumerates every complete candidate and tests it at the end. The pruning is the whole point: N-Queens has 64-choose-8 board placements but backtracking explores only a few thousand nodes, because a conflicting queen kills an entire subtree immediately.

Recursively, at each index choose to include or exclude the element and recurse on the rest, appending a copy of the current path at every node — 2^n subsets, so O(n * 2^n) total. Iteratively, loop i from 0 to 2^n - 1 and treat the bits of i as an inclusion mask, which is the neatest version when n is at most about 20. For a multiset, sort first and skip a duplicate value unless it is the first at its recursion depth, or you will emit the same subset twice.

Backtrack by swapping each remaining candidate into the current position, recursing on the rest, and swapping back to restore state — O(n!) results and O(n) extra space beyond the output. The alternative uses a used[] flag array and builds the permutation in a path list, which is easier to adapt when duplicates must be skipped. Forgetting the undo step after the recursive call is the single most common bug in every backtracking problem.

Place one queen per row and recurse to the next row, trying each column and rejecting any that is attacked. Track attacked columns and both diagonals in hash sets or boolean arrays — a cell is on diagonal row minus column and anti-diagonal row plus column — so each safety check is O(1) rather than O(n). Undo the three marks when backtracking; the pruning is what turns an astronomically large search into something that solves n=8 instantly.

Dynamic programming solves a problem by breaking it into subproblems, solving each one once, and storing the result so it is never recomputed. It applies when the problem has overlapping subproblems and optimal substructure. The naive recursive Fibonacci is O(2^n) because it recomputes the same values exponentially many times; memoizing turns it into O(n), which is the whole idea in one example.

Overlapping subproblems means the same subproblem is reached many times through different recursion paths, which is what makes caching pay off — merge sort lacks this, so it is divide and conquer, not DP. Optimal substructure means an optimal solution to the whole is built from optimal solutions to its parts, which is what makes the recurrence valid. Both must hold: without overlap, memoization buys nothing; without optimal substructure, the recurrence is simply wrong.

Memoization is top-down: you write the natural recursion and cache results in a map or array, so only the subproblems actually reachable get computed. Tabulation is bottom-up: you fill a table in dependency order with loops, which avoids recursion overhead and stack depth and makes space optimization easy. Memoization is faster to derive in an interview and wins when the reachable state space is sparse; tabulation is usually faster and safer to run.

A greedy algorithm makes the locally best choice at each step and never reconsiders it. It is fast — usually one pass, often after a sort — and uses little memory, but it is only correct when the problem has the greedy-choice property, meaning a locally optimal choice is always part of some globally optimal solution. Dijkstra, Kruskal, Prim, and Huffman coding are greedy algorithms with proofs behind them.

Try greedy first because it is cheaper, then look hard for a counterexample; if you can construct an input where the locally best choice forces a worse global outcome, you need DP. Coin change is the standard illustration: greedy is correct for denominations like 1, 5, 10, 25, but for coins 1, 3, 4 making 6 it picks 4+1+1 when 3+3 is optimal. Greedy commits, DP explores every combination and keeps the best — which is why greedy is usually O(n log n) and DP polynomial in the state space.

Define dp[i][w] as the best value using the first i items within capacity w, and for each item take the better of skipping it or taking it plus dp[i-1][w - weight]. That is O(n*W) time and O(n*W) space, reducible to O(W) by keeping one row and iterating capacity downwards so each item is used at most once. Note that O(n*W) is pseudo-polynomial, not polynomial, because W is a value rather than an input length — the problem is NP-hard.

In fractional knapsack you can take any portion of an item, so sorting by value-per-weight and filling greedily is provably optimal — the last item is simply cut to fit, and no better arrangement exists. In 0/1 you must take an item whole, so a high-density item can block a combination that fills the sack more completely. That indivisibility is exactly what removes the greedy-choice property and forces dynamic programming.

Build a table where dp[i][j] is the LCS length of the first i and first j characters: if the characters match it is dp[i-1][j-1] + 1, otherwise the max of dp[i-1][j] and dp[i][j-1]. That is O(n*m) time and space, and you recover the actual subsequence by walking back through the table. A subsequence need not be contiguous, which is what separates it from longest common substring, where a mismatch resets the cell to zero.

The straightforward DP sets dp[i] to the best subsequence ending at i by scanning every earlier element, which is O(n^2). The O(n log n) version maintains an array of the smallest possible tail for each length and binary searches each new value into it, replacing the first tail that is greater or equal. That tails array is not itself a valid subsequence — only its length is meaningful — so reconstructing the actual sequence needs a parallel parent array.

For the minimum number of coins, define dp[amount] as one plus the best over every coin that fits, initialized to infinity with dp[0] = 0, giving O(amount * coins). For the number of distinct combinations, loop coins on the outside and amounts on the inside — swapping the loop order counts permutations instead, which is the single most common mistake in this problem. Greedy fails on arbitrary denominations, so DP is required.

Edit distance, or Levenshtein distance, is the minimum number of single-character insertions, deletions, or substitutions to turn one string into another. The recurrence: if the characters match, take dp[i-1][j-1]; otherwise take one plus the minimum of the three neighboring cells representing delete, insert, and substitute. It is O(n*m) time and space, reducible to O(min(n,m)) space if you only need the number, and it powers spell-checkers and fuzzy search.

Kadane finds the maximum sum of a contiguous subarray in one O(n) pass with O(1) space: keep a running sum, reset it to the current element whenever the running sum turns negative, and track the best value seen. It is dynamic programming in disguise — the running sum is the best subarray ending at the current index. Handle the all-negative case explicitly, since initializing the answer to zero would wrongly return zero rather than the largest single element.

If each row of the table depends only on the previous row, keep two rows and swap them, or a single row updated in the correct direction — dropping O(n*m) to O(m). Knapsack is the canonical case: iterate capacity downwards to reuse one array while still allowing each item once. The trade-off is that you lose the full table, so you can no longer reconstruct the chosen solution, only its value — mention that, because it is the reason the optimization is not always applied.

Both split a problem into subproblems, but divide and conquer's subproblems are disjoint, so nothing is ever recomputed and no cache is needed — merge sort and binary search are the examples. Dynamic programming applies when the subproblems overlap, so storing results is what turns exponential work into polynomial. If you memoize a divide-and-conquer algorithm you gain nothing but memory overhead.

Match the structure to the operations you do most often. If you need fast key-based lookups, reach for a hash table; if you need sorted order with fast search, a balanced BST or sorted array; if you repeatedly need the smallest or largest item, a heap; and if you need LIFO or FIFO processing, a stack or queue. Always weigh the time complexity of the critical operations against the memory the structure consumes.

In the context of program memory, the stack is a region that stores function call frames, local variables, and return addresses, managed automatically in LIFO order and very fast to allocate. The heap is a larger region for dynamically allocated memory that lives beyond a single function call and must be managed manually or by a garbage collector. This memory heap is unrelated to the heap data structure, which is a tree-based priority queue, and interviewers sometimes ask the question to check that you know the difference.

Combine a hash map from key to node with a doubly linked list ordered by recency. The map gives O(1) lookup, and because you hold the node you can unlink and move it to the head in O(1); eviction removes the tail. A singly linked list would not work, because unlinking a node requires its predecessor. This pairing of two structures to get the best operation from each is the reason the question is asked so often.

A trie, because it stores keys by prefix, so finding every completion is one O(m) walk to the prefix node followed by a traversal of its subtree. Storing the top few suggestions per node, or pairing the trie with a heap, avoids traversing a huge subtree for a short prefix. A hash map is the wrong choice here — it can confirm an exact key in O(1) but has no way to answer "everything starting with these letters" short of a full scan.

Keep a dynamic array of the values plus a hash map from value to its index in that array. Insert appends and records the index; getRandom picks a uniform random index; delete swaps the target with the last element, fixes that element's index in the map, and pops the tail. The swap-with-last trick is the whole answer — it avoids the O(n) shift that a plain array deletion would cost.

Restate the problem and confirm the constraints and edge cases before writing anything — input size decides whether O(n^2) is acceptable or you need O(n log n). Say the brute-force solution out loud with its complexity, then look for the structure that removes the repeated work: a hash map to turn a search into a lookup, sorting to enable two pointers, a heap for repeated extremes, memoization for overlapping subproblems. Then code it, and walk one small example plus one edge case through it before saying you are done.