Settings & backup

An algorithm is a precise list of steps that turns an input (①) into an output (③). A data structure organises data so the steps at ② stay fast. In Two Sum, the hash map seen lets each step ask "have I met the partner?" in one move instead of rescanning the array.

The words around a problem tell you how good the steps must be:

Watch it run.

Big-O describes how the number of steps grows as the input size n grows. It ignores constants and smaller terms, so 3n² + 10n + 7 is O(n²). One loop over the input is the straight line at ①. A loop inside a loop is the steep curve at ②. Halving the problem each step, as binary search does, is the flat curve at ③.

Space complexity counts extra memory the same way. Amortised means averaged over many operations: ArrayList.add is O(1) amortised, even though an occasional resize copies everything.

An array (int[], or an ArrayList that can grow) stores items side by side, each with an index from 0. Reading a[3] at ① is one jump, O(1), because the address is computed from the index. Inserting at the front at ② moves every item one place right, so it costs O(n). Appending at the end is O(1) amortised.

A string is an array of characters, and a Java String is immutable: s += c in a loop may copy the whole string each time. Prefix sums at ③ store running totals once, in O(n), so any range sum becomes one subtraction.

A hash map (HashMap) stores key → value pairs, and a hash set (HashSet) stores keys only. The key at ① goes through a hash function at ②, which gives a number. Taking it modulo the table size picks a bucket at ③, so lookup, insert and delete are O(1) on average. Two keys landing in the same bucket, as at ④, is a collision. It is handled automatically, but many collisions degrade lookups toward O(n).

Keys need a consistent equals and hashCode, and must not change while they are in the map. String, Integer and a List of them work. An int[] does not: arrays compare by identity, so an equal-looking array is a different key. Helpers: map.merge(x, 1, Integer::sum) counts every value, computeIfAbsent(k, key -> new ArrayList<>()) creates missing entries, and getOrDefault(k, 0) reads with a default.

Watch it run.

A recursive function calls itself on a smaller input. At ① each call waits on the call stack while it calls the next one down. At ② the base case answers directly, so the descent stops. At ③ each waiting call combines its own piece with the answer from below, and returns.

The mental trick is to trust the recursion: assume total(a, i + 1) is already right, and only write how to combine it. Each Java thread has a fixed-size stack, so very deep recursion fails with StackOverflowError.

Before coding, read the constraints at ①. They set a time budget at ②. Roughly 10⁸ simple steps run in a second (③), so n ≤ 10⁵ rules out O(n²) straight away. Then work one example by hand, and list the edge cases at ④.

Ask the clarifying questions that change the algorithm: is the input sorted? Are duplicates allowed? Return indices or values? Can there be several valid answers?

One line: when you need a fast "have I seen this?" or "how many of this?", a hash set or hash map turns an O(n²) scan into one O(n) pass.

Every word at ① is turned into a canonical key at ②: its letters sorted. Anagrams produce the same key, so at ③ the map collects them in one bucket without ever comparing two words directly. The brute force compares every pair. The map replaces that inner loop with an O(1) average lookup.

Signals: "contains a duplicate", "two numbers that add to", "group the words that…", "most frequent".

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // value -> index
    for (int i = 0; i < nums.length; i++) {
        int want = target - nums[i];    // what would complete the answer?
        if (seen.containsKey(want)) {
            return new int[]{seen.get(want), i};
        }
        seen.put(nums[i], i);           // store AFTER checking: no self-pair
    }
    return new int[0];
}

Watch it run.

One line: with sorted input, or a pair or triple to find, put one pointer at each end and move the one that can only improve the answer.

At ① the sum 12 is too small. Every pair that uses 1 with anything up to 11 is 12 or less, so 1 can never be in an answer and l moves on. At ② the same proof discards 2. At ③ the pointers meet the pair. Each step discards one candidate with proof, so n steps cover every pair that matters.

Signals: the input is sorted (or sorting is allowed); find a pair or triple with a target sum; compare the two ends (palindromes, containers).

public int[] twoSum(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int s = nums[l] + nums[r];
        if (s == target) {
            return new int[]{l, r};
        }
        if (s < target) {
            l++;                // need bigger: only l can raise the sum
        } else {
            r--;                // need smaller: only r can lower it
        }
    }
    return new int[0];
}

Watch it run, then try Container With Most Water.

One line: for the best contiguous substring or subarray under a condition, expand the right edge, shrink the left edge while the window is invalid, and track the best valid window.

At ① the window "abc" is valid, so the best length is 3. At ② the new 'a' makes it invalid, and l moves past the old 'a'. At ③ a repeated 'b' pushes l again. Every bigger window starting at a dashed letter would also be invalid, so l never moves back: each index enters once and leaves once, O(n) in total.

Signals: "longest" or "shortest" substring or subarray (contiguous) such that…; a fixed window size k.

public int longestWindow(String s) {
    int[] counts = new int[128];                  // counts per ASCII char
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        counts[s.charAt(r)]++;                    // 1. expand
        while (!valid(counts)) {                  // 2. shrink until valid
            counts[s.charAt(l)]--;
            l++;
        }
        best = Math.max(best, r - l + 1);         // 3. record
    }
    return best;
}

Watch it run.

One line: for "next greater or smaller" questions, or matching pairs, keep a stack. A monotonic stack pops everything the new item beats, and each pop is an answer.

At ① to ③ each new temperature is colder, so it waits on top of the stack: the stack stays in decreasing order. At ④ the warmer 72 arrives, pops every waiting day it beats, and each pop gets its answer (the distance in days). Each day is pushed once and popped at most once, so the whole pass is O(n).

Signals: matching brackets or tags, undo history, expression evaluation (last in, first out); "next warmer day", "next greater element", "largest rectangle".

public int[] dailyTemperatures(int[] temps) {
    int[] res = new int[temps.length];
    Deque<Integer> stack = new ArrayDeque<>();   // days still waiting
    for (int i = 0; i < temps.length; i++) {
        while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
            int j = stack.pop();
            res[j] = i - j;                      // day i answers day j
        }
        stack.push(i);
    }
    return res;
}

Watch it run, and see Valid Parentheses for the plain stack.

One line: with sorted data, or an answer space where "works / doesn't work" flips exactly once, binary search it. Write the check function first, then the lo/hi loop.

Koko can finish at speed k or she cannot, and a faster speed never needs more hours. So the checks along speeds 1 to 11 read fail, fail, fail, then pass for good. At ① the middle speed passes, so the answer is 6 or lower. At ② speed 3 fails, so everything up to 3 is gone. At ③ the range closes on 4. Each check halves the range: O(log n) checks.

Signals: sorted input; "find the minimum or maximum value such that…"; huge n or ranges (10⁹); a rotated sorted array.

public int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 0;
    for (int p : piles) {
        hi = Math.max(hi, p);              // the answer is in [lo, hi]
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;      // (lo + hi) / 2 can overflow
        if (canFinish(piles, h, mid)) {    // true for mid and above
            hi = mid;                      // mid might be the answer: keep it
        } else {
            lo = mid + 1;                  // mid fails: discard it
        }
    }
    return lo;
}

Watch it run, and compare with the classic search.

One line: use a dummy head for anything that may change the head, and fast/slow pointers for the middle, a cycle or the nth node from the end.

Reversal is pointer surgery. At ① cur is node 1 and prev is empty. At ② cur.next is saved first, so the rest of the list is not lost. Then node 1's arrow turns back to prev, and both pointers advance. At ③ every arrow points left, and prev holds the new head. Fast/slow: fast moves two steps, slow moves one; in a cycle the gap shrinks by one each step, so they must meet.

Signals: reverse, merge, reorder or remove nodes; find a middle, a cycle, or a node counted from the end in O(1) extra space.

public ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {           // reverse in place
        ListNode nxt = cur.next;    // 1. save the rest
        cur.next = prev;            // 2. rewire
        prev = cur;                 // 3. advance
        cur = nxt;
    }
    return prev;
}

Watch it run, then see Linked List Cycle for fast/slow.

One line: most tree problems are a DFS that returns one value up (height, gain, a boolean) while updating a global best. Level-by-level questions are BFS with a queue.

At ① the recursion goes all the way down before anything is computed. At ② an empty child returns the neutral value 0, so each leaf returns 1. At ③ every node returns 1 plus the larger of its children's answers, and the root's answer, 3, is the depth. Trust the recursion: assume each child returns the right answer, and only write how to combine them. The value you return can differ from the value you record: Diameter returns height but records left + right.

Signals: depth, diameter, balanced, path sum, same tree (post-order DFS); level order, right side view (BFS); BST problems (in-order is sorted, every node has a (low, high) range).

int best = 0;                                // a field, shared by every call
int height(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int l = height(node.left), r = height(node.right);
    best = Math.max(best, l + r);            // answer passes through here
    return 1 + Math.max(l, r);               // what the parent needs
}

Watch it run, and compare with level order, which is BFS.

One line: with many words and prefix queries, build a trie: each node maps a character to a child and carries an end-of-word flag. For a word grid, walk the grid and the trie together.

At ① "app", "apple" and "apt" share the nodes a and p, so the prefix is stored and walked once. At ② the double ring is the end flag: "app" is a stored word, not just a prefix. At ③ "apple" continues below it. A lookup costs O(length of the word), however many words the trie holds.

Signals: "starts with", autocomplete, a dictionary of words, wildcard search, many words searched at once.

class Node {
    Map<Character, Node> kids = new HashMap<>();   // char -> Node
    boolean end;                                   // a word ends here
}
void insert(Node root, String word) {
    Node cur = root;
    for (char ch : word.toCharArray()) {
        cur = cur.kids.computeIfAbsent(ch, k -> new Node());
    }
    cur.end = true;
}

Watch it run.

One line: for "top k", "k-th largest" or "always take the smallest or largest next", use a heap of size k. For a running median, use two heaps balanced by size.

At ① the min-heap holds the 3 largest values seen so far, and its top, 4, is the weakest of them: the 3rd largest. At ② 10 arrives, so it is pushed and the smallest, 4, is popped. The top is now 5. At ③ a value below the top never survives. Each step costs O(log k), so n values cost O(n log k) instead of O(n log n) for a full sort.

Signals: k-th largest or smallest, k closest, k most frequent; repeatedly take the min or max while items keep arriving (streams, schedulers, merging k lists).

public int kthLargest(int[] nums, int k) {
    // min-heap holding the k largest seen
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int x : nums) {
        heap.offer(x);
        if (heap.size() > k) {
            heap.poll();           // drop the smallest; the k largest remain
        }
    }
    return heap.peek();            // k-th largest
}

Watch it run.

One line: to generate all combinations, permutations or partitions, choose, recurse, then un-choose. Sort first and skip equal siblings to avoid duplicates.

The answers form a decision tree, and each level decides one element. At ① the path takes 1, then 2, reaching the leaf [1, 2]. At ② that leaf is recorded as a copy. At ③ the last choice is undone (remove), and the walk tries the sibling branch, "skip 2". One shared path list serves every branch because each choice is undone on the way back. Pruning cuts a branch as soon as it cannot lead to an answer.

Signals: "all subsets", "all permutations", "all combinations that sum to", "all ways to place"; small n (often 20 or fewer).

List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
void dfs(int[] nums, int i) {
    if (i == nums.length) {
        res.add(new ArrayList<>(path));      // copy! path keeps changing
        return;
    }
    path.add(nums[i]);                       // choose nums[i]
    dfs(nums, i + 1);
    path.remove(path.size() - 1);            // un-choose: skip nums[i]
    dfs(nums, i + 1);
}
// call dfs(nums, 0)

Watch it run.

One line: for connectivity questions on a grid or an edge list, use DFS or BFS with a visited set. Fewest steps means BFS; dependency order means topological sort; merging components means union-find.

At ① the start cell enters the queue at distance 0. At ② BFS removes cells in order of distance and gives every unvisited neighbour distance + 1, so it spreads in rings around the walls. At ③ the first time BFS reaches G, it got there by the fewest moves, 7, because every shorter path was explored first. A visited set guarantees each cell is processed once: O(V + E).

Signals: a grid of cells, or "n nodes and a list of edges"; "number of islands or components", "can you finish all courses", "fewest steps", "spread in minutes".

int bfs(int start, int goal) {
    Deque<Integer> q = new ArrayDeque<>();
    Set<Integer> seen = new HashSet<>();
    q.offer(start);
    seen.add(start);
    int steps = 0;
    while (!q.isEmpty()) {
        for (int size = q.size(); size > 0; size--) {   // one level
            int node = q.poll();
            if (node == goal) {
                return steps;
            }
            for (int nxt : neighbours(node)) {
                if (seen.add(nxt)) {       // new? mark on enqueue
                    q.offer(nxt);
                }
            }
        }
        steps++;
    }
    return -1;
}

Watch it run, then see Rotting Oranges for multi-source BFS.

One line: for a weighted shortest path, use Dijkstra with a min-heap. For a minimum spanning tree, use Prim or Kruskal. For an order built from pairwise rules, use topological sort.

At ① A is popped at distance 0, and its neighbours get tentative distances: B 4, C 1. At ② C is the closest unfinished node, so it is final at 1, and relaxing its edge improves B from 4 to 3. Then B is final at 3 and D at 4. With non-negative weights, the closest unfinished node can never be improved later, which is why popping it from the heap finalises it. At ③ the accent edges form the shortest-path tree.

Two relatives use the same graph. A minimum spanning tree links every node at the least total edge cost. Prim grows it from one node with a heap. Kruskal adds the cheapest edge that joins two groups (union-find). Bellman-Ford relaxes every edge once per round. If each round reads a copy of the last one, round k gives the cheapest paths of at most k edges.

Signals: edge weights and "minimum total"; "connect all points at minimum cost" (spanning tree); dictionary order from sorted words (topological sort); a limit on the number of edges (Bellman-Ford rounds).

int[] dijkstra(List<List<int[]>> adj, int src) {   // adj.get(u): {v, w} pairs
    int[] dist = new int[adj.size()];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<int[]> heap =
        new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    heap.offer(new int[]{0, src});                  // {distance, node}
    while (!heap.isEmpty()) {
        int[] top = heap.poll();
        int d = top[0], u = top[1];
        if (d > dist[u]) {
            continue;                      // stale entry: u is final
        }
        for (int[] e : adj.get(u)) {
            int v = e[0], w = e[1];
            if (d + w < dist[v]) {
                dist[v] = d + w;
                heap.offer(new int[]{d + w, v});
            }
        }
    }
    return dist;
}

Watch it run.

One line: when the answer at i depends on a few earlier answers, write the recurrence dp[i] = f(dp[i−1], dp[i−2], …), then keep only the variables you need.

dp[i] means "the most loot from houses 0 to i". At house 2 there are two choices. At ① skip it, and keep the best up to house 1, 7. At ② rob it, which forbids house 1, so add 9 to the best up to house 0: 11. At ③ the cell keeps the better choice. Every cell reuses two earlier cells, so the exponential recursion becomes one O(n) pass.

The method: say what dp[i] means in one sentence; write the recurrence from the last decision; set the base cases; fill small to large.

public int rob(int[] nums) {
    int rob1 = 0, rob2 = 0;                       // dp[i-2], dp[i-1]
    for (int x : nums) {
        int cur = Math.max(rob2, rob1 + x);       // skip house i, or rob it
        rob1 = rob2;
        rob2 = cur;
    }
    return rob2;
}

Watch it run, and compare with Climbing Stairs.

One line: with two indices (two strings, a grid, items × capacity), use a dp[i][j] table. Define what one cell means in a single sentence before writing any code.

Here a cell is "the LCS of the first i letters of 'abc' and the first j letters of 'ac'". The ∅ row and column are the empty string, so they are 0. At ① the letters match, so the cell extends the diagonal by 1. At ② they differ, so the cell takes the better of dropping a letter from either string: the cell above or the cell to the left. At ③ the corner holds the answer. Filling row by row guarantees every dependency is ready: O(m · n).

Signals: two strings compared ("common subsequence", "edit distance", "interleaving"); a grid walked right or down; a knapsack (items × budget).

public int lcs(String a, String b) {
    int[][] dp = new int[a.length() + 1][b.length() + 1];
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];      // extend diagonal
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[a.length()][b.length()];
}

Watch it run, then try Edit Distance.

One line: make a local choice that never needs undoing (the farthest reach, the earliest end, a reset on a deficit). Check it against one counter-example before coding.

Kadane's algorithm keeps a running sum cur. At ① and ② the running sum before the next number is negative. A negative prefix can only shrink any subarray that extends it, so it is dropped and the sum restarts. That is the exchange argument: no optimal answer keeps a negative prefix. At ③ the best running sum, 6, comes from [4, −1, 2, 1].

Signals: "can you reach the end", "minimum jumps", "maximum subarray", "partition so each letter appears in one part"; one pass with a single best-so-far value.

public int maxSubArray(int[] nums) {
    int best = nums[0], cur = 0;
    for (int x : nums) {
        cur = Math.max(cur, 0) + x;     // drop a negative prefix
        best = Math.max(best, cur);
    }
    return best;
}

Watch it run, then see Gas Station.

One line: sort by start (or by end), then sweep once, comparing each interval with the last one kept.

At ① the intervals are sorted by start, so an interval can only overlap the last kept one, never an earlier one. At ② [2, 6] starts before [1, 3] ends, so they merge into [1, 6]: the new end is the max of both ends. At ③ [8, 10] starts after 6, so it begins a new group. One sort plus one sweep: O(n log n). For "remove the fewest", keep the interval that ends earliest.

Signals: pairs [start, end] (meetings, bookings, ranges); "merge overlapping", "insert", "remove the fewest", "how many rooms".

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    List<int[]> merged = new ArrayList<>();
    merged.add(intervals[0]);
    for (int i = 1; i < intervals.length; i++) {
        int s = intervals[i][0], e = intervals[i][1];
        int[] last = merged.get(merged.size() - 1);
        if (s <= last[1]) {                    // overlaps the last kept
            last[1] = Math.max(last[1], e);
        } else {
            merged.add(new int[]{s, e});
        }
    }
    return merged.toArray(new int[0][]);
}

Watch it run.

One line: matrix problems are index bookkeeping, so shrink the boundaries or use the first row and column as markers. Number problems: watch for overflow and use fast exponentiation.

A 90° clockwise rotation sends the cell at (r, c) to (c, n−1−r). Doing that directly needs a copy. Instead, at ② transpose (swap (r, c) with (c, r)), then at ③ reverse each row (send column c to n−1−c). Together they produce exactly the rotation, with in-place swaps only. Fast power works the same way, by breaking a big step into cheap ones: x^n = (x^(n/2))², so O(log n) multiplications.

Signals: rotate, spiral, set zeroes (in-place moves on a grid); powers, digits, carries, very large numbers as strings.

public double myPow(double x, int n) {
    long e = n;                     // long: -Integer.MIN_VALUE overflows int
    if (e < 0) {
        x = 1 / x;
        e = -e;
    }
    double res = 1;
    while (e > 0) {
        if ((e & 1) == 1) {
            res *= x;               // bit of n is set: include x
        }
        x *= x;                     // x, x², x⁴, x⁸ ...
        e >>= 1;
    }
    return res;
}

Watch it run.

One line: XOR cancels pairs, n & (n − 1) drops the lowest set bit, and shifts walk the bits. Know these three moves.

XOR works column by column: equal bits give 0, different bits give 1. At ① and ③ the two 4s put a 1 in the same column, and those two 1s cancel. At ② only the bits of the number that appears once survive, so XOR-ing the whole list finds it in one pass with O(1) memory. Order does not matter, because XOR is commutative and associative. n & (n − 1) clears the lowest 1 bit, so a loop of it runs once per set bit.

Signals: "every element appears twice except one", "count the 1 bits", "missing number", arithmetic without + or −, 32-bit limits.

public int singleNumber(int[] nums) {
    int res = 0;
    for (int x : nums) {
        res ^= x;                   // pairs cancel; the single one remains
    }
    return res;
}

Watch it run, then see Missing Number.

Experts read the constraints before the story (①). Each question prunes the options. Tiny n at ② means enumerating everything is affordable. Sorted input at ③ almost always means two pointers or binary search is intended. Large n at ④ sets an O(n log n) budget, which points to sorting, heaps or hash maps.

"In place" or "O(1) space" means pointers and swaps, or using the input as its own marker storage.

Experts match signals in the wording to a short list of patterns, then verify the match against the constraints. "Longest substring" at ① suggests a sliding window. "Next greater" at ② suggests a monotonic stack. "Fewest steps" at ③ suggests BFS. "Count the ways" at ④ suggests dynamic programming. The full table:

Interviewers grade the process as much as the code, so use the same loop every time and narrate it. At ① you restate the problem and work one example. At ② you name candidate patterns. At ③ you state the brute force and its cost, then the better idea and why it is correct. At ④ you code while talking. At ⑤ you trace your example through the code, and if it breaks, the dashed arrow takes you back to the plan. At ⑥ you state the complexity and test the edge cases.

Experts optimise by asking what the brute force repeats. At ① every element triggers a fresh scan of the array: the repeated work is "search for a value". At ② that search is replaced by a hash-map lookup, so the loop at ③ does one O(1) check per element. The same question works everywhere:

Watch it run.

Each question below shows a short piece of code with one classic mistake. The diagram shows the first one. With marking on pop (①), B queues D but nothing marks it. C then queues D again, which gives the duplicate at ③. Marking on push (②) records D the moment it is queued, so C skips it.

A client (browser or app) asks a server for something, and the server responds. At ① DNS turns the name into an IP address, like looking up a phone number. At ② the client opens a TCP connection, plus a TLS handshake for HTTPS. At ③ it sends an HTTP request such as GET /users/42. At ④ the server's code reads the database, and at ⑤ the response returns with a status code (200 OK, 404 Not Found, 500 Server Error) and a body.

Every arrow is a network hop with its own latency and its own way to fail. Large systems add helpers along the path: a CDN near the user, a load balancer in front of many servers, a cache in front of the database.

Latency is how long one request takes. Throughput is how many requests are handled per second. At ① most requests are fast and the median (p50) is 50 ms, but a few take 2 seconds, so p99 is 2 s. Users who make many requests hit that tail often, which is why systems are judged by percentiles, not averages. At ② a request needs A, B and C to all be up, so at ③ their availabilities multiply: three 99.9% services give about 99.7%.

A database stores data durably and answers queries. A relational database keeps tables of rows with fixed columns, as at ①. An index, as at ②, is a sorted structure on a column, so "orders for user 42" jumps straight to the right rows instead of reading every row. Indexes cost extra writes and storage. At ③ a transaction groups statements so they happen all together or not at all: the money is never debited without being credited.

NoSQL stores trade some of this for scale or flexibility: key-value (Redis, DynamoDB), document (MongoDB), wide-column (Cassandra), graph.

An API is the contract for talking to a service. REST over HTTP maps actions onto resources: GET reads, POST creates, PUT replaces, DELETE removes. Idempotent means doing it twice has the same effect as once. GET, PUT and DELETE should be idempotent, POST usually is not. At ① the client sends a payment with a key, and at ② the server records it, but the response times out. At ③ the client retries with the same key. At ④ the server recognises the key and returns the stored result instead of charging again.

Other styles: gRPC for fast service-to-service calls, WebSockets for two-way live updates, and cursor pagination (?after=id123) instead of slow, shifting offsets.

Vertical scaling (①) means a bigger machine. It is simple, but it has a ceiling and stays a single point of failure. Horizontal scaling (②) puts many machines behind a load balancer, with no hard ceiling and with redundancy. It only works if the servers are stateless: at ③ sessions and other state live in a shared store, so any server can handle any request and servers can be added or removed freely.

Scale the stateless tier by adding servers. Scale the data tier with caching, replication and sharding, which is where the hard problems are.

In a distributed system, a network partition (①) will eventually happen: N1 has the new value, and N2 cannot hear about it. A client now asks N2. At ② a CP choice keeps the data consistent by refusing or delaying the answer. At ③ an AP choice stays available by answering with what it has, which may be stale, and reconciles later. When there is no partition, the trade-off becomes latency versus consistency, because waiting for replicas to agree takes time (PACELC).

Choose per feature, not per company: payments, inventory and bookings lean CP; feeds, likes and view counts lean AP.

Strong consistency means every read sees the latest write. Eventual consistency means replicas converge if writes stop. At ① the user's write reaches the primary, but at ② their read goes to a replica that has not received it yet, so they see the old bio. At ③ the update arrives, which is eventual consistency working as designed. At ④ read-your-own-writes fixes the visible symptom by sending that user's reads to the primary for a few seconds after a write. Monotonic reads is the related guarantee that a user never sees data go backwards in time.

DNS maps names to addresses through a hierarchy of servers, and answers are cached for a TTL. At ① DNS can also route: geo-DNS returns the address of a nearby CDN edge. At ② the edge, a cache close to the user, holds static files: images, video, scripts. At ③ a cache hit is served from the edge in a short hop. At ④ only misses travel to your origin, which fetches the file once and lets the edge keep it.

This is a pull CDN: the edge fetches a file on its first miss. A push CDN has you upload files to the edge ahead of time, which suits large files that rarely change.

Versioned file names (app.3f2a.js) let you cache files forever and still deploy instantly: a new build gets a new name, so no stale copy is ever served under it.

A load balancer spreads requests across servers. At ① a layer-7 balancer reads the HTTP request, so at ② it can route by path: /api/* to the API pool, /static/* to the file servers. Within a pool it picks a server by round robin, least connections or consistent hashing. At ③ health checks take a failing server out of rotation, so users never reach it. A layer-4 balancer only sees IPs and ports, which is faster but cannot route by content.

A reverse proxy (nginx, Envoy) sits in front of servers for TLS, compression, caching and rate limiting. A load balancer is a reverse proxy that spreads load. Run it redundantly, or it becomes the single point of failure.

Start with SQL (PostgreSQL, MySQL) unless you have a reason not to, as at ①: it gives transactions, joins, constraints and mature tooling, and one machine handles thousands of queries a second. Choose another store for a specific access pattern. At ② enormous write volume read by key suits wide-column or key-value stores. At ③ counters, sessions and leaderboards that need sub-millisecond reads suit Redis. At ④ images and video belong in object storage, with only their metadata and URL in the database. Full-text search usually runs in a search index alongside the main database.

Before sharding, two cheaper levers help. Federation splits databases by function, such as users in one and orders in another. Denormalisation stores copies of data so hot reads skip joins, at the cost of keeping the copies in sync.

Replication keeps copies of data on several nodes. At ① the common setup sends all writes to a leader, which streams changes to followers. At ② reads can go to followers, but with asynchronous replication they may be slightly stale, and a leader crash can lose its last few writes. At ③ failover promotes a follower; the danger is split brain, two nodes both acting as leader, which consensus (Raft) or fencing prevents. At ④ leaderless systems write to W nodes and read from R: when W + R > N, every read set overlaps every write set, as n2 does here, so a read always meets the latest write.

Leader-leader (multi-leader) replication accepts writes on several nodes, often one per region, so writes stay local. The cost is conflicts: two leaders can change the same row at once, and something must decide which change wins.

Sharding splits data so each node holds a subset. It is needed when one machine cannot hold the data or absorb the writes. At ① hash sharding spreads keys evenly, so the write load is balanced, but a range query such as "orders this week" must ask every shard. At ② range sharding keeps ranges together, which suits scans, but at ③ every new order lands on the newest shard: a hot spot while the others sit idle.

The shard key is the crucial decision: it must match the main access pattern and spread the load. Watch for cross-shard queries and transactions, hot keys (one celebrity account), and resharding cost, which consistent hashing or many small virtual shards reduce.

A cache keeps hot data in fast memory so most reads skip the slow source. In cache-aside, at ① the app asks Redis first. On a miss, at ② it reads the database, and at ③ it stores the row in Redis with a TTL, so the next read is a hit. On a write, at ④ the app updates the database, then at ⑤ deletes the cache key rather than writing the new value into it. Deleting avoids races where two writers update the cache in the opposite order to the database.

Redis values can be more than strings. A hash holds an object's fields, and a sorted set keeps a ranked list, such as a leaderboard or a timeline.

Caches are small, so they evict: LRU (least recently used) is the usual default, LFU keeps long-term favourites, and a TTL expires entries by age. At ① a hot key expires and every request that needs it misses at once and queries the database together: a cache stampede (thundering herd). At ② request coalescing lets one request hold a lock and rebuild the key while the others wait briefly or get the stale value, so at ③ the database sees one query. Jittered TTLs stop many keys expiring together, and early refresh rebuilds hot keys just before they expire.

A message queue holds tasks until a worker takes them. The producer does not wait for the slow consumer: decoupling. During a spike the backlog grows instead of the system falling over. At ① the consumer takes m1 and processes it, and at ② it acknowledges it, which removes it. At ③ the consumer crashes before acknowledging, so the queue delivers m1 again. Delivery is usually at-least-once, so consumers must be idempotent: deduplicate by message id or make the effect repeatable. A log or stream (Kafka) keeps an ordered, replayable record that many consumers read at their own pace.

A task queue (Celery, Sidekiq) is a message queue built for jobs. Each message names a function and its arguments, and the library runs the workers, retries with backoff, schedules delayed jobs and tracks results. A plain message queue (SQS, RabbitMQ) only moves messages, and the consumer decides what each one means. Use a task queue for background jobs inside one app, and a message queue or stream to pass events between services.

Backpressure is how a system says "slow down": bounded queues, rejecting work, or consumers pulling at their own pace.

With plain hash(key) % N, changing N remaps almost every key. Consistent hashing places both servers and keys on a ring, and a key belongs to the first server clockwise from it. At ① server E joins between A and B. At ② only the keys in the arc from A to E change owner, from B to E. At ③ every other key stays where it was. So adding or removing a server moves about 1/N of the keys. Virtual nodes place each server at many points on the ring, which evens out the load and spreads a failed server's keys across many survivors.