What actually gets asked

Big-O describes asymptotic growth as n grows large, so the dominant term decides how the cost scales; constants and lower-order terms become negligible in that limit. 3n + 5 and n both grow linearly, so both are O(n). The point is to compare how algorithms scale, not to predict exact wall-clock time.

Naive fib(n) = fib(n-1) + fib(n-2) is O(2^n) (more precisely O(φ^n)) because each call spawns two more and the recursion tree's size roughly doubles per level, recomputing the same subproblems exponentially many times. Memoizing the results collapses it to O(n) time (each fib(k) computed once), and an iterative version is O(n) time with O(1) space. This is the canonical 'overlapping subproblems ⇒ use DP' example.

Sequential phases add, then you keep the dominant term: O(n) + O(n^2) = O(n^2), because the quadratic term swamps the linear one as n grows. When a phase depends on a different input size m, you cannot fold it into n — the honest answer is O(n^2 + m), keeping both variables because either could dominate depending on the inputs.

Combined it's O(n log n) — the sort dominates the linear scan, so the scan is effectively absorbed, but the sort is certainly not free; it sets the overall complexity. A common mistake is to advertise 'an O(n) two-pointer solution' while quietly sorting first, which makes the real cost O(n log n). Always fold the preprocessing cost into the bound you quote.

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!). The split that matters most in interviews is polynomial (everything up to O(n^2)) versus exponential/factorial (O(2^n), O(n!)), which become intractable for even modest n. Knowing where a candidate algorithm sits on this ladder is usually the first thing an interviewer wants.

~100x slowdown for 100x data is linear, O(n). A ~10,000x slowdown is 100^2, i.e. O(n^2) — the quadratic term means scaling the input scales the cost by the square. This back-of-envelope reasoning is exactly how you sanity-check whether a measured slowdown matches your assumed complexity.

It's O(log n). Multiplying i by 2 each iteration means i takes the values 1, 2, 4, 8, …, so the loop body runs about log2(n) times before i reaches n. Any loop where the counter is multiplied or divided by a constant factor (rather than added to) is logarithmic — this is the same shape as binary search.

Big-O is an upper bound (grows no faster than), Big-Omega (Ω) is a lower bound (grows no slower than), and Big-Theta (Θ) is a tight bound (both at once). Strictly, an O(n) algorithm is also O(n^2) because O is only an upper bound, so the precise claim is usually Θ(n). In interviews people say 'O(n)' loosely to mean the tight bound; it's fine, but knowing the distinction signals rigor.

Yes, it's O(n^2) — even though the inner loop doesn't always run n times. The total iterations are 0 + 1 + 2 + … + (n-1) = n(n-1)/2, which is ~n^2/2; dropping the constant gives O(n^2). The lesson: a triangular nested loop is still quadratic, because half of a square is still proportional to n^2.

Best/average/worst describe how cost varies across different inputs of the same size. Interviewers usually mean worst-case Big-O because it's the guarantee that holds regardless of input, but average case matters for things like quicksort (avg O(n log n), worst O(n^2)) and hash maps (avg O(1), worst O(n)). Good practice: state worst-case first, then add the expected/average case with the assumption it relies on.

Amortized cost is the average cost per operation across a long sequence, even if individual operations vary. A dynamic array doubles capacity on resize, so a resize costs O(n) but only happens after ~n cheap appends; spreading that O(n) over the n appends gives O(1) per append on average. The doubling (geometric growth) is what makes the total work across n appends O(n), not O(n^2).

Halving n each call with O(1) work per level gives O(log n) time (about log2(n) levels). Space is O(log n) too because the call stack holds one frame per level until the base case unwinds — a point candidates often miss when they say O(1) space. This is the binary-search recursion shape.

Nesting doesn't automatically mean O(n^2) — what matters is total iterations. In a sliding-window or two-pointer pass, the inner pointer advances monotonically and never resets, so across the whole run it moves at most n times total: the two loops combined do O(n) work. Always count how many times the inner body actually runs, not how deeply the loops nest.

Big-O hides constants and cache effects, so for small or medium n a higher-Big-O algorithm with a tiny constant often wins. Classic cases: insertion sort (O(n^2)) beats quicksort on tiny arrays — which is why Timsort/introsort fall back to it; linear scan of a contiguous array can beat a hash map for small n because of cache locality and no hashing overhead; and an O(n log n) algorithm with huge constants can lose to a well-tuned O(n^2) until n is large. The honest senior answer is 'Big-O tells you scaling behavior; profile to know the crossover point for your actual n.'

It's a time/space trade-off driven by constraints: if memory is tight (embedded, huge inputs, streaming) favour the O(1)-space version; if latency dominates and memory is cheap, take the O(n)-time version. The strong-signal answer names the constraints out loud, states the assumption (e.g. input fits in memory), and asks the interviewer about input size and environment rather than guessing.

The hash map gives O(1) lookup from key to its node; the doubly linked list gives O(1) reordering — unlink a node from anywhere and move it to the front/back using its prev/next pointers. Neither alone suffices: a hash map has no order, and a list alone needs O(n) to find a node. Together they back an LRU cache where both get and put (including evicting the least-recently-used entry) are O(1). The doubly-linked part is essential because unlinking an interior node in O(1) requires knowing its predecessor, which only a backward pointer provides.

Arrays are contiguous: O(1) random index access but O(n) to insert/delete in the middle (shifting). Linked lists give O(1) insert/delete at a known node or the ends, but O(n) to find or index because you must walk the pointers. Reach for an array when you index a lot and the size is roughly known; reach for a linked list when you constantly add/remove at the front (or splice known nodes) and rarely index.

Walk both lists with a dummy head and a tail pointer: at each step append the smaller of the two current nodes and advance that list; when one list runs out, append the remainder of the other. O(n + m) time, O(1) extra space because you splice existing nodes rather than allocate new ones. The dummy node removes the special case for choosing the very first node.

A singly linked list has only a next pointer per node (forward traversal only); a doubly linked list adds a prev pointer, enabling backward traversal and O(1) deletion of a node given only a reference to it. The cost is one extra pointer of memory per node plus more bookkeeping on every insert/delete (you must fix two links, not one). Choose doubly when you need to walk backward or splice out arbitrary nodes cheaply (LRU caches, browser history); choose singly to save memory when forward-only suffices.

A stack is LIFO — last in, first out — used for undo, call stacks, DFS, and expression parsing. A queue is FIFO — first in, first out — used for task/work queues and BFS. A deque is double-ended, O(1) push/pop at both ends, used when you need front-and-back access (and as a faster substitute for inserting at index 0 of an array).

Iterate with three pointers — prev, curr, next — and on each step reverse the link (curr.next = prev) then advance all three; return prev at the end. This is O(n) time, O(1) space. The recursive version is O(n) space due to the call stack, so mention the iterative one first.

Push each opening bracket onto a stack; on a closing bracket, pop and check it matches the expected opener, failing fast on mismatch or empty stack. At the end the string is valid only if the stack is empty. O(n) time, O(n) space — the classic motivating example for why stacks exist.

Use the fast/slow pointer trick: advance slow by one and fast by two each step; when fast reaches the end, slow sits at the middle. It's O(n) time, O(1) space, and finishes in a single pass — no need to first count the length and then walk halfway. For an even-length list, decide up front whether you return the first or second middle (the fast/fast.next loop condition controls this).

Advance a fast pointer n nodes ahead, then move fast and slow together until fast hits the end — now slow is just before the node to remove, so you splice it out. Use a dummy head in front of the real head so removing the first node needs no special case. One pass, O(n) time, O(1) space.

A ring buffer is a fixed-size array with head and tail indices that wrap around using modulo; you enqueue at tail and dequeue at head, both O(1), reusing slots instead of shifting. It's ideal for bounded producer/consumer streams — audio/IO buffering, recent-event logs, fixed-window rate limiting — where memory must be capped and old data can be overwritten. The classic subtlety is distinguishing full from empty when head == tail (track a size/count or leave one slot unused).

Use a monotonic decreasing stack of indices: scan left to right, and while the current temperature exceeds the temperature at the stack's top index, pop it and record the gap (current index − popped index) as its answer. Push the current index. Each index is pushed and popped at most once, so it's O(n) time, O(n) space — far better than the O(n^2) double loop. The stack pattern answers 'next greater element' style questions generally.

Use Floyd's tortoise-and-hare: a slow pointer moves one step and a fast pointer two steps; if they ever meet there's a cycle, and if fast reaches null there isn't. O(n) time, O(1) space. A hash set of visited nodes also works but costs O(n) space, so lead with Floyd's.

Keep a second 'min stack' that records the running minimum in parallel with the main stack; on push you store min(value, currentMin), and on pop you pop both. Every operation stays O(1) time and the structure uses O(n) extra space. The key idea is that each level remembers the min as of when it was pushed, so popping restores the previous min for free.

Inserting at index 0 forces every existing element to shift one slot right, which is O(n) per insert. If you frequently add/remove at the front, use a deque (or a linked list), which gives O(1) push/pop at both ends. This is a common hidden-quadratic bug: building a result by repeatedly inserting at the front of an array turns an O(n) loop into O(n^2).

Keep an in stack for pushes and an out stack for pops; when out is empty, pour everything from in into out, which reverses the order and exposes the oldest element. Each element is moved at most once between stacks, so dequeue is amortized O(1) even though a single transfer is O(n). This is a clean test of whether a candidate understands LIFO-vs-FIFO and amortized cost.

Put every number in a hash set for O(1) membership, then for each number x start counting a run only if x - 1 is absent (so x is a sequence start); from such a start, extend x, x+1, x+2, … while present and track the longest. Starting only at run-beginnings means each number is visited O(1) times overall, giving O(n) time, O(n) space — beating the O(n log n) sort-then-scan.

A hash map places a key in a bucket derived from its hash; if you mutate a key after insertion so its hash changes, the entry is now in the 'wrong' bucket and lookups silently fail to find it. The equals/hashCode contract is the rule that ties them together: if two objects are equal they must have the same hash code, and equal objects must stay equal — so keys should be immutable (or at least their hash-relevant fields must be). Override hashCode whenever you override equals, or hash-based collections break.

A hash function maps a key to a bucket index, so with a good hash and a reasonable load factor most buckets hold ~1 entry and lookup is average O(1). The worst case is O(n) when many keys collide into the same bucket (bad hash, adversarial keys, or everything hashing the same), degrading a bucket into a linear scan. The O(1) is therefore an expected/average bound, not a guarantee.

A hash set stores keys only and answers 'have I seen this?' — use it for membership, dedup, and presence checks. A hash map stores key→value associations — use it when you also need data attached to each key (counts, indices, last-seen position). Both give average O(1) ops; a set is essentially a map whose values you don't care about. Reach for the map the moment you need to remember *something about* each key, not just *that* you saw it.

Walk the array once, inserting each value into a hash set; if a value is already present, return true immediately, otherwise return false at the end. O(n) time, O(n) space. Alternatively sort first and check adjacent equal pairs for O(n log n) time and O(1) extra space — a clean time/space trade-off to mention.

Walk the array once, and for each value x check a hash map for target - x; if present you've found the pair, otherwise store x -> index and continue. This is O(n) time, O(n) space — the canonical 'use a hash map to remember what you've seen' problem. The brute-force double loop is O(n^2); the hash map trades space for that speedup.

Make one pass to build a hash map (or 26-length array) of character counts, then a second pass over the string returning the index of the first character whose count is 1; return -1 if none. Two linear passes, O(n) time, O(1) space if the alphabet is fixed (at most 26/128 entries). The second pass must walk the original string order, not the map, because a map has no positional order.

Entries are placed by hash value into buckets, so iteration order reflects the internal bucket layout — which changes with the hash function, capacity, and resizes — not insertion or sort order. If you need a stable order, use an insertion-ordered map (Java's LinkedHashMap, Python's dict since 3.7) for insertion order, or a tree/sorted map (TreeMap, C++ std::map) for key-sorted order at O(log n) per op. Never rely on a plain hash map's iteration order; it's an implementation detail that can differ across runs or versions.

Separate chaining stores colliding keys in a per-bucket list (or tree, as Java 8+ does past a threshold), so it tolerates high load factors but pays pointer/indirection overhead. Open addressing keeps everything in the array and probes for the next free slot (linear/quadratic probing, double hashing); it's cache-friendlier but degrades sharply as load factor approaches 1 and complicates deletion. The choice trades memory locality against sensitivity to load factor.

Load factor is entries divided by buckets — a measure of how full the table is (Java's HashMap defaults to 0.75). When it's exceeded the table resizes: capacity roughly doubles and every key is rehashed into the larger array, an O(n) operation that happens rarely, keeping amortized insert O(1). A higher load factor saves memory but raises collision rates and slows lookups; a lower one wastes space.

Use a hash map keyed by a canonical form of each word and collect words sharing a key. The canonical key is either the sorted characters (O(k log k) per word) or a 26-length character-count signature (O(k) per word); the latter is faster for long strings. Total time is about O(n*k), space O(n*k). The trick the interviewer is probing is choosing a good collision-free key.

Track a running prefix sum and a hash map of how many times each prefix sum has occurred; at each index, the count of subarrays ending here equals the number of earlier prefix sums equal to prefixSum - k. Seed the map with {0: 1} to count subarrays starting at index 0. This is O(n) time, O(n) space, versus the O(n^2) brute force.

A hash map gives no ordering, so it's wrong when you need sorted iteration, the min/max, or range queries ('all keys between A and B'). For those, use an ordered/tree-based map (red-black tree, like Java's TreeMap or C++ std::map) giving O(log n) ordered operations, or a heap when you only need the extreme. Hash maps shine for pure key lookup, dedup, and frequency counting.

A good hash function distributes keys uniformly across buckets, is fast to compute, and is deterministic — minimizing collisions so buckets stay ~O(1). Hash flooding is a denial-of-service attack where an adversary crafts many keys that all hash to the same bucket, collapsing every lookup/insert to O(n) and the whole table to O(n^2) work — historically used to DoS web servers via crafted POST/query parameters. Defenses include per-process randomized/seeded hashing (SipHash) so an attacker can't predict the bucket, and converting long collision chains into balanced trees (Java 8+ does this).

Combine a dynamic array (for O(1) random access by index) with a hash map from value to its index in the array. Insert appends and records the index; delete swaps the target with the last element, pops the tail, and fixes the moved element's index; getRandom picks a random array index. The swap-with-last trick is what keeps delete O(1) instead of O(n).

Recurse: if the current node is null or equals either target, return it; otherwise recurse left and right. If both sides return non-null, the current node is the LCA (the targets split here); if only one side does, propagate that side up. O(n) time, O(h) stack space. If it's specifically a BST, you can do better: walk down, going left when both targets are smaller and right when both are larger — the first node that splits them is the LCA, O(h) time.

In a BST every node's left subtree holds only smaller keys and its right subtree only larger keys, so an in-order traversal yields sorted order. Search/insert/delete are O(log n) when the tree is balanced (height ~log n) but degrade to O(n) when it degenerates into a linked-list shape (e.g. inserting already-sorted data). That fragility is exactly why self-balancing variants exist.

Run BFS with a queue: at each step record the current queue size (that's one full level), then dequeue exactly that many nodes, collect their values into a level list, and enqueue their children. Repeat until the queue empties. O(n) time, O(width) space. Snapshotting the queue size per round is the trick that cleanly separates one level from the next.

A binary heap is a complete tree (stored in an array) maintaining the heap property — each parent is <= (min-heap) or >= (max-heap) its children — so the extreme element sits at the root. Peek-min/max is O(1); insert and extract are O(log n) because you sift up/down one level at a time. It's the go-to for top-K, scheduling, Dijkstra, and merging K sorted streams.

Preorder (node, left, right) visits the root first — good for copying/serializing a tree. Inorder (left, node, right) yields sorted order in a BST — good for validation and producing ordered output. Postorder (left, right, node) visits children before the parent — good for deletion and bottom-up aggregates like subtree sums/heights. Level-order is BFS with a queue, processing tier by tier — good for shortest-depth and 'by level' problems. The first three are DFS (recursion or stack); level-order is BFS (queue).

Do a single postorder DFS that returns each node's height while updating a global max: at each node, the longest path *through* it is leftHeight + rightHeight (in edges), so track the maximum of that across all nodes and return 1 + max(leftHeight, rightHeight) to the parent. O(n) time, O(h) stack. The key insight is that the answer is a path that bends at some node, computed from its two subtree depths.

A trie answers prefix queries — 'all words starting with "pre"', autocomplete, longest-prefix matching — which a hash map cannot do without scanning every key, and it shares storage for common prefixes. Lookups are O(m) in the word length, independent of how many words are stored. The catch is memory: each node carries a child map/array (up to alphabet size), so a sparse trie can use far more memory than a hash set of the same words, and it's only worthwhile when prefix operations matter.

Do an inorder traversal (which visits BST keys in ascending order) and stop at the kth visited node — you don't need to traverse the whole tree. An iterative inorder with an explicit stack lets you halt early at O(h + k) time. If the tree is queried for many different k values, augment each node with its left-subtree size so each query becomes O(h) by navigating directly.

Recurse with a valid (min, max) range for each node: the root is unbounded, the left child tightens the max to the parent's value and the right child tightens the min. A node fails if its value violates its range. O(n) time, O(h) stack space. Equivalently, an in-order traversal of a valid BST is strictly increasing, so you can check that the previous visited value is always smaller.

Self-balancing BSTs perform rotations on insert/delete to keep height O(log n), guaranteeing O(log n) operations regardless of input order. AVL trees keep height balance tighter (faster lookups, more rotations); red-black trees balance more loosely (fewer rotations, faster writes). They back ordered maps/sets such as Java's TreeMap and C++ std::map, and red-black trees appear in the Linux process scheduler.

Each node holds a map/array of child links and an isEnd flag; insert walks/creates a path of nodes one character at a time, search walks the path and checks isEnd, and startsWith walks the path without requiring isEnd. All three are O(m) for a word of length m, independent of how many words are stored. Tries shine for autocomplete, spellcheck, and prefix-heavy lookups where a hash map can't answer prefix queries.

Maintain a min-heap of size k: push each element, and whenever the heap exceeds k pop the smallest, so the heap ends holding the k largest with the kth largest at its root. That's O(n log k) time, O(k) space. Quickselect gives average O(n) by partitioning around a pivot and recursing into only the relevant side, with O(n^2) worst case — mention both and the trade-off.

Bottom-up heapify (sift-down from the last internal node up to the root) is O(n), not O(n log n), because most nodes sit near the leaves and sift down only a tiny distance — summing the work weighted by height gives a convergent series bounded by O(n). (Inserting one-by-one with sift-up is the O(n log n) way.) Heapsort then builds a max-heap in place, repeatedly swaps the root (the max) with the last unsorted element and sifts down the reduced heap — O(n log n) time, O(1) extra space, but not stable.

B-trees are shallow and high-fanout — each node holds many keys, so the tree stays only a few levels deep even for millions of rows, which minimizes expensive disk seeks (disk I/O, not comparisons, is the bottleneck). A binary tree would be far taller and cost many more page reads. In a B+ tree all values live in the leaves, which are linked together, so range scans and ORDER BY can sweep the leaves sequentially without re-walking the tree.

Push the head of each list into a min-heap keyed by node value; repeatedly pop the smallest, append it to the result, and push that node's successor. Each of the n total nodes is pushed/popped once at O(log k) cost, giving O(n log k) time and O(k) heap space. Divide-and-conquer pairwise merging hits the same O(n log k) without a heap.

Union-find tracks elements partitioned into disjoint sets via a parent-pointer forest, supporting find (which set/root an element belongs to) and union (merge two sets). Path compression flattens the tree by pointing visited nodes straight at the root during find, and union by rank/size always attaches the smaller tree under the larger; together they make each operation nearly O(1) — amortized O(α(n)), the inverse-Ackermann function, effectively constant. It's the tool for dynamic connectivity, counting connected components, cycle detection in undirected graphs, and Kruskal's MST.

An adjacency list stores each node's neighbours, using O(V + E) space — efficient for sparse graphs, which is most real-world graphs. An adjacency matrix is a V x V grid giving O(1) edge-existence checks but O(V^2) space regardless of edge count, so it only pays off for dense graphs or when you constantly test specific edges. Default to the list unless the graph is dense.

BFS explores level by level using a queue and finds the shortest path in an unweighted graph (fewest edges); DFS dives deep along one branch using recursion or an explicit stack and suits connectivity, cycle detection, and topological sort. BFS uses O(width) memory, DFS uses O(depth). Choose BFS when you need shortest hops or level order; choose DFS when you need to fully explore structure or order dependencies.

Graphs can contain cycles and multiple paths to the same node, so without a visited set a traversal revisits nodes and, on a cycle, loops forever or explodes in work. A visited set makes both BFS and DFS O(V + E) by guaranteeing each node and edge is processed once. (Trees are the special case where you can skip it — they have no cycles.)

In a directed graph edges have a direction (Twitter 'follows'); in an undirected graph they go both ways (Facebook 'friends'). Weighted edges carry a cost or distance (road network with mileage); unweighted edges just record a connection (a maze of equal steps). These two axes determine your algorithm choice — e.g. unweighted shortest path uses BFS, weighted uses Dijkstra.

Way 1 — traversal: loop over all nodes; each time you hit an unvisited node, increment the count and BFS/DFS to mark its whole component visited. O(V + E). Way 2 — union-find: start with V components and union the endpoints of every edge; each successful merge of two distinct sets drops the count by one. O(E·α(V)). Union-find shines when edges arrive incrementally or you also need connectivity queries; traversal is simplest for a static graph.

Dijkstra greedily grows a set of finalized shortest distances: a min-heap repeatedly pops the closest unfinalized node, finalizes its distance, and relaxes its outgoing edges. With a binary heap it's O((V + E) log V). It relies on the assumption that once you finalize a node, no later path can be shorter — true only with non-negative weights. A negative edge can make a 'longer-looking' path actually cheaper after the node is already finalized, breaking correctness; for negative edges use Bellman-Ford (O(V·E)), which also detects negative cycles.

In an undirected graph, DFS finds a cycle if it reaches an already-visited node that isn't the immediate parent (or union-find: an edge joining two nodes already in the same set). In a directed graph a plain visited set is insufficient — you must track nodes currently on the recursion stack (often three colors: white/unvisited, gray/in-progress, black/done); a back edge to a gray node means a cycle. The difference is that in directed graphs revisiting a finished node is fine (it's just a shared descendant), whereas an edge back to an *in-progress* ancestor is the cycle.

Compute every node's in-degree, seed a queue with all in-degree-0 nodes (no dependencies), then repeatedly dequeue a node, append it to the order, and decrement its neighbors' in-degrees — enqueuing any that hit zero. O(V + E). If the emitted order contains fewer than V nodes, a cycle exists and no valid ordering is possible, so the same algorithm doubles as cycle detection. This is exactly Course Schedule II / dependency resolution.

Scan every cell; when you hit unvisited land, increment the island count and flood-fill (BFS or DFS) all connected land, marking it visited so you don't recount it. The grid is an implicit graph where each cell connects to its 4 neighbours. O(rows * cols) time and space. The core insight is recognizing a 2D matrix as a graph traversal.

Model courses as a directed graph and ask whether it has a cycle: if it does, the prerequisites are circular and you can't finish. Use Kahn's algorithm (BFS topological sort — repeatedly remove in-degree-0 nodes; if you can't remove them all, a cycle remains) or DFS cycle detection with a recursion-stack marker. O(V + E) time and space.

A topological sort is a linear ordering of a directed graph's vertices where every edge u->v has u before v — it exists if and only if the graph is a DAG (no cycles). Compute it with Kahn's algorithm (repeatedly emit in-degree-0 nodes) or via DFS finish times reversed. It models dependency resolution: build systems, task scheduling, course prerequisites.

Unweighted shortest path is plain BFS — the first time you reach a node is via the fewest edges, so it's optimal at O(V + E). With non-negative weights, BFS no longer works because fewer edges can cost more; switch to Dijkstra's algorithm, which uses a min-heap/priority queue to always expand the cheapest frontier node. The shift from a queue to a priority queue is the key recognition.

Traverse with BFS or DFS while keeping a hash map from original node to its clone. When you first see a node, create its clone and record it; then for each neighbor, create-or-look-up its clone and wire up the edge. The map serves double duty as both the visited set and the original→copy lookup, which is what prevents infinite loops on cycles. O(V + E) time and space.

Model each word as a graph node with edges to words differing by one letter, then run BFS from beginWord — the first time you reach endWord, the BFS depth is the shortest transformation length (unweighted shortest path). To find neighbors efficiently, use wildcard patterns like h*t as buckets so you don't compare every pair of words. BFS guarantees the shortest sequence; bidirectional BFS from both ends prunes the frontier and is a strong optimization to mention.

Backtracking is DFS over a decision tree: choose an option, explore by recursing, then un-choose (undo the change) before trying the next option. You hit a base case when a full candidate is built (record it) and prune by checking constraints *before* recursing — abandoning a branch the moment it can't lead to a valid solution. Pruning (e.g. skipping a queen placement under attack in N-Queens, or stopping when a partial sum exceeds the target) is what turns brute-force enumeration into something tractable.

Kadane's algorithm: scan once, maintaining curr = max(x, curr + x) (either start fresh at x or extend the running subarray) and tracking the best curr seen. O(n) time, O(1) space. The key decision at each element — extend the previous subarray or restart — is a one-line DP. Watch the all-negative case: initialize the answer to the first element (or -∞), not 0, so you don't wrongly return 0 for an empty subarray.

Recursion solves a problem by calling itself on smaller inputs until a base case stops the descent; each call pushes a frame onto the call stack and pops it on return. Without a correct base case (or with too-deep recursion) the stack grows until it overflows. Deep recursion on large inputs should be rewritten iteratively (or made tail-recursive where the language optimizes it) to use O(1) instead of O(depth) stack space.

The ways to reach step n equal the ways to reach n-1 (then a 1-step) plus the ways to reach n-2 (then a 2-step): ways(n) = ways(n-1) + ways(n-2) — the Fibonacci recurrence. Bottom-up DP keeping just the last two values gives O(n) time and O(1) space. Recognizing that the final move splits the problem into independent subproblems is the DP insight; the naive recursion without memoization is exponential.

Quicksort partitions around a pivot in place — average O(n log n), O(log n) stack space, but O(n^2) worst case on bad pivots and not stable. Mergesort splits and merges — guaranteed O(n log n) and stable, but needs O(n) extra space. Any comparison-based sort is bounded below by O(n log n) because there are n! possible orderings and each comparison yields one bit, so you need at least log2(n!) ~ n log n comparisons to distinguish them.

At each house you either skip it (carry forward the best so far) or rob it (its value plus the best up to two houses back): dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Keep just the two previous results for O(n) time, O(1) space. The greedy 'rob every other house' fails — the optimal choice depends on values, which is the cue for DP over greedy.

Use backtracking: at each index decide to include or exclude that element, recursing on the rest and recording the running subset at every node of the decision tree. There are 2^n subsets, so it's O(n·2^n) time (n to copy each subset) — inherent to the output size. An iterative alternative builds subsets by, for each new element, appending it to every subset seen so far. Passing a start index prevents revisiting earlier elements and generating duplicates.

Use prefix and suffix products: first pass fills each position with the product of everything to its left; second pass multiplies in the product of everything to its right (tracked in a running variable). O(n) time, O(1) extra space if the output array doesn't count. Division would be the obvious trick but is explicitly banned — and it breaks on zeros anyway, which is exactly why the prefix/suffix approach is the expected answer.

The cue is 'sorted (or monotonic) + find', or a search space you can halve by a yes/no test — binary search gives O(log n). In a rotated sorted array, at each midpoint one half is still sorted; check whether the target lies within that sorted half to decide which side to discard, keeping it O(log n). Binary search also hides in 'find minimum capacity/threshold' problems via binary-search-on-the-answer.

Two pointers fits sorted arrays and pair/triplet problems: move a left and right pointer inward based on a comparison (e.g. pair-sum, removing duplicates). Sliding window fits 'longest/shortest contiguous subarray or substring satisfying a constraint': grow the right edge and shrink the left when the constraint breaks. Both turn an O(n^2) brute force into O(n) by never resetting the pointers backwards.

Slide a window with two pointers, tracking the characters currently inside in a hash set/map; when the right pointer hits a duplicate, advance the left pointer (removing characters) until the window is valid again, recording the max length along the way. Each character enters and leaves the window at most once, so it's O(n) time, O(min(n, alphabet)) space. The classic sliding-window-plus-hashing problem.

DP applies when a problem has overlapping subproblems (the same smaller problem recurs) and optimal substructure (the best answer is built from best sub-answers) — counting paths, min cost, longest subsequence are typical. Memoization is top-down: write the natural recursion and cache results. Tabulation is bottom-up: fill a table in dependency order, avoiding recursion overhead. Both cut exponential brute force to polynomial; choose based on which is clearer.

This is bottom-up DP: dp[a] = fewest coins to make amount a, computed as 1 + min over coins c of dp[a - c], with dp[0] = 0 and unreachable amounts marked infinity. Answer is dp[amount] or -1 if still infinity. O(amount * numCoins) time, O(amount) space. The interviewer is watching you state the subproblem and transition clearly — and notice that greedy (largest coin first) fails for denominations like {1, 3, 4}.

When the input isn't sorted but the answer space is monotonic — a candidate value either works or doesn't, and 'works' is monotone (if capacity X works, every larger capacity also works) — you binary-search over the range of possible answers, using a feasibility check as the comparison. Example: find the minimum eating speed so Koko finishes in H hours — binary-search the speed and test 'can she finish at speed k?' in O(n) each, giving O(n log(max)) overall. The trick is spotting the monotone yes/no boundary you can bisect.

Divide-and-conquer splits into independent subproblems and combines results (mergesort, binary search). DP is for overlapping subproblems with optimal substructure, caching to avoid recomputation. Greedy makes the locally optimal choice at each step and never revisits it — fast and simple, but only correct when the problem has the greedy-choice property (e.g. interval scheduling, Dijkstra, Huffman). You justify greedy with an exchange argument or by proving the greedy choice is always part of some optimal solution; otherwise fall back to DP.

401 Unauthorized means 'I don't know who you are' — no/invalid credentials; the right fix is to authenticate. 403 Forbidden means 'I know who you are, but you're not allowed' — re-authenticating won't help. 404 Not Found means the resource doesn't exist.

The security twist: a 403 on a resource you can't see still confirms it exists, leaking information (resource enumeration). Some APIs deliberately return 404 instead of 403 for unauthorized access to private resources, so an attacker can't distinguish 'exists but forbidden' from 'doesn't exist'.

Five families by first digit: 1xx informational, 2xx success (200 OK, 201 Created, 204 No Content), 3xx redirection (301 permanent, 302 found, 304 Not Modified), 4xx client error (400 bad request, 401 unauthenticated, 403 forbidden, 404 not found, 409 conflict, 422 unprocessable, 429 too many requests), 5xx server error (500 internal, 502 bad gateway, 503 unavailable).

The useful instinct: 4xx means the client must change the request; 5xx means the client can retry the same request later.

GET, PUT, DELETE, HEAD, and OPTIONS are idempotent: making the same call N times leaves the server in the same state as making it once. POST is not idempotent — two POSTs typically create two resources.

It matters for safe retries. When a client times out it cannot tell whether the request was processed, so it must retry. Idempotent methods can be retried freely; for non-idempotent POSTs you need an idempotency key so the server can dedupe.

HttpOnly hides the cookie from JavaScript (document.cookie), so an XSS payload can't read it — it mitigates token theft. Secure sends the cookie only over HTTPS, so it can't leak over plaintext. SameSite controls whether the cookie rides along on cross-site requests: Strict never sends it cross-site, Lax sends it only on top-level navigations (the modern browser default), and None sends it always but then requires Secure.

Together they harden a session cookie: HttpOnly+Secure stop theft and eavesdropping; SameSite is the first line of CSRF defense.

By the HTTP spec GET is safe (read-only) and idempotent, so intermediaries (browsers, proxies, CDNs) freely cache and retry it. But 'safe' is a *contract you must honor*, not something the protocol enforces — a poorly designed GET /delete?id=5 will happily delete data.

The danger: because GETs are prefetched, cached, and retried, a side-effecting GET can be triggered by a link prefetcher, a crawler, or a retry, causing unintended mutations. Mutations belong on POST/PUT/PATCH/DELETE; keep GET strictly read-only.

An ETag is an opaque validator (often a hash) the server attaches to a response to identify a specific version of a resource. On the next request the client sends If-None-Match: <etag>. If the resource is unchanged the server replies 304 Not Modified with no body, saving bandwidth; if it changed it returns 200 with the new body and a new ETag.

ETags also enable optimistic concurrency on writes via If-Match: the write is rejected with 412 Precondition Failed if someone else changed the resource first.

CORS (Cross-Origin Resource Sharing) is a browser security mechanism on top of the same-origin policy. By default a page at origin A cannot read responses from origin B unless B opts in via Access-Control-Allow-Origin.

For non-simple requests (custom headers, methods like PUT/DELETE, certain content types) the browser first sends a preflight OPTIONS request. The server answers with Access-Control-Allow-Methods, Allow-Headers, and Allow-Origin; only then does the browser send the real request.

TLS adds three things: confidentiality (traffic is encrypted), integrity (tampering is detected), and server identity (the certificate, signed by a CA, proves you are talking to the real host).

Handshake sketch: client sends ClientHello (supported ciphers); server returns its certificate and key-exchange parameters; they use asymmetric crypto (e.g. ECDHE) to agree on a shared symmetric session key; the rest of the connection uses fast symmetric encryption. TLS 1.3 cuts this to roughly one round trip.

PUT replaces the resource wholesale and is idempotent — send the full representation. PATCH applies a partial modification (only the changed fields) and is not guaranteed idempotent by spec. POST creates a new subordinate resource or triggers a non-idempotent action.

Rule of thumb: full replace at a known URL → PUT; partial field update → PATCH; create-and-let-the-server-assign-the-id → POST.

Keep-alive (persistent connections, default in HTTP/1.1) reuses one TCP connection for multiple sequential requests, avoiding a new handshake each time. But requests on that connection are still serialized — request 2 waits for response 1 (head-of-line blocking), which is why browsers open ~6 parallel connections per host.

HTTP/2 multiplexing interleaves many concurrent request/response streams over a single connection, so a slow response doesn't block the others at the application layer. Keep-alive reuses the pipe; multiplexing lets many requests share it simultaneously.

HSTS (HTTP Strict Transport Security) is a response header (Strict-Transport-Security: max-age=...) that tells the browser to only ever contact this host over HTTPS for the given duration — the browser upgrades any http:// request to https:// *before* sending it.

A plain 301 redirect from HTTP→HTTPS still sends that first request in cleartext, which a man-in-the-middle can intercept and strip (SSL stripping). HSTS closes that window because, after the first secure visit (or via the preload list), the browser never makes the insecure request at all.

When a client is about to send a large request body, it can send the headers first with Expect: 100-continue and pause before sending the body. The server inspects the headers (auth, content-length limits, content-type) and replies 100 Continue to greenlight the body, or an error status (e.g. 401, 413) to reject it up front.

The point is to avoid wasting bandwidth uploading a huge body that the server would only reject anyway. It's part of the 1xx informational family — a provisional response before the final one.

Caching is governed by Cache-Control (max-age, no-store, no-cache, private/public, must-revalidate), plus validators ETag/Last-Modified and the legacy Expires.

Debug path: inspect the response Cache-Control and Age headers; check whether an intermediary (CDN/proxy) added Age or an X-Cache: HIT. no-cache means 'revalidate before use', not 'do not cache' — that surprises people. To force freshness set no-store or a short max-age plus an ETag so clients revalidate cheaply with 304s.

HTTP/1.1 suffers head-of-line blocking: one response per connection at a time, so browsers open many TCP connections. HTTP/2 adds multiplexing (many concurrent streams over one connection), header compression (HPACK), and server push, removing application-layer HOL blocking.

But HTTP/2 still rides TCP, so a single lost packet stalls all streams (transport-layer HOL blocking). HTTP/3 runs over QUIC (UDP), giving independent streams, faster connection setup (0-RTT), and seamless connection migration across network changes.

GraphQL resolvers run per-field, per-object. Fetch a list of 10 authors and then ask for each author's posts, and the naive resolver fires 1 query for the authors + N queries for the posts — the classic N+1 blowup, which gets worse as clients nest deeper.

The standard fix is a DataLoader: it batches the individual post requests made within one tick of the event loop into a single WHERE author_id IN (...) query and caches results per request. This collapses N+1 into 2 queries while keeping the per-field resolver model.

It mixes RPC-style verb-in-the-path (getUserById) with REST, which is redundant and inconsistent. In REST the HTTP method is the verb and the URL names a resource (noun). So fetching user 5 is simply GET /users/5; the GET already says 'retrieve', and /users/{id} identifies the resource.

Proper resource modeling: GET /users (list), POST /users (create), GET /users/5, PUT/PATCH /users/5 (update), DELETE /users/5. Keep verbs out of paths and use plural nouns consistently.

Use the right status code to signal the category, then a structured body with a stable machine-readable code, a human message, and optional details/field-level errors. Keep the shape identical across every endpoint so clients can handle errors generically.

Example shape: { "error": { "code": "card_declined", "message": "Your card was declined.", "details": [] } }. Stable string codes (not just HTTP numbers) let clients branch on the specific failure without parsing prose. Never leak stack traces or internal identifiers.

Two core endpoints: POST /urls with the long URL returns a short code (201 + Location); GET /{code} issues a 301/302 redirect to the long URL.

Key decisions: generate the code via a base62 encoding of an auto-increment id or a hash (handle collisions); store code -> longURL in a fast KV store; cache hot codes (read-heavy workload). Discuss 301 (permanent, cacheable, loses analytics) vs 302 (temporary, every hit reaches you for click counts). Add rate limiting and custom-alias support as extensions.

Long polling holds an HTTP request open until there's data, then the client reconnects — works everywhere but is request-heavy and laggy. Server-Sent Events (SSE) is a one-way server→client stream over a single long-lived HTTP connection, with built-in auto-reconnect and event IDs — ideal for notifications, live scores, dashboards. WebSockets give a full-duplex bidirectional channel after an HTTP upgrade — needed when the client also pushes frequently (chat, collaborative editing, multiplayer).

Rule of thumb: server-push-only → SSE (simpler, rides plain HTTP); two-way/high-frequency → WebSockets; fallback when neither is available → long polling.

gRPC rides HTTP/2 (multiplexed, persistent connections) and serializes with Protocol Buffers — a compact binary format with a strict schema, so payloads are smaller and parsing is faster than text JSON. It also generates typed client/server stubs and supports streaming in both directions.

Downsides: it's not natively callable from browsers (you need gRPC-Web + a proxy); the binary payloads aren't human-readable, so debugging needs tooling; and it adds schema/codegen overhead. That's why gRPC dominates internal service-to-service traffic while REST/JSON stays the default for public, browser-facing APIs.

When throttling, return 429 Too Many Requests and tell the client *how* to behave. Limit headers expose the budget: a limit, the remaining count, and a reset time (GitHub uses X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset; the IETF RateLimit draft standardizes this). On a 429 (or 503) a Retry-After header tells the client exactly how long to wait.

This lets a good client self-throttle proactively — slow down as remaining approaches zero and back off precisely after a 429 — instead of blindly hammering and guessing.

REST: default for public CRUD over HTTP; cacheable, simple, ubiquitous. GraphQL: client picks exactly the fields it needs — kills over/under-fetching when many clients aggregate data from many resources; cost is caching and query-complexity control. gRPC: high-performance internal service-to-service calls over HTTP/2 + protobuf, with streaming; not browser-native. WebSockets: persistent bidirectional real-time channel (chat, live feeds, multiplayer).

Choose by traffic shape: public+cacheable → REST; flexible client queries → GraphQL; fast internal RPC → gRPC; push/real-time → WebSockets.

Offset/limit (LIMIT 20 OFFSET 10000) is simple but the database must scan and discard every skipped row, so deep pages get slow, and rows shifting between requests cause duplicates or skips.

Cursor/keyset pagination passes the last-seen sorted key (WHERE id > :lastId ORDER BY id LIMIT 20). It uses the index directly, so performance is constant regardless of depth, and it is stable under inserts. Tradeoff: you can't jump to an arbitrary page number. Use cursors for infinite scroll and large/active datasets.

Three common strategies: URI versioning (/v1/users) — explicit and cache-friendly, the most common; header versioning (Accept: application/vnd.api.v2+json) — cleaner URLs, harder to test in a browser; and query param (?version=2).

The deeper answer is to avoid breaking changes at all: add fields rather than remove, treat unknown fields as ignorable, never repurpose a field's meaning, and only bump the major version for genuinely incompatible changes. Announce deprecations with timelines and Deprecation/Sunset headers.

Don't process 10k records in a synchronous request — you'll hit timeouts and tie up a worker. Accept the payload, validate it cheaply, enqueue a background job, and return 202 Accepted with a job/status URL (Location: /imports/{id}). The client polls that URL (or subscribes) for progress and the final per-record outcome.

Key decisions: define partial-failure semantics (all-or-nothing transaction vs per-record results so 9,998 succeed and 2 errors are reported), make the import idempotent via a client-supplied batch key so retries don't double-import, and cap batch size with backpressure.

The client generates a unique key (e.g. a V4 UUID) and sends it in an Idempotency-Key header. The server stores the key with the request's outcome.

Logic: on first request for a key, process it and persist the resulting status + response body keyed by that idempotency key (inside the same transaction as the side effect). On any retry with the same key, return the stored response instead of re-charging. Handle the in-flight case (a retry arriving while the first is still processing) with a lock or a 409. Stripe expires keys after 24 hours. This turns a non-idempotent POST into a safely retryable one after a timeout.

The token bucket is the common default — a bucket refills tokens at a fixed rate up to a capacity; each request consumes a token, and an empty bucket means the request is rejected with 429 Too Many Requests (plus a Retry-After header). It allows short bursts while bounding the average rate. ByteByteGo notes both Amazon and Stripe use this algorithm to throttle their APIs.

Alternatives: leaky bucket (smooths to a constant outflow), fixed window (simple but allows 2x bursts at window edges), and sliding window (smooths the edge problem). For a distributed limiter, keep counters in a shared store like Redis (atomic INCR with TTL) so all nodes agree.

HATEOAS (Hypermedia As The Engine Of Application State) is the REST constraint where responses include links to the next available actions, so the client discovers transitions dynamically ({ "_links": { "cancel": "/orders/42/cancel" } }) instead of hardcoding URLs.

In practice it's the least-adopted REST constraint — most 'REST' APIs are really HTTP+JSON without hypermedia. Be honest in interviews: know what it is and the decoupling argument, but acknowledge most teams skip it because clients are coupled to the API anyway and tooling support is thin.

CSRF (Cross-Site Request Forgery) tricks a logged-in victim's browser into making a state-changing request to your site. The attacker hosts a page that auto-submits a form (or fires a request) to yourbank.com/transfer; because the browser automatically attaches the victim's cookies to any request to that origin, the request arrives authenticated — even though the attacker never read the cookie.

The core enabler is ambient authority: cookies ride along by default. Defenses: SameSite cookies (block cross-site sends), anti-CSRF tokens (a secret the attacker's page can't know), and checking Origin/Referer.

Authentication answers 'who are you?' — verifying identity (password, token, passkey). Authorization answers 'what are you allowed to do?' — checking permissions after identity is established.

Example: logging in with your password is authentication; the check that decides you can read but not delete the document is authorization. Authn always precedes authz. The corresponding status codes: 401 Unauthorized = not authenticated; 403 Forbidden = authenticated but not permitted.

A JWT is header.payload.signature, each base64url-encoded and joined by dots. The header names the algorithm; the payload holds the claims (sub, exp, roles); the signature is computed over header+payload with a secret (HMAC) or private key (RSA/ECDSA).

The signature guarantees integrity and authenticity — the server detects any tampering and confirms the token was issued by a holder of the key. It does not provide confidentiality: the payload is merely encoded, not encrypted, so anyone can base64-decode and read it. Never put secrets in a JWT payload, and always verify the signature server-side.

Sessions: server stores session state, the client holds an opaque session id in an HttpOnly cookie. Stateful, but revocation is trivial — delete the server-side session. Needs shared session storage to scale horizontally.

JWTs: a signed, self-contained token the server verifies without a lookup — stateless and scales easily. The catch is revocation: a valid JWT is honored until it expires, so logout/ban requires a denylist or short expiry + refresh tokens, which reintroduces state. Use short-lived access tokens (minutes) plus a refresh token to limit the blast radius.

OAuth 2.0 is delegated authorization: 'let app A access my data on service B' without sharing my password — it issues access tokens scoped to resources. It says nothing about who the user is.

OIDC (OpenID Connect) is an authentication layer built on top of OAuth2. It adds an ID token (a JWT) and a standard /userinfo endpoint, so the app learns *who* logged in — this is what powers 'Log in with Google'. So: OAuth2 = access to resources; OIDC = proof of identity.

Never store plaintext or reversible encryption. Use a slow, salted, adaptive password hash — bcrypt, scrypt, or Argon2 (the current OWASP-preferred). The salt (unique per user) defeats rainbow tables; the deliberate slowness/work factor caps how many guesses an attacker can make per second after a breach.

Fast general-purpose hashes (SHA-256, MD5) are wrong precisely because they're fast — a GPU computes billions per second, making offline brute force cheap. Choose a memory-hard function and raise the cost factor as hardware improves.

A stateless access token can't be revoked before it expires, so you want it to live only minutes — that bounds the damage if it leaks. To avoid forcing the user to log in every few minutes, a longer-lived refresh token (stored more securely, server-trackable) is exchanged for fresh access tokens.

This splits concerns: access tokens are stateless and fast to verify; refresh tokens are the revocable, stateful part. Add refresh token rotation (issue a new refresh token each use and invalidate the old one) so a stolen refresh token is detected on reuse.

This is the classic alg: none / algorithm-confusion vulnerability. The JWT header declares its own algorithm; if the verifier trusts that field, an attacker sets alg: none (or strips the signature) and the library skips verification, accepting a payload they forged (role: admin). A related attack swaps RS256 for HS256, signing with the public key as if it were an HMAC secret.

Fix: never let the token dictate the algorithm. Configure the verifier with an allowlist of expected algorithms, reject none, and validate exp/aud/iss. Treat the header's alg as untrusted input.

RBAC (Role-Based Access Control) grants permissions through roles: a user is an editor, the editor role can update:article. Simple, auditable, and enough for most apps. It strains when access depends on context beyond a role — ownership, department, time of day, resource attributes — leading to a 'role explosion' (editor_team_a_readonly_weekends).

ABAC (Attribute-Based Access Control) decides via policies over attributes of the user, resource, action, and environment (e.g. 'allow if user.dept == resource.dept and time is business hours'). It's far more expressive but harder to reason about and audit. Start with RBAC; reach for ABAC when contextual, fine-grained rules cause role explosion.

A normal string == short-circuits at the first mismatching byte, so it returns faster the earlier the difference. An attacker measuring response timing can exploit this timing side channel to recover a secret (an API token or HMAC) byte by byte — try values until the comparison takes slightly longer, meaning one more byte matched.

A constant-time comparison always examines the full length regardless of where bytes differ, leaking no timing information. Use the platform's crypto.timingSafeEqual / hmac.compare_digest for tokens, HMAC tags, and similar secrets. (Note: bcrypt/Argon2 verification already handles this for passwords.)

A salt is a unique random value stored *alongside* each password hash; it ensures identical passwords produce different hashes and defeats precomputed rainbow tables. It's not secret — it lives in the database with the hash.

A pepper is a single secret value mixed into every password before hashing, but kept outside the database (in app config, a secret manager, or an HSM). The point of defense-in-depth: if an attacker steals only the database, the salts don't help them, and without the pepper they still can't crack the hashes offline. Salt = per-user, public, in DB; pepper = global, secret, outside DB.

Authorization code flow: the app redirects the user to the auth server; the user authenticates and consents; the auth server redirects back with a short-lived authorization code; the app's backend exchanges that code (plus its client secret) for an access token over a back channel. Keeping tokens off the front channel is the point.

PKCE (Proof Key for Code Exchange) hardens this for public clients (SPAs, mobile) that can't keep a secret. The client sends a hashed code_challenge up front and the original code_verifier at exchange time, so a stolen authorization code is useless without the verifier. PKCE is now recommended for all clients.

localStorage is readable by any JavaScript on the page, so a single XSS flaw leaks the token. An HttpOnly cookie is invisible to JS (XSS can't read it) but is sent automatically, which opens CSRF.

The pragmatic answer: store tokens in HttpOnly, Secure, SameSite=Lax/Strict cookies and add anti-CSRF defenses (SameSite already blocks most cross-site sends; add a CSRF token for the rest). Keep access tokens short-lived. There's no storage location immune to a compromised front end — defense in depth plus a tight CSP matters more than the slot.

After OIDC verifies identity, you typically mint your own session/JWT rather than passing Google's token around. Reasons: you control expiry and revocation; you attach your app's roles/permissions and user id; you don't couple every internal service to the external provider's token format or availability; and you avoid leaking a powerful provider token across your backend.

The provider token is used once at login to establish identity; from then on your own credential governs the session.

They overlap but aren't identical. MVC is a UI-organizing pattern: the Model holds data/state, the View renders it, and the Controller handles input and coordinates the two — its purpose is separating presentation from data.

A layered architecture stacks responsibilities by technical concern (presentation → business/service → data-access/repository), each layer depending only on the one below. In practice a server MVC framework's 'Controller' maps to the presentation layer, and the 'Model' often expands into service + repository layers. So MVC describes the request-handling triangle; layering describes the full vertical stack that the model side usually grows into.

Middleware is a function in the request/response pipeline that runs before (and often after) the route handler. Each piece can inspect or mutate the request/response and either pass control to the next link or short-circuit (e.g. reject an unauthenticated request).

Classic uses: logging, authentication, body parsing, CORS, rate limiting, error handling. In Express the signature is (req, res, next) => { ... next(); }. The ordered chain is what makes cross-cutting concerns composable instead of duplicated in every handler.

S — Single Responsibility: a class has one reason to change; fixes the god-class that mixes parsing, business rules, and DB code. O — Open/Closed: extend behavior without editing existing code; fixes the ever-growing switch you reopen for every new case. L — Liskov Substitution: subtypes must be usable through the base type without surprises; fixes the subclass that throws on a method the parent promises. I — Interface Segregation: many small interfaces over one fat one; fixes clients forced to implement methods they don't use. D — Dependency Inversion: depend on abstractions, not concretions; fixes high-level logic nailed to a specific DB/SDK, which kills testability.

A Repository is a collection-like abstraction over persistence: the service asks for userRepo.findActiveByEmail(email) and doesn't know whether that's SQL, a document store, or an in-memory list. It centralizes query logic, decouples the domain from the ORM, and makes services testable with a fake repository.

The risk is a leaky abstraction: if the repository exposes IQueryable, raw SQL fragments, or ORM-specific lazy-loading proxies, persistence concerns bleed into the service and the decoupling is gone. Keep the interface in domain terms — return domain objects, accept domain criteria — so the storage technology stays a private detail.

A bloated constructor (a 'too many dependencies' smell) usually signals a Single Responsibility Principle violation — the class is doing too many jobs, each pulling in its own collaborators. It's the constructor-injection symptom of a god class.

Fix by decomposing: extract cohesive groups of those dependencies into smaller focused classes (e.g. a NotificationService wrapping the email/SMS/push senders) so the original class depends on a few higher-level abstractions instead of fourteen low-level ones. The number of constructor args is a proxy metric; the real fix is restoring single responsibility, not hiding the args behind a service locator or a giant config object.

Inheritance models 'is-a' and binds a subclass to its parent's implementation at compile time — a rigid, white-box coupling that gets brittle with deep hierarchies (the fragile base class problem) and tempts Liskov violations. Composition builds behavior by holding other objects and delegating to them ('has-a'), which you can vary at runtime and swap for tests.

The guidance 'favor composition over inheritance' (from the Gang of Four) is about flexibility: small composed parts recombine freely, while inheritance hierarchies resist change. Use inheritance for genuine, stable is-a relationships with a real behavioral contract; prefer composition for sharing/reusing behavior.

A Singleton enforces one global instance with global access. The problems: it's global mutable state in disguise, which hides dependencies (a class secretly reaches for Logger.getInstance() instead of receiving it). That makes unit tests hard — you can't easily substitute a mock, tests share state and leak into each other, and parallel tests interfere.

The usual fix is dependency injection: create one instance at the composition root and pass it in. You keep 'one instance' as a lifecycle policy without the hard-coded global lookup.

Dependency injection means a component receives its collaborators from outside (constructor/parameters) instead of constructing them itself. It's the practical expression of the Dependency Inversion Principle: code depends on an interface, and the concrete implementation is wired in at the edge.

Testability win: in a test you inject a fake/mock repository or HTTP client, so you can unit-test the service in isolation with no real database or network. It also decouples modules — swapping Postgres for an in-memory store is a wiring change, not a rewrite.

Controller: HTTP concerns only — parse/validate the request, call a service, map the result to a status code and response. Service: the business logic and orchestration — transactions, rules, coordinating multiple repositories; it knows nothing about HTTP. Repository: data access — encapsulates queries behind a collection-like interface so the service depends on an abstraction, not raw SQL.

The payoff is that each layer is testable and replaceable in isolation, and business logic doesn't leak into the web framework or the database.

Strategy: swap interchangeable algorithms behind one interface at runtime — e.g. pluggable payment processors or sort comparators, picked by configuration. Factory: centralize object creation so callers ask for *what* they want, not *how* it's built — e.g. createParser(fileType). Adapter: wrap an incompatible third-party interface to match the one your code expects — e.g. adapting a legacy SDK to your PaymentGateway interface.

Mnemonic: Strategy varies behavior, Factory varies construction, Adapter reconciles interfaces.

Observer / pub-sub: subjects publish events and any number of subscribers react, with no direct coupling between them — e.g. on OrderPlaced, the email service, inventory service, and analytics each subscribe independently. It decouples producers from consumers and underlies event-driven systems.

Decorator: wrap an object to layer behavior without changing it, preserving the same interface — e.g. wrapping a repository with caching, then logging, then retry. Each layer adds one concern and delegates inward, so you compose features instead of editing the core class.

Hexagonal architecture puts the domain/application core at the center and defines ports (interfaces) for everything it talks to. Adapters implement those ports for specific technologies — a Postgres adapter, a REST adapter, a Kafka adapter — and plug in at the edges. The dependency rule points inward: the core never imports a framework or driver.

Versus a strict top-down layered design (where the business layer still depends on a concrete data layer beneath it), hexagonal inverts those edge dependencies so the database, web framework, and message bus are all swappable, interchangeable details. The payoff is testability (drive the core through fake adapters) and decoupling the domain from infrastructure churn.

Inversion of control is the general principle that a framework or container — not your code — drives the flow: instead of your code calling into a library, the framework calls your code at the right moments ('don't call us, we'll call you', the Hollywood Principle). Event loops, middleware pipelines, and template method patterns are all IoC.

Dependency injection is one specific kind of IoC: inverting *who supplies a component's dependencies*. Rather than a class constructing its own collaborators, something external (a container or the composition root) provides them. So DI inverts dependency acquisition; IoC is the broader family of 'the framework controls the flow, you fill in the parts'.

Classic example: Square extends Rectangle. Setting width and height independently is part of Rectangle's contract, but a Square forces them equal, so code that does rect.setWidth(5); rect.setHeight(4); assert area == 20 breaks when handed a Square. The subtype violates the base type's expectations.

Fix: drop the inheritance — model Shape with an area() method and make Square and Rectangle siblings, or use immutable value objects so the mutating contract that conflicts never exists. The lesson: 'is-a' in English isn't enough; the subtype must honor the supertype's behavioral contract.

Deadlock: threads are blocked forever, each waiting on a resource another holds — nobody moves (e.g. the AB/BA lock-ordering cycle). Livelock: threads aren't blocked and keep *changing state* in response to each other, but make no progress — like two people stepping aside in the same direction repeatedly in a hallway. Starvation: a thread *can* run but is perpetually denied the resource because others keep winning it (e.g. a low-priority thread under a greedy scheduler).

Key distinction: deadlock = stuck and idle; livelock = busy but unproductive; starvation = some progress overall, but one thread is unfairly shut out.

Concurrency is about *dealing with* many tasks by interleaving them — making progress on several by switching between them, even on a single core. Parallelism is *doing* many tasks at the same instant on multiple cores.

Rob Pike's line: concurrency is about structure, parallelism is about execution. A single-threaded async server is concurrent but not parallel; a CPU-bound job split across 8 cores is parallel. You can have concurrency without parallelism and vice versa.

Node runs your JavaScript on a single event-loop thread. A heavy *synchronous* CPU task (a big loop, sync crypto, JSON over megabytes) doesn't yield, so it blocks the event loop — every other pending request, timer, and callback stalls until it finishes. Async I/O isn't the issue; CPU-bound sync work is.

Fixes: move the CPU work off the loop — use a worker thread (or worker_threads/a child process), the async variant of the crypto API, or offload to a separate service/queue. The rule: never run long synchronous CPU work on the event loop thread.

Thread-per-request (classic Java/Tomcat, Apache prefork) assigns each connection a thread. The model is simple — blocking code reads top-to-bottom — but each thread costs ~1MB+ of stack and context-switch overhead, so tens of thousands of concurrent connections exhaust memory and the scheduler (the C10k problem).

Event-loop / reactive servers (Node, Netty, nginx) handle many connections on a few threads via non-blocking I/O and callbacks, scaling to huge connection counts with low memory. The cost is programming complexity (callbacks/async) and the danger that any blocking call freezes the loop. Threads suit moderate concurrency with blocking dependencies; event loops suit massive I/O-bound concurrency.

A process has its own isolated memory space; threads within a process share the same heap/address space. Threads are cheaper to create and communicate through shared memory; processes are heavier but isolated — a crash or memory corruption in one process can't directly corrupt another.

Pick threads for fine-grained shared-memory work where communication cost matters; pick processes for isolation and fault containment (and, in languages with a GIL like CPython, to get true CPU parallelism). The tradeoff is shared-memory speed vs. isolation and safety.

A race condition is when the result depends on the unpredictable timing/interleaving of concurrent operations on shared state. Classic case: two threads run balance = balance + 100. That's read-modify-write: both read the same old value, both add 100, both write back — one update is lost.

Fix by making the critical section atomic: guard it with a mutex/lock, use an atomic increment, or use a compare-and-swap. The general principle is to serialize access to shared mutable state so only one thread is in the critical section at a time.

A mutex provides mutual exclusion: one holder at a time, and ownership matters — the thread that locks it should unlock it. Use it to protect a single shared resource / critical section.

A semaphore is a counter that permits up to N concurrent holders (acquire decrements, release increments, block at zero). A binary semaphore (N=1) resembles a lock but has no ownership and is often used for signaling between threads. Use a counting semaphore to cap concurrency — e.g. limit to 10 simultaneous DB connections.

Most server work is I/O-bound — waiting on the network, disk, or a database. With blocking I/O each connection ties up a thread that just sits idle during the wait, so 10k connections need ~10k threads (expensive memory + context switching).

Non-blocking async I/O flips this: the thread issues the I/O and immediately moves on; the OS notifies it (epoll/kqueue) when data is ready, and a callback/continuation resumes. One thread multiplexes thousands of in-flight waits because no thread blocks on the wait. The catch: a CPU-bound task blocks the loop and starves everyone, so async shines for I/O-bound, not CPU-bound, work.

Pool starvation: every thread (or DB connection) in a bounded pool is busy waiting on a resource that can only be supplied by *another* task that's now stuck in the pool's queue with no thread to run it. No mutex is involved, yet the system wedges — a 'pool-induced deadlock'.

Classic case: a request handler holds a pooled thread and synchronously calls back into the same service/pool, which is exhausted; the inner call waits for a thread that will only free up when the outer call returns. Fixes: never block a pooled thread waiting on the same pool, size pools to account for nested calls, separate pools for distinct workloads (bulkheading), and add timeouts so waiters fail fast instead of hanging forever.

Double-checked locking checks instance == null, locks only if null, checks again inside the lock, then constructs. The subtle bug is memory visibility / instruction reordering: object construction isn't atomic — the reference can become visible to other threads *before* the constructor's writes are flushed, so a second thread sees a non-null but partially-initialized object.

The fix depends on the memory model: in Java, mark the field volatile (which since JMM 5 establishes the needed happens-before ordering); other languages need their equivalent memory barrier / acquire-release semantics. The deeper lesson: correctness under concurrency needs the language's memory model guarantees, not just mutual exclusion.

A deadlock is when threads wait forever on each other's locks. It needs all four Coffman conditions simultaneously: mutual exclusion, hold-and-wait, no preemption, and circular wait.

Break any one to prevent it. The most practical: impose a global lock-ordering so all threads acquire locks in the same order (kills circular wait); or acquire all locks at once (kills hold-and-wait); or use lock timeouts / tryLock and back off. Example deadlock: thread A holds lock 1 and wants lock 2 while thread B holds lock 2 and wants lock 1.

Pessimistic locking assumes conflicts are likely, so it locks the row/resource up front (SELECT ... FOR UPDATE) and others wait. Safe but reduces concurrency and risks deadlocks.

Optimistic locking assumes conflicts are rare: read freely, and at write time check a version number (or timestamp/ETag) — if it changed, someone else won, so reject and retry. Great for low-contention, read-heavy workloads; wasteful retries under high contention. Pick pessimistic for hot, highly-contended rows; optimistic for mostly-independent updates.

A mutex involves OS-level machinery: contended threads may block and be parked/woken by the scheduler, which costs context switches. CAS is a single hardware instruction — 'if memory still holds the value I read, swap in the new value, else fail' — so a lock-free counter just loops read → compute → CAS, retry on failure entirely in user space with no blocking.

Under low-to-moderate contention this is much cheaper. The tradeoff: CAS works for small single-word updates; complex multi-variable invariants still need locks, and very high contention makes CAS retry loops spin wastefully. This is the basis of lock-free/atomic data structures.

In a point-to-point queue, each message is delivered to exactly one consumer among possibly many competing workers — it's a work queue for distributing tasks (e.g. resize one image once, no matter how many workers are running). In publish/subscribe, each message is fanned out to *every* subscriber, so N independent services all react to the same event.

Use point-to-point to load-balance work across a pool (competing consumers); use pub/sub to broadcast an event to multiple independent consumers. Kafka models pub/sub via consumer groups: across groups it's fan-out, within a group it's point-to-point load balancing.

Kafka is a durable, append-only distributed log: consumers track an offset and can replay; built for high-throughput streaming and event sourcing, with retention so multiple consumer groups read the same stream independently. RabbitMQ is a traditional broker with smart routing (exchanges, queues, bindings) and per-message acks — great for complex routing and classic task queues, but messages typically vanish once consumed. SQS is a fully managed AWS queue — minimal ops, at-least-once delivery, near-infinite scale, but no replay and limited ordering (FIFO queues excepted).

Pick Kafka for streaming/replay/high-throughput, RabbitMQ for rich routing and work queues, SQS when you want managed simplicity on AWS.

No — this is the key mental-model shift from traditional queues. Kafka is a durable log; reading a message does not remove it. The consumer just advances its offset (a bookmark), and the data stays on disk for everyone else to read. Multiple consumer groups can read the same messages independently, and a group can rewind its offset to replay.

Retention is governed by configured policy, not consumption: time-based (retention.ms, e.g. 7 days) or size-based (retention.bytes), or log compaction (keep the latest value per key). Messages age out by policy regardless of whether anyone consumed them.

Most brokers guarantee at-least-once delivery: if a consumer processes a message but crashes before acking, the broker redelivers it, so duplicates are inevitable. If processing isn't idempotent, a duplicate means double-charging, double-emailing, or double-incrementing.

Make the consumer idempotent: dedupe on a stable message id (record processed ids and skip repeats), or design the operation so reapplying it is a no-op (upsert, set-to-value instead of increment). Then redelivery is harmless.

A dead-letter queue (DLQ) is a side queue where messages go after they repeatedly fail to be processed (exceeding a max-receive/retry count) or can't be delivered. It stops a single 'poison' message from being redelivered forever and blocking the main queue.

Operationally you alert on DLQ depth, inspect the failed messages, fix the bug or bad data, and replay them back to the main queue. Without a DLQ, a permanently-failing message either loops endlessly or gets silently dropped.

Consumer lag is the gap between the latest offset produced to a partition (the log-end offset) and the offset the consumer group has committed — i.e. how many messages are produced-but-not-yet-processed. Steady or near-zero lag means consumers keep up; growing lag means the consumers can't process as fast as producers write.

It's a primary health/alerting signal. Remedies for chronic lag: add consumers (up to the partition count — that's the parallelism ceiling), add partitions, speed up per-message processing, or batch. Spiky lag that drains is fine; monotonically rising lag predicts an eventual backlog blowup.

With no distributed ACID transaction across microservices, a Saga breaks a business transaction into a sequence of local transactions, each publishing an event; if a step fails, compensating transactions undo the prior steps (e.g. refund a charge after inventory reservation fails).

Choreography: services react to each other's events with no central coordinator — loosely coupled but the end-to-end flow is implicit and hard to trace. Orchestration: a central orchestrator explicitly drives each step and triggers compensations — easier to reason about and monitor, but the orchestrator is a coupling point. Choose choreography for simple, few-step flows; orchestration as step count and error handling grow.

With manual acks, RabbitMQ keeps a message 'unacked' until the consumer confirms it; if the consumer dies first, the message is requeued — that's how at-least-once delivery and crash safety work. Auto-ack trades that safety for speed (a crash mid-processing loses the message).

Prefetch (basic.qos) caps how many unacked messages a consumer may hold at once. Prefetch=1 gives the fairest load distribution (a slow consumer won't hoard a backlog) but adds round-trip overhead; a higher prefetch boosts throughput by pipelining but can let one consumer grab a big batch while others idle. Tune prefetch to balance fairness against throughput for your processing time.

A queue decouples producer rate from consumer rate: during a spike, messages buffer in the queue instead of overwhelming the downstream service, which keeps processing at its sustainable rate — that's load leveling (the queue-based load-leveling pattern). It smooths bursts into a steady drain.

But a queue is finite. If producers persistently outpace consumers, queue depth grows unbounded: latency climbs (messages wait longer), memory/disk fills, and you risk hitting limits or processing hours-stale data. Back-pressure is signaling producers to slow down (reject, throttle, or block) when depth crosses a threshold. Always monitor and alert on queue depth/age, cap the queue, and decide a shed/back-pressure policy — a queue defers overload, it doesn't eliminate it.

Exactly-once *network delivery* is generally impossible — you can't simultaneously guarantee no loss and no duplicates across an unreliable network (two-generals problem). What systems offer is exactly-once processing / effective-once: at-least-once delivery plus idempotent or transactional handling so the observable effect happens once.

Kafka's 'exactly-once semantics' works this way: idempotent producers and transactions tie the consume-process-produce cycle together so duplicates don't produce duplicate effects. The honest framing: dedup + transactions give exactly-once *effects*, not magically-once delivery.

Request/response is synchronous and simple: the caller waits and gets an answer or an error, with a clear linear flow that's easy to reason about and debug. But it couples services temporally — if the callee is down, the caller fails — and it doesn't absorb spikes.

Event-driven publishes events and lets consumers react asynchronously: it decouples producers from consumers, buffers load (the queue absorbs spikes), and lets you add new consumers without touching the producer. The costs are eventual consistency, harder end-to-end debugging/tracing, and the need for idempotency and ordering handling. Use events for fan-out, decoupling, and load-leveling; use request/response when you need an immediate answer.

Kafka guarantees ordering only within a partition, not across a topic. Messages with the same partition key (e.g. userId) always land in the same partition and are consumed in order, so per-key ordering holds.

The catch: you only get parallelism by having multiple partitions, and across partitions there's no global order. So you trade total ordering for throughput. If you need strict global ordering you're limited to one partition (no parallelism) — the usual move is to choose a partition key that makes per-key ordering sufficient.

The trap (a dual write) is committing to the DB and then publishing to the broker as two separate steps — a crash in between leaves them inconsistent (event lost, or published but DB rolled back).

The standard fix is the transactional outbox: in the same DB transaction as the business write, insert the event into an outbox table. A separate relay (polling or change-data-capture like Debezium) reads the outbox and publishes to the broker, marking rows sent. Because the write and the outbox insert commit atomically, the event is never lost; the relay gives at-least-once publishing, so consumers stay idempotent.

A timeout is ambiguous: when a client's request times out, it cannot tell whether the server never received it, processed it but the response was lost, or is still processing. So a retry might be a true retry or an accidental duplicate of a request that already succeeded.

That's why a non-idempotent operation (charge a card, place an order) needs an idempotency key: the client sends a stable key, the server dedupes on it, and a retry of an already-applied request returns the original result instead of re-applying it. Without the key, the safe-looking retry can double-charge. The subtlety: the failure you can see (timeout) hides whether the side effect happened.

CAP says that when a network partition happens, a distributed data store must choose between Consistency (every read sees the latest write) and Availability (every request gets a non-error response). You can't have both during a partition; without a partition you get both.

So it's really a choice made *when partitioned*. CP systems (e.g. HBase, MongoDB in its default config) refuse or block to stay consistent; AP systems (e.g. Cassandra, CouchDB) keep serving and reconcile later (eventual consistency). Important caveat: CAP says nothing about latency or scalability — it's strictly about behavior under partition.

Round robin sends each request to the next server in rotation — simple and fine when requests are uniform and servers identical, but blind to actual load. Least connections routes to the server with the fewest active connections — better when request durations vary, since it adapts to real load instead of assuming uniformity.

Consistent hashing (hash the client/key to a server) keeps a given key/session on the same server — essential for cache affinity or sticky routing, and it minimizes remapping when servers are added/removed. Round robin for stateless uniform work; least connections for variable work; consistent hashing when affinity/locality matters.

Latency is how long a single operation takes (time per request); throughput is how many operations complete per unit time. They're related but distinct — a system can have high throughput and high latency at once.

They trade off because techniques that raise throughput often add per-request latency: batching many requests amortizes overhead (more throughput) but each request waits for the batch to fill (more latency); deep queues keep workers busy (throughput) but messages wait longer (latency). The discipline is to measure latency as a distribution (p50/p95/p99), not a mean, since tail latency is what users feel, and to choose the tradeoff per workload.

Vertical scaling means a bigger machine (more CPU/RAM) — simple but bounded by the largest box and a single point of failure. Horizontal scaling means more machines behind a load balancer — effectively unbounded and fault-tolerant, but only if requests can hit any node.

That's why statelessness matters: if a server keeps user session state in local memory, the load balancer must pin a user to one node (sticky sessions), which breaks failover and uneven load. Push state to a shared store (Redis/DB) so any node can serve any request, and horizontal scaling becomes trivial.

Eventual consistency means replicas may temporarily disagree, but if writes stop, they converge to the same value given enough time. AP systems accept it as the price of staying available and low-latency under partitions and across regions.

Why accept it: strong consistency requires coordination (consensus, quorums) on every write, which adds latency and reduces availability when nodes can't reach each other. For many features — a like count, a social feed, a shopping cart — a few seconds of staleness is fine, and the availability/latency win is worth it. For money movement you choose strong consistency instead.

An API gateway is the single entry point for clients: it routes to the right service and handles cross-cutting concerns — auth, rate limiting, TLS termination, request aggregation, and sometimes response shaping — so each service doesn't reimplement them and clients don't need to know the internal topology.

Service discovery lets services find each other's network locations as instances scale up/down and move. A registry (Consul, Eureka, or Kubernetes DNS/Services) maps a logical service name to current healthy instances, so callers resolve a name instead of hardcoding IPs. Together they decouple clients from the shifting set of backend instances.

For read-heavy load, add read replicas: writes go to the primary, which asynchronously replicates to replicas that serve reads, spreading read load and adding redundancy. The catch is replication lag — a replica may be milliseconds-to-seconds behind, so a user who just wrote can read a replica and not see their own change.

Fix the read-your-writes experience by routing a user's reads to the primary for a short window after they write, pinning their session to the primary, tracking a write timestamp/LSN and only reading replicas caught up past it, or using synchronous replication for the critical path (at a latency cost). Layer caching and, if writes also dominate, consider sharding.

This is a retry storm / metastable failure. When a dependency slows or briefly fails under load, every client retries — often multiplying traffic 3x or more right when the service is least able to handle it. The added load keeps the service overloaded, so it keeps failing, so clients keep retrying: a self-sustaining feedback loop that doesn't recover even after the original trigger passes.

Fixes: bound retries with a retry budget (cap retries as a fraction of traffic, not per-request), add exponential backoff with jitter, use circuit breakers to fail fast, and only retry idempotent operations. Retries help with isolated transient blips; unbounded retries under systemic load amplify the failure.

Sharding splits one logical dataset across multiple databases/nodes by a shard key, so each shard holds a subset and the system scales writes and storage beyond one machine. Reads/writes route to the shard owning the key.

The shard key is the hard part because a bad one creates hotspots — picking a low-cardinality or monotonically-increasing key (like a timestamp) funnels traffic to one shard, defeating the point. You want a key that spreads load evenly *and* keeps commonly-joined data co-located so you avoid expensive cross-shard queries. Cross-shard transactions and re-sharding as you grow are the recurring pains, which is why teams delay sharding until replicas and caching are exhausted.

A monolith is one deployable: simpler local dev, easy refactors across boundaries, in-process calls, one transaction — at the cost of coupled deploys and scaling the whole app together. Microservices give independent deploys, team autonomy, and targeted scaling — but you pay with distributed-systems tax: network failures, eventual consistency, distributed transactions/sagas, harder debugging and tracing, and heavy ops.

The seasoned answer: don't reach for microservices by default. Most teams should start with a well-modularized monolith and split out services only when a clear scaling, team-ownership, or deploy-cadence boundary justifies the added operational cost.

Retries handle transient failures, but naive retries cause two problems. Exponential backoff (wait 1s, 2s, 4s…) stops a struggling service from being hammered every few milliseconds while it tries to recover.

Jitter (randomizing each wait) prevents a thundering herd: if many clients fail at the same instant and all back off by the exact same schedule, they retry in synchronized waves that keep knocking the service over. Adding randomness spreads the retries out. Pair this with retry budgets/circuit breakers and only retry idempotent or idempotency-keyed operations.

A circuit breaker wraps calls to a dependency and tracks failures. In closed state calls pass through; once failures cross a threshold it opens and fails fast (returns an error or fallback immediately) instead of piling up calls on a sick service. After a cooldown it goes half-open, lets a trial request through, and closes again if it succeeds.

It prevents cascading failures: without it, a slow dependency exhausts the caller's threads/connections waiting on timeouts, which then takes the caller down, propagating upstream. Failing fast contains the blast radius and lets the dependency recover.

With plain hash(key) % N, changing the number of nodes N remaps almost every key — catastrophic for a cache (mass misses) or a sharded DB (mass data movement). Consistent hashing maps both keys and nodes onto a ring; a key belongs to the next node clockwise. Adding or removing a node only relocates the keys in that node's arc — about 1/N of keys — instead of nearly all of them.

Virtual nodes (each physical node placed at many ring positions) smooth out uneven distribution. This is why Cassandra, DynamoDB, and Memcached-style caches use it.

Many tasks need exactly one node in charge (assigning work, ordering writes) to avoid conflicts — so the cluster elects a leader via a consensus protocol (Raft, Paxos, ZooKeeper/ZAB). If the leader dies, a new one is elected.

To agree despite failures, decisions use a quorum — a majority (N/2 + 1). Requiring a majority for writes and reads guarantees any two quorums overlap, so the system never commits two conflicting decisions and can tolerate a minority of nodes failing. This is the backbone of consistent distributed stores and coordination services.

Prefer delete (invalidate) over update-in-place. Updating the cache directly on write opens a race: two concurrent writers can set the cache in the opposite order from how they hit the DB, leaving the cache holding the older value permanently. Deleting the key sidesteps that — the next read just repopulates from the source of truth.

Delete is also cheaper (you don't recompute a value that may never be read) and avoids caching an intermediate state. The cost is one guaranteed cache miss after each write. For very hot keys you can refresh asynchronously, but the default rule is invalidate, don't update.

Caching exists at many layers, each closer to the user is cheaper: browser cache (per-user, static assets via Cache-Control/ETag); CDN / edge (shared, geo-distributed static and cacheable responses); application / in-process (a local in-memory map — fastest but per-instance and not shared); distributed cache (Redis/Memcached — shared across app servers); and the database query/buffer cache.

The instinct: cache as close to the user as the data's freshness allows. Each layer trades reach (shared vs per-instance) against latency and invalidation difficulty.

Cache-aside (lazy loading): app checks cache; on a miss it reads the DB, populates the cache, and returns. Most common for read-heavy workloads; only requested data is cached, but the first hit is a miss and stale data is possible without invalidation.

Write-through: writes go to cache and DB together, so the cache is always consistent — at the cost of higher write latency and caching data that may never be read. Write-back (write-behind): write to cache immediately and flush to the DB asynchronously — fast writes and great for write-heavy bursts, but a cache crash before flush loses data. Pick cache-aside by default; write-through when reads must never be stale; write-back when write latency dominates and you can tolerate the durability risk.

A good cache key is deterministic (same logical request → same key), specific enough to avoid collisions (include the parameters that change the result — user, locale, version), and normalized (sort query params, lowercase where appropriate) so equivalent requests share a key. Over-specific keys (including irrelevant params like a request id) fragment the cache and tank the hit rate; under-specific keys serve the wrong data.

Hit ratio (hits / total lookups) is the headline metric because a cache only pays off when most reads avoid the backend. A low hit ratio means you're spending memory and adding a layer for little benefit — investigate whether keys are too granular, TTLs too short, or the working set exceeds cache capacity.

Stale data after a deploy almost always means a cache somewhere is serving the old version. Walk the layers from the client inward: the browser cache (Cache-Control/Expires on the asset — a missing hash/versioned filename means the browser reuses the old bundle), the CDN/edge (needs a purge/invalidation for changed assets), the application/distributed cache (Redis/Memcached entries not invalidated by the deploy), and finally the DB query cache.

Debug tooling: inspect response headers for Age, X-Cache: HIT, and Cache-Control; force-reload to bypass the browser; check whether the CDN was purged. The durable fix for static assets is cache-busting — content-hashed filenames so a new version is a new URL and old caches simply don't apply.

Both are lazy-loading read strategies, but they differ in *who* loads on a miss. In cache-aside (lazy loading) the application owns the logic: it checks the cache, and on a miss it reads the DB and writes the result back to the cache itself. The cache is just a dumb store; the app is the orchestrator.

In read-through, the cache sits inline and loads from the DB on a miss transparently — the application only ever talks to the cache, and a provider/loader function populates it. Read-through centralizes the load logic (less duplicated code, consistent behavior) but needs cache support for it; cache-aside is more flexible and the most common pattern. Both still need a write strategy and TTLs to manage staleness.

When a cache is full it evicts by policy. LRU drops the least-recently-used entry — the default; great when recent access predicts future access (temporal locality). LFU drops the least-frequently-used — better when some items are persistently hot regardless of recency, but it can keep stale 'once-popular' items. FIFO evicts the oldest inserted regardless of use — simple but ignores access patterns.

TTL is orthogonal: it bounds staleness by expiring entries after a time, independent of capacity pressure. Typical setup: LRU for capacity eviction plus a TTL for freshness.

Combine a hash map (key → node) with a doubly linked list ordered by recency. The map gives O(1) lookup; the linked list gives O(1) move-to-front and O(1) eviction at the tail.

On get: look up the node in the map, unlink it, move it to the head (most recent), return its value. On put: if present, update and move to head; if new, insert at head and add to the map; if over capacity, remove the tail node and delete its key from the map. Both operations are O(1) because every step is a constant-time pointer/map update.

Map (key -> node) + DLL: head=newest ... tail=evict

Memcached is a simple, multithreaded, in-memory key→blob cache — extremely fast and easy to scale for pure caching of opaque values. Redis is a richer in-memory data store: it has data structures (lists, sets, sorted sets, hashes, streams), optional persistence, replication, pub/sub, Lua scripting, and clustering.

Pick Memcached when you just need a fast, large, simple cache and want multithreaded throughput per node. Pick Redis when you need those data structures, durability, atomic operations, pub/sub, rate-limiter counters, leaderboards, or built-in replication/clustering — which is most modern use cases.

Redis holds data in memory, so two policies matter. Eviction (maxmemory-policy) decides what happens when memory fills — noeviction (reject writes), allkeys-lru, volatile-ttl, etc. Pick LRU/LFU variants when using Redis as a cache; noeviction when it's a primary store you can't silently drop from.

Persistence decides what survives a restart. RDB takes periodic point-in-time snapshots — compact, fast to load, but you lose writes since the last snapshot. AOF (append-only file) logs every write operation — far better durability (down to per-write fsync) at the cost of larger files and slower restart. Many run both: AOF for durability, RDB for fast restores. Treating Redis purely as a cache means you may not need persistence at all.

Caching is not free — it adds a consistency problem and an extra failure mode. It's the wrong move when the data changes more often than it's read (you invalidate constantly, getting a near-zero hit ratio while paying the cost), when staleness is unacceptable (account balances, inventory at checkout, anything where a wrong value causes real harm), when the working set is far larger than memory so you thrash with evictions, or when the backend is already fast enough that the cache only adds complexity and a coherence bug surface.

The instinct: reach for caching when reads dominate writes and a little staleness is tolerable; otherwise the extra layer buys complexity, not speed.

A cache stampede happens when a hot key expires and many concurrent requests all miss simultaneously, then all hit the database at once to recompute the same value — a spike that can overload the backend.

Mitigations: request coalescing / locking so only one request recomputes while others wait for or briefly serve the old value; early/probabilistic expiration so one request refreshes the key slightly before it expires; stale-while-revalidate, serving the old value while refreshing in the background; and jittering TTLs so many keys don't expire at the same instant.

There are really two hard problems: deciding *when* a cached value is no longer valid, and making the cache and source of truth agree across concurrent updates. With cache-aside, a classic race: reader gets a miss and starts loading the old value; a writer updates the DB and deletes the cache key; the reader then writes its stale value back — now the cache is wrong indefinitely.

Approaches: delete (don't update) the key on write so the next read repopulates fresh; use short TTLs to bound staleness; version keys; or for tighter consistency use write-through. There's no free lunch — you trade consistency, latency, and complexity.

Cache penetration: requests for keys that don't exist anywhere always miss the cache and hit the DB — common in scraping/attacks. Fix by caching the negative result (a short-TTL 'null' marker) or screening with a Bloom filter of valid keys.

Cache avalanche: a large set of keys expire at once (or the cache itself goes down), so traffic floods the DB en masse. Fix by jittering TTLs, layering caches, and adding rate limiting / circuit breakers in front of the DB. Versus a stampede, which is many concurrent requests for *one* expiring hot key — avalanche is many keys at once, penetration is keys that never exist.

COUNT(*) counts rows, including rows where every column is NULL. COUNT(col) counts rows where col is not NULL — NULLs are skipped. COUNT(DISTINCT col) counts the number of distinct non-NULL values.

So on a column with NULLs, COUNT(*) >= COUNT(col) >= COUNT(DISTINCT col). This trips people up in 'how many customers placed an order' style questions, where a LEFT JOIN leaves NULLs and COUNT(*) over-counts.

A primary key uniquely identifies a row: it is UNIQUE and NOT NULL, and there is exactly one per table.

A UNIQUE constraint also forbids duplicates but *does* allow a NULL (one, in most engines), and a table can have many of them.

A foreign key is a column whose values must exist as a key in another table — it enforces referential integrity (you cannot insert an order for a customer that does not exist, and the DB can block/cascade deletes).

CHAR(n) is fixed-length — it pads with spaces to n, so it suits truly fixed codes (a 2-char country code, a fixed hash). VARCHAR(n) is variable-length with a declared max, erroring if you exceed it. TEXT is variable-length with no practical limit.

In PostgreSQL there is no performance difference between them — the manual recommends text or varchar and notes char(n) is usually the *slowest* due to padding. The length limit is mainly a data-integrity constraint, not an optimization. (In some other engines, like older MySQL row formats, fixed vs variable length had storage implications.)

Use a CASE expression, which is SQL's inline if/else:

SELECT name, salary, CASE WHEN salary < 50000 THEN 'low' WHEN salary < 100000 THEN 'mid' ELSE 'high' END AS band FROM employee;

The searched CASE evaluates WHEN branches top-to-bottom and returns the first match, so order the boundaries carefully. With no ELSE, unmatched rows get NULL. You can also wrap CASE inside an aggregate (SUM(CASE WHEN … THEN 1 ELSE 0 END)) for conditional counts — the classic pivot trick.

Straight SELECT … WHERE … ORDER BY:

SELECT name, salary FROM employees WHERE department = 'Engineering' AND salary > 100000 ORDER BY salary DESC;

Watch the clause order — WHERE filters rows, ORDER BY runs last. String literals are single-quoted; double quotes mean an identifier in standard SQL.

WHERE filters individual rows before grouping; HAVING filters groups after the GROUP BY runs.

An aggregate like COUNT(*) is not known until rows are grouped, so it cannot appear in WHERE — it belongs in HAVING. Example: SELECT dept, COUNT(*) FROM emp WHERE active = true GROUP BY dept HAVING COUNT(*) > 5; — active is filtered per-row, the head-count per-group.

NULL is 'unknown', not a value. Any comparison with NULL using =/<> yields UNKNOWN (not true), so the row is dropped — WHERE col = NULL always returns zero rows.

Use the dedicated operators: WHERE col IS NULL / IS NOT NULL. Note aggregates skip NULLs (AVG, COUNT(col)) but COUNT(*) counts the row regardless.