DoorDash Senior Full-Stack Developer Interview Preparation Guide

Direct answer

Eventual consistency means that after writes stop, all copies of the data will eventually agree, but there's a window, sometimes milliseconds, sometimes longer, during which different readers can see different, both "correct at the time" answers. For a non-technical stakeholder, the useful line is: the system prioritizes staying responsive everywhere over making everyone see the same thing at the exact same instant. Below are three analogies for that idea, each with the one place it will mislead if you don't say it out loud.

Choosing the analogy and what to omit

• Pick an analogy where the delay AND the reconciliation are both visible, not just the delay. Many weak analogies (mail, gossip) only show that news travels slowly; they hide the harder part, what happens when two people acted on different information during that delay.
• Decide up front which mechanism you're omitting: you're almost always omitting HOW the system decides which write wins when two conflict. Say that you're leaving it out, rather than letting the analogy imply there's no rule for it at all.
• Check understanding by asking them to predict a scenario, not recite the definition back: "if two people edit this at the same moment from different offices, what do you think happens?" A correct prediction means the model landed; an answer that assumes instant sync means you need to go back to the delay itself.
• The same shape, plain definition, one concrete example, why it matters, holds for any jargon-heavy term a non-technical audience needs defined on the spot: ETL vs ELT (does the transformation happen before or after loading), ACID vs BASE (strict correctness vs eventual, available correctness, which is this same idea from the database's side), or REST vs GraphQL (fetch a fixed shape of data vs ask for exactly the fields you need). Same competency, different vocabulary each time.

Worked example

1. A group chat where one person's phone is off. You send a message to a group chat; everyone online sees it in under a second. Someone whose phone died an hour ago won't see it until they turn it back on, at which point it downloads and they're caught up. What it shows well: the "everyone gets there eventually, but not at the same time" shape, and that being offline doesn't break the system, it just delays that one reader. Where it misleads: it implies messages simply queue up in order. If two people update the SAME piece of shared data while a third is disconnected, there can be a genuine conflict to resolve, not just a backlog to deliver, and the chat analogy has no equivalent of "two people edited the same message."

2. A retail chain updating a sale price across stores. Head office cuts a price. Each store's system checks for updates on its own schedule, so for a few minutes Store A shows the new price and Store B still shows the old one. What it shows well: the same data existing in multiple places, each catching up on its own timeline, with no single moment where everyone updates at once. Where it misleads: it suggests the only direction of change is head office to stores, one writer, many readers. Real eventually consistent systems often allow writes at multiple locations at once, a customer changing their address from two devices, and that's where the interesting conflicts and reconciliation rules actually come from.

3. Watering one end of a long garden bed. You water one end of a dry garden bed and moisture visibly spreads down the row over the next hour until it's evenly damp. What it shows well: gradual, automatic convergence toward one final state with no single "sync" event. Where it misleads: soil moisture always converges smoothly. Some real systems can get stuck in a genuine conflict that never resolves on its own, two writes with no way to tell which should win, and need a rule, or a human, to break the tie. "It'll just even out" is the sentence most likely to leave a stakeholder with a false sense of safety.

Trade-offs and pitfalls

The single biggest risk in any of these analogies is implying the temporary disagreement is harmless. For some products it is, a slightly stale follower count. For others it isn't, two systems both believing they hold the last unit of inventory. Say plainly which case you're in. Also resist stacking all three analogies in one conversation; one that survives a follow-up question beats three shallow ones, use the extra two only if the first one visibly didn't land.

Direct answer

Build a standing information diet from what the partner function already produces for itself, its goals or planning document, the metrics it is measured on, and its retro or release notes, and pair that with a recurring informal check-in with one counterpart in that function. You are not trying to get invited into their planning meeting; you are trying to read what they optimize for, and occasionally confirm your read against a real person.

Structured elaboration

The habit that ties these together: translate their metric into one sentence you could say back to them and have them agree it is accurate, then test that sentence the next time you talk. If you cannot state their current priority in a sentence they would sign off on, your information diet has a gap.

Worked example

Suppose you regularly partner with a support or customer-success function but are not in their planning. Their quarterly goals page (a document they publish for their own team) states the goal is "reduce median response time." Reading that before proposing a change that would meaningfully increase inbound volume lets you flag the likely trade-off to your counterpart ahead of launch, rather than finding out after the fact that you worked against their stated goal. The artifact told you what they were measured on; the counterpart conversation confirmed it was still current.

Trade-offs & pitfalls

• Relying only on artifacts risks reading a goal that is stale or aspirational and no longer reflects what the team is actually prioritizing day to day.
• Relying only on a single counterpart's opinion risks mistaking one person's take for the function's actual priority, especially if that person is not close to how the team's metrics are reviewed.
• A common miss: reading the dashboard but never validating the interpretation with anyone in that function, which produces confidently wrong assumptions that only surface when a decision already went the wrong way.
• The senior differentiator on an easy-sounding question like this is treating it as a standing habit built before you need it, rather than something you scramble to learn only after a conflict has already surfaced.

The idea

Every way to climb is a sequence of 1s and 2s that adds up to n. Look only at the last move: it was either a 1-step from stair n-1 or a 2-step from stair n-2. Those two groups do not overlap and together cover every climb, so the count for n is the count for n-1 plus the count for n-2. That is a recurrence (a formula that defines each value from smaller ones), and the numbers it produces are the Fibonacci numbers: the sequence 1, 1, 2, 3, 5, 8, 13, ... in which every term is the sum of the two before it.

The five things to state

1. What one cell means. ways[i] is the number of different sequences of 1-steps and 2-steps whose total is exactly i.
2. The transition. ways[i] = ways[i-1] + ways[i-2]. Every sequence for i ends in 1 (the rest is any sequence for i-1) or ends in 2 (the rest is any sequence for i-2), and never both, so nothing is missed or counted twice.
3. Base cases. ways[0] = 1 (the empty sequence: you are already at the start) and ways[1] = 1 (just [1]). The recurrence needs two earlier cells, so it can only start at i = 2.
4. Fill order. Ascending i, because each cell reads two smaller indices.
5. Where the answer is. ways[n]. For n = 5 it is 8, and the filled table and the list of all eight sequences in the output below show why.

Brute force first

Plain recursion ways(n) = ways(n-1) + ways(n-2) recomputes the same subproblems again and again. Counting every call, the root included, gives 15 calls for n = 5, 177 for n = 10, 21,891 for n = 20 and 2,692,537 for n = 30. Each call count is exactly 2 * ways(n) - 1, so the work grows like the answer itself, roughly 1.6 times per extra stair. The memoized version (memoization means remembering the result for each argument so it is computed once) makes 2n - 1 calls: 9, 19, 39 and 59 for the same inputs. The table version removes the recursion altogether.

The code

import random

calls = 0


def ways_brute(n):
    """Plain recursion: ways(n) = ways(n-1) + ways(n-2)."""
    global calls
    calls += 1
    if n <= 1:
        return 1
    return ways_brute(n - 1) + ways_brute(n - 2)


def ways_memo(n, memo=None, counter=None):
    """Same recursion, but each n is computed once."""
    if memo is None:
        memo, counter = {}, [0]
    counter[0] += 1
    if n <= 1:
        return 1, counter[0]
    if n not in memo:
        a, _ = ways_memo(n - 1, memo, counter)
        b, _ = ways_memo(n - 2, memo, counter)
        memo[n] = a + b
    return memo[n], counter[0]


def ways_table(n):
    """ways[i] = number of 1-or-2-step sequences that sum to exactly i."""
    ways = [0] * (n + 1)
    ways[0] = 1                      # the empty sequence
    if n >= 1:
        ways[1] = 1
    for i in range(2, n + 1):
        ways[i] = ways[i - 1] + ways[i - 2]
    return ways


def ways_const_space(n):
    prev2, prev1 = 1, 1              # ways[0], ways[1]
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1                     # ways[1] when n == 1, ways[0] when n == 0 is also 1


def ways_const_space_wrong(n):
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2 = prev1                # overwrites prev2 first
        prev1 = prev1 + prev2        # now adds prev1 to itself
    return prev1


def enumerate_sequences(n):
    if n == 0:
        return [[]]
    out = []
    for step in (1, 2):
        if step <= n:
            out += [[step] + rest for rest in enumerate_sequences(n - step)]
    return out


n = 5
print("filled table for n=5:", ways_table(n))
print("all sequences for n=5:", enumerate_sequences(5))
for n in (5, 10, 20, 30):
    calls = 0
    ways_brute(n)
    value, memo_calls = ways_memo(n)
    print(f"n={n:2d} ways={value:7d} brute_calls={calls:8d} memo_calls={memo_calls}")
print("n=0 ->", ways_const_space(0), " n=1 ->", ways_const_space(1), " n=2 ->", ways_const_space(2))
print("n=5 correct update:", ways_const_space(5), " wrong update order:", ways_const_space_wrong(5))

random.seed(7)
for _ in range(300):
    n = random.randint(0, 18)
    expected = len(enumerate_sequences(n))
    assert ways_table(n)[n] == ways_const_space(n) == ways_memo(n)[0] == expected
print("300 random n in 0..18 agree with explicit enumeration")
fib_a, fib_b = 1, 1                  # F(1), F(2)
for n in range(0, 40):
    assert ways_const_space(n) == fib_a  # ways(n) is the Fibonacci number F(n+1)
    fib_a, fib_b = fib_b, fib_a + fib_b
print("ways(n) equals the Fibonacci number F(n+1) for n in 0..39")
print("ratio ways(30) / ways(29) =", round(ways_const_space(30) / ways_const_space(29), 6),
      "| (1 + sqrt(5)) / 2 =", round((1 + 5 ** 0.5) / 2, 6))
n = 0
while ways_const_space(n) <= 2**63 - 1:
    n += 1
print("first n whose count exceeds a signed 64-bit integer:", n, "| ways(n-1) =", ways_const_space(n - 1))

Output:

filled table for n=5: [1, 1, 2, 3, 5, 8]
all sequences for n=5: [[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 2, 1, 1], [1, 2, 2], [2, 1, 1, 1], [2, 1, 2], [2, 2, 1]]
n= 5 ways=      8 brute_calls=      15 memo_calls=9
n=10 ways=     89 brute_calls=     177 memo_calls=19
n=20 ways=  10946 brute_calls=   21891 memo_calls=39
n=30 ways=1346269 brute_calls= 2692537 memo_calls=59
n=0 -> 1  n=1 -> 1  n=2 -> 2
n=5 correct update: 8  wrong update order: 16
300 random n in 0..18 agree with explicit enumeration
ways(n) equals the Fibonacci number F(n+1) for n in 0..39
ratio ways(30) / ways(29) = 1.618034 | (1 + sqrt(5)) / 2 = 1.618034
first n whose count exceeds a signed 64-bit integer: 92 | ways(n-1) = 7540113804746346429

Reading the output

• The sequence grows by a nearly constant factor: the ratio of one term to the one before it settles at (1 + sqrt(5)) / 2, about 1.618 (the ratio line). That is where the 1.618 in the plain-recursion row of the table below and the "roughly 1.6 times per extra stair" above come from.
• The filled table [1, 1, 2, 3, 5, 8] is ways[0] to ways[5]; its last cell is the answer 8, and the eight listed sequences are all of them.
• ways(n) equals the Fibonacci number F(n+1), where F(1) = F(2) = 1. The check loop asserts that for every n from 0 to 39.
• Constant space: only ways[i-1] and ways[i-2] are ever read, so two variables replace the list. The update must be a simultaneous assignment prev2, prev1 = prev1, prev1 + prev2. The wrong version first overwrites prev2 with prev1 and then adds prev1 to itself, so every step doubles and n = 5 prints 16 instead of 8.
• The random check compares the table, the memoized version and the constant-space version against explicit enumeration of every sequence on 300 seeded cases with n from 0 to 18.

Complexity

The call stack is the list of function calls that have started but are still waiting for their sub-calls to return, and its depth is how many wait at once; plain recursion and the memoized version both go n calls deep before the first return. On CPython that depth is capped: the memoized version hits the default 1000-frame limit for n near 1000; the loop versions do not.

Edge cases and common mistakes

• n = 0 returns 1 (one way to do nothing) and n = 1 returns 1, as printed. Some problem statements start at n = 1; say which convention you use.
• Python integers never overflow, but in a fixed-width language the count exceeds a signed 64-bit integer at n = 92, as the last line of the output shows. Ask whether a modulus is wanted.
• Updating the two rolling variables one at a time in the wrong order, shown above.

Follow-ups

Allowing steps of 1, 2 or 3 turns the recurrence into a sum of three terms. Forbidding some stairs sets ways[i] = 0 on those stairs. For very large n the same recurrence is a 2 x 2 matrix power, which takes O(log n) multiplications.

Running the code

python3.12 climb_stairs.py

Standard library only. Save the listing as climb_stairs.py and run the command above; it prints exactly the output shown.

Direct answer

For an API gateway that needs header-based routing, TLS termination, and WebSocket support, choose a Layer 7 load balancer, typically a purpose-built API gateway built on an L7 proxy such as Envoy or NGINX. All three requirements only make sense above the transport layer: header inspection and TLS termination require parsing beyond TCP, and correct WebSocket support means handling the HTTP Upgrade handshake and then holding the resulting connection open as a long-lived stream rather than a short request/response cycle.

Structured elaboration

• Header-based routing needs the balancer to read the HTTP request line and headers, which is by definition an L7 operation; an L4 balancer only sees IP and port.
• TLS termination at the gateway centralizes certificate management and lets the gateway apply routing decisions to the decrypted request; an L4 balancer would have to pass TLS through untouched, which is incompatible with header-based routing.
• WebSocket support requires the proxy to recognize the Upgrade: websocket handshake, respond correctly, and then treat the connection as a long-lived, low-request-rate stream instead of applying HTTP request timeouts to it.

Session affinity: L7 gateways can implement affinity via cookies or a header-based token, which survives client IP changes (mobile networks, corporate NAT). Prefer stateless backends with a shared session store over affinity where possible, since affinity re-couples scaling to specific instances: pinning a client's requests to one backend means that backend cannot be drained, replaced, or autoscaled away without either breaking that client's session or running a migration step first, unlike a stateless backend, which any instance can serve interchangeably. For a WebSocket connection specifically that coupling is even tighter, the connection itself is pinned to one backend process for its entire lifetime by the nature of a long-lived stream, so scaling in an instance mid-connection always terminates every WebSocket it is holding, whether or not cookie-based affinity is even in use.

Health checks: use active HTTP checks against a readiness endpoint, and make sure the check reflects the ability to accept a WebSocket upgrade, not just answer a plain GET. A backend that fails upgrades but passes a generic HTTP check will look healthy while breaking every WebSocket client.

Autoscaling: centralizing TLS and routing on the gateway makes it critical infrastructure, so it must scale independently of the backends and stay stateless (shared config, no local session state). Backend autoscaling should key off concurrent connections for WebSocket-heavy services, not just CPU, since an idle WebSocket connection holds a slot without generating CPU load.

Worked example

The same gateway often serves two very different endpoints. A /v1/search endpoint returns small JSON responses quickly and can use small buffers and short timeouts. A /v1/uploads bulk-ingestion endpoint accepts large file payloads and needs the gateway to stream the request body to the backend rather than fully buffering it first, plus a much longer idle timeout. Configuring both endpoints with the same defaults turns the L7 tier into exactly the kind of bottleneck it was chosen to avoid: the search path gets timeouts that are too generous, and the upload path either times out mid-transfer or forces the gateway to hold large payloads in memory. The fix is per-route configuration (buffering, body size limits, timeouts) rather than one global policy for the whole gateway.

Trade-offs & pitfalls

• Centralizing TLS and routing on one L7 tier makes it a high-value target for both attacks and outages; it must be horizontally scaled and kept stateless or it becomes the new single point of failure.
• WebSocket connections do not fit request-count or CPU-based autoscaling signals well, since an idle connection still occupies a slot; scale on concurrent connections too.
• Sticky sessions look like the easy fix for keeping a client's WebSocket routing consistent, but they reintroduce the coupling between traffic and specific instances that choosing L7 with a shared store was meant to avoid.

Direct answer

I treat this as a decision-making process problem, not a technical one: gather input broadly but make the actual call with a small accountable group, pilot the standard on a real team before mandating it org-wide, communicate the reasoning and not just the rule, and measure adoption with an honest, mechanically-enforced signal rather than assuming a written standard changes behavior on its own.

Structured elaboration

Gather input

Survey affected teams for their current conventions and actual friction, not just preferences, so the decision is grounded in real problems (for example, "our formatter conflicts with theirs when we share a monorepo") rather than taste. Reduce the debate to 2-3 genuinely competing proposals rather than open-ended bikeshedding; most style disagreements collapse to a small number of real axes, like import ordering or naming convention.

Weigh technical trade-offs

Favor whichever option has the strongest tooling support (an existing auto-formatter, mature editor integration, linter support) over one that's marginally nicer but manual to enforce, since manual enforcement is where standards quietly die. Weigh switching cost too: a team with a large existing codebase in the new language has more sunk cost in its current convention than a team just starting out.

Pilot before mandating

Pick one or two willing teams to adopt the standard for a real sprint or two, not a toy example, and explicitly ask what broke, what felt like friction, and what they'd change before finalizing anything.

Communicate the decision

Publish the reasoning, not just the rule: why this option over the alternatives, and what trade-offs were accepted. Give a clear timeline, a grace period, and name who to raise disagreement with.

Measure adoption and minimize disruption

Track adoption through the automated formatter or linter's own pass/fail rate in CI (continuous integration, the automated build/test pipeline) across repos, an honest signal since it's mechanically enforced rather than self-reported. Roll out with tools that fix code automatically instead of requiring manual compliance, the single biggest lever for minimizing disruption. Grandfather existing code with format-on-touch (only reformat files as they're naturally edited) rather than one disruptive mass reformat that breaks blame history and floods review queues.

Worked example

Three teams adopting a new backend language disagree on import-ordering and error-handling conventions. I run a two-week input-gathering round: two teams prefer style A, matching their existing microservices; one team already has 40,000 lines in style B, a shared library they don't want to rewrite. Rather than forcing a binary choice, I pick style A as the org standard, since it has better tooling support (an existing auto-formatter plugin), but scope the rollout as format-on-touch: new and touched files get reformatted automatically by CI, while untouched legacy files in the third team's library keep style B until they're naturally edited, with a linter configuration that doesn't flag the legacy files. I publish a short doc explaining the tooling reasoning and the grandfather policy, pilot on the first team for two weeks, adjust the auto-formatter's import-grouping rule after they report false-positive linter noise, then roll out to the other two teams. I track adoption as the percentage of touched files in each repo that pass the new formatter in CI, which climbs past 90% within a month without anyone manually reformatting anything.

Trade-offs and pitfalls

• Forcing a big-bang reformat of an entire existing codebase creates a disruptive diff that breaks git blame and swamps review queues; format-on-touch avoids this at the cost of a longer period of inconsistency
• Deciding by committee vote often produces a compromise nobody's tooling actually supports well; weigh tooling maturity heavily, not just preference counts
• Skipping the pilot and mandating org-wide immediately is the most common way this backfires, since the standard hasn't been tested against a real team's actual workflow
• Publishing a rule without publishing the reasoning breeds quiet non-compliance; people follow standards they understand the "why" of far more reliably

Direct answer

Huffman coding is optimal among prefix-free codes because repeatedly merging the two lowest-frequency nodes builds the encoding tree bottom-up in exactly the order that minimizes total weighted path length (each symbol's frequency times its code length, summed over all symbols). Merging any other pair first can strand a frequent symbol deeper than it needs to be, which strictly increases the encoded size.

Structured elaboration

Build procedure: put every symbol in a min-heap keyed by frequency; while more than one node remains, pop the two smallest, create a parent whose frequency is their sum, and push it back; the last remaining node is the tree's root. Assigning 0/1 to left/right edges yields prefix-free codes, since every symbol sits at a distinct leaf.

import heapq
from collections import Counter

def build_huffman_codes(freqs: dict[str, int]) -> dict[str, str]:
    """
    freqs: symbol -> frequency (must have >= 2 distinct symbols).
    Returns symbol -> binary code string.
    """
    if len(freqs) < 2:
        raise ValueError("need at least 2 distinct symbols for a prefix tree")

    counter = 0
    heap = []
    for sym, f in freqs.items():
        heapq.heappush(heap, (f, counter, sym))
        counter += 1

    while len(heap) > 1:
        f1, _, n1 = heapq.heappop(heap)
        f2, _, n2 = heapq.heappop(heap)
        merged = (n1, n2)
        heapq.heappush(heap, (f1 + f2, counter, merged))
        counter += 1

    _, _, root = heap[0]
    codes: dict[str, str] = {}

    def walk(node, prefix):
        if isinstance(node, tuple):
            walk(node[0], prefix + "0")
            walk(node[1], prefix + "1")
        else:
            codes[node] = prefix or "0"  # single-symbol edge case

    walk(root, "")
    return codes


def encoded_length_bits(freqs: dict[str, int], codes: dict[str, str]) -> int:
    return sum(freqs[s] * len(codes[s]) for s in freqs)


message = "abracadabra"
freqs = dict(Counter(message))
print("frequencies:", freqs)

codes = build_huffman_codes(freqs)
for s in sorted(codes, key=lambda s: (-freqs[s], s)):
    print(f"  {s!r}: freq={freqs[s]} code={codes[s]} (len {len(codes[s])})")

huff_bits = encoded_length_bits(freqs, codes)
fixed_bits = len(message) * 3  # 5 distinct symbols -> ceil(log2(5)) = 3 bits fixed-width
print(f"Huffman total bits: {huff_bits}")
print(f"Fixed-width (3 bits/symbol) total bits: {fixed_bits}")

Output:

frequencies: {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}
  'a': freq=5 code=0 (len 1)
  'b': freq=2 code=110 (len 3)
  'r': freq=2 code=111 (len 3)
  'c': freq=1 code=100 (len 3)
  'd': freq=1 code=101 (len 3)
Huffman total bits: 23
Fixed-width (3 bits/symbol) total bits: 33

Why the greedy order is optimal (exchange argument sketch): take any optimal prefix tree. Among its deepest leaves, if the two globally-lowest-frequency symbols aren't already siblings there, swap them into those two deepest sibling positions; that swap can only lower or keep equal the total weighted path length, since moving a low-frequency symbol deeper (and a higher-frequency one shallower) never increases the frequency-times-depth sum. So an optimal tree with this sibling property always exists. Once those two symbols are fixed as siblings, merge them into one "super-symbol" of combined frequency; the same greedy step is optimal on the resulting (n-1)-symbol problem by induction, which is exactly what "always merge the two smallest" does at every level.

What breaks with a different merge order: merging arbitrary (not-lowest) nodes can pull a high-frequency symbol away from the root and bury it several merge levels deep before anything forces it back up, inflating its code length instead of shrinking it.

Worked example

For the weighted path length $\text{WPL}(T) = \sum_{s \in \Sigma} f(s)\cdot \text{depth}_T(s)$, applying the wrong merge rule (always combining the two LARGEST nodes first, instead of the two smallest) to the same "abracadabra" frequencies produces a tree whose weighted path length is 37 bits, worse than the fixed-width 33-bit baseline and far worse than the correct Huffman tree's 23 bits: the frequent symbol 'a' (frequency 5) gets buried under extra merges instead of staying near the root.

import heapq

freqs = {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}

def weighted_path_length(node, depth=0):
    if isinstance(node, tuple):
        return (weighted_path_length(node[0], depth + 1)
                + weighted_path_length(node[1], depth + 1))
    return freqs[node] * depth

# Correct order: merge the two SMALLEST nodes each step (standard Huffman).
counter = 0
heap = [(f, i, s) for i, (s, f) in enumerate(freqs.items())]
counter = len(heap)
heapq.heapify(heap)
while len(heap) > 1:
    f1, _, n1 = heapq.heappop(heap)
    f2, _, n2 = heapq.heappop(heap)
    heapq.heappush(heap, (f1 + f2, counter, (n1, n2)))
    counter += 1
_, _, optimal_root = heap[0]
print("optimal weighted path length (bits):", weighted_path_length(optimal_root))

# Bad order: at each step, merge the two HIGHEST-frequency nodes instead.
counter = 0
heap2 = [[f, i, s] for i, (s, f) in enumerate(freqs.items())]
counter = len(heap2)
while len(heap2) > 1:
    heap2.sort(key=lambda x: -x[0])  # sort descending, take two largest
    f1, _, n1 = heap2.pop(0)
    f2, _, n2 = heap2.pop(0)
    heap2.append([f1 + f2, counter, (n1, n2)])
    counter += 1
_, _, bad_root = heap2[0]
print("bad-order (merge two largest first) weighted path length (bits):", weighted_path_length(bad_root))

Output:

optimal weighted path length (bits): 23
bad-order (merge two largest first) weighted path length (bits): 37

Complexity

Building the tree is $O(n \log n)$ for $n$ distinct symbols ($n-1$ heap merges, each
$O(\log n)$); encoding a message of length $m$ is $O(m)$; memory is $O(n)$ for the
tree/codebook.

Edge cases

• Ties in frequency: any tie-break among equally-small nodes preserves the optimal total
  length (though it can change WHICH codeword a given symbol gets); canonical Huffman fixes a
  deterministic tie-break so encoder and decoder agree, which matters for decodability, not for
  optimality itself.
• Single-symbol alphabet is a degenerate edge case: assign a length-1 code by convention,
  since there is nothing to disambiguate.
• Fewer than 2 distinct symbols: build_huffman_codes explicitly raises ValueError when
  len(freqs) < 2, since a prefix tree needs at least two leaves to have anything to
  disambiguate.

Trade-offs & pitfalls

• Static vs adaptive: this build requires knowing (or transmitting) the frequency table up front; if the true distribution drifts mid-stream, adaptive Huffman (the Vitter algorithm) or arithmetic/range coding track a moving distribution without a fixed prior codebook, at the cost of more per-symbol bookkeeping.
• Where Huffman itself falls short: Huffman is optimal only among prefix codes with INTEGER-length codewords per symbol; a symbol with true probability 0.9 "wants" roughly 0.15 bits under the Shannon bound, but no prefix code can give any symbol fewer than 1 bit. For very skewed, single-dominant-symbol distributions, arithmetic or range coding packs closer to the entropy bound than Huffman ever can.

Approach: Use Python's built-in collections.OrderedDict, which is a hash map that also maintains insertion/access order internally (backed by a doubly linked list under the hood) - move_to_end and popitem(last=False) give the O(1) reordering and eviction primitives directly, without hand-rolling the linked-list pointer surgery.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)  # mark as most-recently-used
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)  # evict least-recently-used

Key points: get and put are each O(1) amortized because OrderedDict maintains its internal doubly linked list alongside the hash table, so move_to_end and popitem(last=False) are O(1) list-splice operations, not O(n) scans. Capacity is enforced on every put by evicting the oldest entry once size exceeds capacity.

Complexity: Both get and put are $O(1)$ time. Space is $O(\text{capacity})$, since the cache never holds more than capacity entries.

Edge cases: capacity 0 is rejected explicitly (a cache that can hold nothing is a degenerate case worth guarding); updating an existing key's value correctly refreshes its recency without growing the cache past capacity; requesting a missing key returns a sentinel (-1 here, following the common LeetCode convention) rather than raising, though a production cache would more idiomatically raise KeyError or return None.

Worked example / execution verification

cache = LRUCache(2)
cache.put(1, 'a')
cache.put(2, 'b')
print(cache.get(1))       # promotes 1 to most-recent -> 'a'
cache.put(3, 'c')         # over capacity, evicts 2 (least-recently-used)
print(cache.get(2))       # -1, was evicted
print(cache.get(1))       # 'a', still present
print(cache.get(3))       # 'c', still present

Executed: output is a, -1, a, c - exactly matching the hand-traced sequence from the conceptual companion question (key 2 is correctly evicted because the get(1) call promoted 1 ahead of it, leaving 2 as the least-recently-used entry when 3 was inserted over capacity).

Trade-offs & pitfalls

• OrderedDict is not thread-safe - concurrent get/put calls from multiple threads need an external lock (or a striped-lock / lock-free design, at the cost of significant added complexity) if this cache backs a multi-threaded service.
• Hand-rolling the hash-map-plus-doubly-linked-list structure explicitly (rather than relying on OrderedDict) is worth being able to do too - some interviewers specifically want to see the pointer manipulation, since OrderedDict is "using a library that already solved it."
• For very large caches, consider whether the per-entry overhead of a linked-list node plus hash-map entry (roughly 3-4x a raw value's memory footprint in CPython) is acceptable, or whether a more compact structure (e.g. a ring buffer indexed by insertion slot, at the cost of O(capacity) eviction scans) is a better fit for the memory budget.

Direct answer

The deciding question is what is flexible. If widgets only vary in which fields they show on a known set of entities, a small set of composite REST endpoints (each calling the services in parallel and returning one client-shaped response) is cheaper to run and easier to cache. If widgets vary in which relationships and nesting they traverse (users, their posts, each post's comments, in changing combinations) and many teams add widgets, adopt GraphQL. For this dashboard (nested users, posts and comments, flexible fields per widget) I would choose GraphQL as a single BFF-style layer in front of the three services, provided I ship batching, a depth limit and field-level authorization with it. Without those, the composite endpoint is the safer choice.

Measured: backend calls for the same dashboard

Terms used below. A BFF (backend for frontend) is a server layer built for one client's screens that calls the underlying services and returns what the screen needs. A resolver is the function GraphQL runs to produce the value of one field in a query. DataLoader is a small library that groups many single-item lookups made close together into one batched lookup. Field-level authorization means checking, inside each field's resolver, whether this caller may see that field, for example letting anyone read User.name but only the user themselves read User.email.

The script serves one dashboard of 10 posts (each with an author and 3 comments, each comment with an author) three ways and counts calls to the three services. Run in a Node 22 container:

docker run --rm -v "$PWD":/w -w /w node:22 sh -c 'npm i --no-audit --no-fund graphql@16 dataloader@2 && node dashboard.mjs'

dashboard.mjs:

// Run: npm i graphql@16 dataloader@2 && node dashboard.mjs   (Node 22)
import { buildSchema, graphql, parse, validate, specifiedRules, GraphQLError } from 'graphql';
import DataLoader from 'dataloader';

// ---- three "services"; every call is counted ----
const calls = { users: 0, posts: 0, comments: 0 };
const U = Array.from({ length: 40 }, (_, i) => ({ id: i + 1, name: `User ${i + 1}`, email: `u${i + 1}@example.com` }));
const P = Array.from({ length: 10 }, (_, i) => ({ id: i + 1, title: `Post ${i + 1}`, authorId: i + 1 }));
const C = P.flatMap(p => Array.from({ length: 3 }, (_, k) => ({ id: p.id * 10 + k, postId: p.id, authorId: 11 + ((p.id * 3 + k) % 20), text: 'hi' })));
const svc = {
  posts: async () => { calls.posts++; return P; },
  user: async id => { calls.users++; return U.find(u => u.id === id); },
  usersByIds: async ids => { calls.users++; return ids.map(id => U.find(u => u.id === id)); },
  commentsByPost: async pid => { calls.comments++; return C.filter(c => c.postId === pid); },
  commentsByPosts: async pids => { calls.comments++; return pids.map(pid => C.filter(c => c.postId === pid)); },
};
const reset = () => { calls.users = calls.posts = calls.comments = 0; };
const total = () => calls.users + calls.posts + calls.comments;

// ---- Option A: composite REST endpoint, batch calls written by hand ----
async function dashboardEndpoint() {
  const posts = await svc.posts();
  const [commentLists] = await Promise.all([svc.commentsByPosts(posts.map(p => p.id))]);
  const uids = [...new Set([...posts.map(p => p.authorId), ...commentLists.flat().map(c => c.authorId)])];
  const users = new Map((await svc.usersByIds(uids)).map(u => [u.id, u]));
  return posts.map((p, i) => ({ id: p.id, title: p.title, author: users.get(p.authorId).name,
    comments: commentLists[i].map(c => ({ text: c.text, author: users.get(c.authorId).name })) }));
}

// ---- Option B: GraphQL, naive resolvers vs DataLoader ----
const schema = buildSchema(`
  type User{id:ID! name:String! email:String!}
  type Comment{text:String! author:User! post:Post!}
  type Post{id:ID! title:String! author:User! comments:[Comment!]!}
  type Query{posts:[Post!]!}`);
const naive = () => ({ posts: svc.posts });
const withUsers = {
  Post: { author: (p, _, ctx) => ctx.user.load(p.authorId), comments: (p, _, ctx) => ctx.comments.load(p.id) },
  Comment: { author: (c, _, ctx) => ctx.user.load(c.authorId) },
};
const makeCtx = () => ({ user: new DataLoader(ids => svc.usersByIds([...ids])), comments: new DataLoader(ids => svc.commentsByPosts([...ids])) });   // new loaders per request
const resolveField = (batched) => (src, args, ctx, info) => {
  const t = info.parentType.name, f = info.fieldName;
  if (t === 'Query') return svc.posts();
  if (batched && withUsers[t]?.[f]) return withUsers[t][f](src, args, ctx);
  if (f === 'author') return svc.user(src.authorId);
  if (f === 'comments') return svc.commentsByPost(src.id);
  return src[f];
};
const Q = '{posts{id title author{name} comments{text author{name}}}}';
const run = async (batched, q = Q) => graphql({ schema, source: q, contextValue: makeCtx(), fieldResolver: resolveField(batched), rootValue: {} });

reset(); const rest = await dashboardEndpoint();
console.log('composite endpoint        backend calls:', total(), JSON.stringify(calls), 'rows:', rest.length);
reset(); let r = await run(false);
console.log('GraphQL, per-field fetch  backend calls:', total(), JSON.stringify(calls), 'errors:', r.errors?.length ?? 0);
reset(); r = await run(true);
console.log('GraphQL + DataLoader      backend calls:', total(), JSON.stringify(calls), 'errors:', r.errors?.length ?? 0);
console.log('same data both ways:', JSON.stringify(r.data.posts.map(p => ({ id: +p.id, title: p.title, author: p.author.name, comments: p.comments.map(c => ({ text: c.text, author: c.author.name })) }))) === JSON.stringify(rest));

// ---- query depth limit as a validation rule (runs before any resolver) ----
// Fragment spreads are followed, otherwise `{posts{...F}}` hides the depth inside fragment F.
const depthRule = max => ctx => ({ OperationDefinition(node) {
  const frags = new Map(ctx.getDocument().definitions.filter(x => x.kind === 'FragmentDefinition').map(f => [f.name.value, f]));
  const memo = new Map();                                        // height of each fragment, computed once: a fragment spread twice must not be walked twice
  const height = (sel, seen) => Math.max(0, ...sel.selections.map(s => {
    if (s.kind === 'FragmentSpread') {
      const name = s.name.value, f = frags.get(name);
      if (!f || seen.has(name)) return 0;                        // unknown or cyclic spread: the standard validation rules report it
      if (!memo.has(name)) memo.set(name, height(f.selectionSet, new Set(seen).add(name)));
      return memo.get(name);
    }
    if (s.kind === 'InlineFragment') return height(s.selectionSet, seen);
    return 1 + (s.selectionSet ? height(s.selectionSet, seen) : 0);
  }));
  const depth = height(node.selectionSet, new Set());
  if (depth > max) ctx.reportError(new GraphQLError(`depth ${depth} exceeds ${max}`)); } });
// A query that spreads one fragment twice at each of 30 levels: 2^30 paths if every spread were walked again.
const bomb = '{posts{...F0}} ' + Array.from({ length: 30 }, (_, k) => `fragment F${k} on Post{...F${k + 1} ...F${k + 1}}`).join(' ') + ' fragment F30 on Post{comments{post{comments{author{name}}}}}';
for (const [name, q] of [
  ['dashboard query', Q],
  ['deep query', '{posts{comments{post{comments{author{name}}}}}}'],
  ['deep via fragment', '{posts{...F}} fragment F on Post{comments{post{comments{author{name}}}}}'],
  ['fragment bomb', bomb],
]) {
  const errs = validate(schema, parse(q), [...specifiedRules, depthRule(4)]);
  console.log(name.padEnd(18), errs.length ? 'rejected: ' + errs[0].message : 'accepted');
}

Output:

composite endpoint        backend calls: 3 {"users":1,"posts":1,"comments":1} rows: 10
GraphQL, per-field fetch  backend calls: 51 {"users":40,"posts":1,"comments":10} errors: 0
GraphQL + DataLoader      backend calls: 4 {"users":2,"posts":1,"comments":1} errors: 0
same data both ways: true
dashboard query    accepted
deep query         rejected: depth 6 exceeds 4
deep via fragment  rejected: depth 6 exceeds 4
fragment bomb      rejected: depth 6 exceeds 4

• Composite endpoint: 3 backend calls (posts, comments for all posts, users for all authors), written by hand with batch endpoints (usersByIds, commentsByPosts).

• GraphQL with a resolver per field and no batching: 51 calls: 1 for posts, 10 for comments (one per post), 40 for users (10 post authors plus 30 comment authors). This is the N+1 problem: one query for the list plus one per item.

• GraphQL with DataLoader: 4 calls. The event loop is the JavaScript runtime's cycle of running one queued piece of work after another; one pass of it is a tick. Per the DataLoader documentation, it collects every key requested within a single tick of the event loop and then calls the batch function (the function you give it, which receives an array of keys and returns the values in the same order) once. In this dashboard the lookups happen in two waves:

  1. After posts returns, GraphQL runs the author and comments resolvers for all 10 posts in the same tick. That produces 10 user loads (ids 1 to 10, one call to usersByIds) and 10 comment loads (one call to commentsByPosts).
  2. Only once the comments exist can GraphQL ask who wrote them. The 30 comment authors are 20 distinct ids (11 to 30), so DataLoader sends one second usersByIds call with 20 ids.

  Calls: 1 posts + 1 comments + 2 users = 4. The hand-written endpoint needed 1 user call because it could gather all author ids from both levels before asking. The same data comes back both ways.

Batching only works if the services offer batch endpoints (usersByIds); otherwise the loader just hides N calls inside a loop.

Reading the resolver code

• resolveField(batched) is one function GraphQL calls for every field in the response. info.parentType.name and info.fieldName say which field this is, such as Post and author.
• For Query.posts it calls the posts service. If batched is true and the field has an entry in withUsers, it uses the DataLoader version (ctx.user.load(id), ctx.comments.load(id)). Otherwise author and comments call the service once per parent row, which is where the 51 calls come from. Any other field just reads the property from the source object.
• makeCtx() builds a fresh pair of loaders for each request and passes them in as the context, so no loader cache outlives a request.
• depthRule(max) is a validation rule: it visits each operation, measures how many levels of nested selections the query has with the small recursive function height, and calls ctx.reportError if the depth exceeds max. A fragment is a named, reusable piece of a query (fragment F on Post{...}) that other selections pull in with ...F; height follows those spreads, because a rule that only counted the braces written directly under the operation would accept {posts{...F}} with the deep part hidden inside F. It measures each named fragment once and keeps the result in memo, because a query can spread the next fragment twice at every level of a chain of fragments. Walking every spread afresh doubled the work with each level (1.6 seconds at 22 levels and 6.9 seconds at 24 in a run of that version, and a 30-level chain did not finish in 80 seconds), so the guard itself became the cheapest way to tie up the server. The fragment bomb line in the output is such a 30-level chain, and it is rejected at once. Validation runs before execution, which is why the deep query makes zero backend calls.

Consequences of each option

Keeping each option healthy under load

GraphQL:

• Batch with loaders created per request. A loader shared across requests caches one user's data and can serve it to another.
• Validate depth before execution: the script's depth rule accepts the dashboard query (depth 4) and rejects {posts{comments{post{comments{author{name}}}}}} with "depth 6 exceeds 4" before any resolver runs, including when the same deep selection is hidden inside a named fragment, or behind a chain of fragments that each spread the next one twice (the rule measures each fragment once, so the work grows with the size of the query text, not with the number of paths through it, and the 30-level chain is rejected in about a millisecond). Add a cost budget: give each field a point cost and multiply list fields by their page size. As an illustration, if a list field costs its page size times (1 plus the cost of what is inside it), the dashboard query, 10 posts with 3 comments each, costs 10 x (1 + 3) = 40 points and passes a budget of 100, while asking for 50 comments per post costs 10 x (1 + 50) = 510 and is rejected. Cap page sizes as well.
• Use persisted queries: the approved query texts are registered on the server ahead of time, the client sends only a short id such as {"id":"dash_v3"}, and the server refuses text it has not registered, so strangers cannot send arbitrary expensive ones.
• Put a timeout and a concurrency cap (a limit on how many requests may be in flight to one service at once, for example 20, with extras queued or refused) on each downstream service, and let a failing widget degrade alone.

Composite REST:

• Run independent calls in parallel (Promise.all) and batch by id as the script does.
• Accept a widgets= list from a fixed allowlist, so one endpoint serves several dashboards without turning into a free-form query language.
• Cache each downstream result with a short time-to-live and set per-service timeouts; return per-widget results so a slow service does not blank the page.

What would flip the choice

• Fixed widget set, stable shapes, high read volume, public-ish data: composite REST, cached.
• Many teams adding widgets weekly, nesting varies, mobile and web both consume: GraphQL.
• Strict per-user authorization on many fields and no one to own resolver-level checks: composite REST until that ownership exists.

Direct answer
Converting postmortem findings into durable organizational knowledge means making them genuinely discoverable when someone needs them later, not just archived, and actively driving adoption of the recommended changes rather than assuming a written document alone will change anyone's behavior.

Structured elaboration

• Make it searchable, not just stored. Consistent tagging (by system, by failure category, by team) and a real search interface matter more than where the document technically lives; a postmortem nobody can find when facing a similar problem six months later has produced no lasting value regardless of how good the analysis was.
• Link forward, not just file away. Connect the postmortem to the runbooks, code, or design docs it should influence, so someone reading the runbook for a related system encounters the relevant lesson in context, rather than only finding it if they happen to search the postmortem archive specifically.
• Distribute, don't just publish. A regular digest of recent postmortems' key lessons (even a short one, shared org-wide or per relevant team) reaches people who wouldn't have gone looking, and repeated exposure is often what actually changes behavior, not a single document existing somewhere.
• Drive adoption of the recommended change actively, not passively. If a postmortem recommends a new practice (mandatory pre-deploy data tests, for example), treat rolling that recommendation out as its own project: identify a pilot team, demonstrate impact with real before-and-after data, and use that evidence to build the case for broader adoption, rather than assuming the recommendation alone will spread on its own merit.
• Periodically revisit and retire stale entries. Old postmortems referencing systems that no longer exist or practices that have since changed clutter the knowledge base and erode trust in search results; a light periodic review keeps the archive useful rather than just growing.

Worked example
A postmortem recommends mandatory pre-deploy data-validation tests after a bad data pipeline change silently corrupted downstream reports. Six months earlier, a similar (if less severe) incident had happened and been documented, but the postmortem sat unread and the recommendation was never adopted broadly. This time, instead of just filing the new postmortem, the team: tags it clearly under 'data pipeline' and 'validation gap,' links it directly from the data-pipeline team's onboarding docs and runbook, and pilots the recommended pre-deploy test requirement with one willing team first. After demonstrating the pilot caught two would-be incidents before they shipped, real evidence rather than a hypothetical, the team presents that data to engineering leadership and uses it to justify making the practice mandatory org-wide, with the earlier postmortem now cited as the founding case study in the org-wide rollout communication.

Trade-offs and pitfalls
The most common mistake is treating 'we wrote it down' as equivalent to 'we learned from it,' when in practice a document with no distribution, linking, or active adoption effort is functionally invisible to everyone except the person who wrote it. A second is over-investing in an elaborate knowledge-management system before addressing the more basic problem, which is usually that nobody is actively driving adoption of any given recommendation.

Framing

Heap usage climbing over weeks with occasional OOMs (Out Of Memory events, where the process is killed or fails because it exceeded available memory) is the classic slow-leak signature. The plan is: confirm the shape, capture evidence, trace what's retaining memory, then stop the bleeding while fixing the real cause.

1. Confirm the shape before diving in

Pull GC (garbage collection) logs/metrics over the multi-week window. Linear upward drift in heap-used-after-a-full-collection is a leak signature; a stable-but-high plateau close to the max heap is more likely a sizing problem than a leak.

2. Capture evidence: two heap dumps, not one

A heap dump is a full snapshot of every live object on the JVM (Java Virtual Machine) heap at one instant. Trigger one with jmap -dump:live,format=b,file=heap1.hprof <pid>, then repeat hours or days later under comparable load to get heap2.hprof. One dump alone cannot show growth; comparing two is what reveals which classes and object counts are actually increasing.

3. Trace retained object paths

Load both dumps into a heap analyzer (e.g. Eclipse MAT) and sort by RETAINED size (total memory that would be freed if that object were collected, including everything it exclusively keeps alive), not shallow size (the object's own size alone). For the top retainers that grew between the two dumps, follow "path to GC roots" to see exactly what reference chain is keeping them alive, common culprits are a static collection that's never trimmed, a ThreadLocal never cleared, or listeners registered but never removed.

4. Confirm with allocation profiling and thread state

Run async-profiler (a low-overhead sampling profiler for the JVM) in allocation mode (-e alloc) to get a flame graph of WHERE in the code the suspicious class is actually being allocated, complementing the dump's "what's retained" view with "where it comes from." Take jstack thread dumps around a slow-down or near-OOM moment to rule out request-scoped objects being pinned alive by a pile of blocked threads rather than a true static leak.

Short-term mitigations

• Increase heap size, or add capacity, as a stopgap that buys investigation time; it does not fix the root cause.
• Add a health-check-based rolling restart tied to a memory threshold (not a fixed schedule) so the process recycles before it OOMs.
• If growth correlates with a specific request type or feature flag (a toggle that turns a code path on or off without a deploy), consider a temporary circuit breaker (a safeguard that stops calling an overloaded dependency for a cooldown period instead of retrying forever) on that path.

Long-term prevention

• Bound every cache with a max size and a TTL (Time To Live, an expiration window), rather than a raw unbounded map.
• Add a leak-detection canary test that runs a fixed number of iterations and asserts heap returns to baseline.
• Alert on heap TREND (a sustained upward slope over days), not just on OOM itself, so this class of problem is caught in days instead of weeks.