DoorDash Full-Stack Developer Interview Preparation Guide (Junior Level)

I would start by diagnosing the problem before trying to fix it. I would interview both teams, review the timeline, and map every requirement change, handoff, and missed dependency. I would look for evidence of changing scope, unclear ownership, or missing acceptance criteria rather than assuming the issue is attitude.

Then I would reset the operating model. First, create a single source of truth for requirements and decisions. Second, define ownership for each deliverable and each handoff. Third, add a lightweight change-control step so new requirements are reviewed, sized, and approved before they disrupt the plan. I would also establish a regular checkpoint where both teams see the same risks and blockers.

If I found that the real problem was unclear handoffs, I would introduce a standard handoff template with the deliverable, due date, acceptance criteria, and owner. For example, if design changes a flow, engineering should see exactly what changed and what stayed stable. That shifts the teams from blame to shared execution and usually stabilizes delivery quickly.

For example, say the two teams are the Checkout team and the Fulfillment team, and the requirement that kept shifting was how a partial refund should be represented in the order-status payload. A filled-in handoff entry might read: deliverable: order-status payload v2 for partial refunds; due date: the 14th; acceptance criteria: refund_amount and refund_reason fields present and validated against three sample orders; owner: the Checkout API lead. With that entry in place, Fulfillment could build against a fixed contract instead of a moving target, and in the next release cycle the number of last-minute payload changes dropped to zero, because any change now had to go through the same template before it reached Fulfillment.

The idea in plain words

Two binary trees are identical when they have the same shape and the same value at every position. Both questions can be answered by walking the two trees in lock step (moving down both at the same time, so the two nodes you look at always sit at the same position) and comparing the pair of nodes found at each step. A pair is in one of three situations:

1. Both empty: this spot matches, nothing more to check.
2. Exactly one empty: the shapes differ, so the answer is no.
3. Both present: the values must be equal, and then the two subtrees must match as well.

For "identical" the left child is compared with the left child and the right with the right. For a mirror image (the second tree is the first one flipped left to right), the pairing crosses over: the left child of one tree must match the right child of the other, and the right child must match the left. That is the only change. The comparison is also what makes a single tree symmetric: compare the root's left subtree with its right subtree as a mirror pair.

The brute-force alternative is to write both trees to a list (with a marker for each missing child, otherwise different shapes could produce the same list) and compare the lists. It is correct but always builds two O(n) lists, and always reads both trees completely, which the direct comparison does not.

Height convention: height counts edges, so an empty tree has height -1 and a single node has height 0.

Code

The example trees are tree_a, its copy, its mirror image and a tree with different values:

  tree_a            mirrored_a          other_values
    1                  1                   9
   / \                / \                 / \
  2   3              3   2               8   7
 /     \            /     \             /     \
4       5          5       4           6       5

import random


class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def is_same(p, q, values=True, on_pair=None):
    """Identical trees: same shape and (if values=True) same value at every position."""
    if on_pair:
        on_pair(p, q)
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if values and p.val != q.val:
        return False
    return (is_same(p.left, q.left, values, on_pair)
            and is_same(p.right, q.right, values, on_pair))


def is_mirror(p, q, values=True, on_pair=None):
    """q is p flipped left-to-right: p's left side must match q's right side, and vice versa."""
    if on_pair:
        on_pair(p, q)
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if values and p.val != q.val:
        return False
    return (is_mirror(p.left, q.right, values, on_pair)
            and is_mirror(p.right, q.left, values, on_pair))


def is_symmetric(root):
    """A single tree that is its own mirror image."""
    return root is None or is_mirror(root.left, root.right)


def match_iterative(p, q, mirror=False):
    """is_same (mirror=False) or is_mirror (mirror=True) with a stack of node pairs."""
    stack = [(p, q)]
    while stack:
        a, b = stack.pop()
        if a is None and b is None:
            continue
        if a is None or b is None or a.val != b.val:
            return False
        if mirror:
            stack.extend([(a.left, b.right), (a.right, b.left)])
        else:
            stack.extend([(a.left, b.left), (a.right, b.right)])
    return True


def label(node):
    return "None" if node is None else str(node.val)


#     tree_a            mirrored_a          other_values
#       1                  1                   9
#      / \                / \                 / \
#     2   3              3   2               8   7
#    /     \            /     \             /     \
#   4       5          5       4           6       5
tree_a = Node(1, Node(2, Node(4)), Node(3, None, Node(5)))
copy_of_a = Node(1, Node(2, Node(4)), Node(3, None, Node(5)))
mirrored_a = Node(1, Node(3, Node(5)), Node(2, None, Node(4)))
other_values = Node(9, Node(8, Node(6)), Node(7, None, Node(5)))
symmetric = Node(1, Node(2, Node(3), Node(4)), Node(2, Node(4), Node(3)))

print("is_same(a, copy of a)              :", is_same(tree_a, copy_of_a))
print("is_same(a, mirrored a)             :", is_same(tree_a, mirrored_a))
print("is_mirror(a, mirrored a)           :", is_mirror(tree_a, mirrored_a))
print("is_mirror(a, a)                    :", is_mirror(tree_a, tree_a))
print("is_symmetric(a), is_symmetric(sym) :", is_symmetric(tree_a), is_symmetric(symmetric))
print("same shape, ignoring values        :", is_same(tree_a, other_values, values=False),
      "(with values:", is_same(tree_a, other_values), ")")
print()

pairs = []
is_mirror(tree_a, mirrored_a, on_pair=lambda p, q: pairs.append(f"({label(p)}, {label(q)})"))
print("pairs compared by is_mirror(a, mirrored a):")
print("  " + " ".join(pairs))
print(f"  {len(pairs)} calls for a tree with 5 nodes (2 * 5 + 1)")

calls = []
different_root = Node(2, tree_a.left, tree_a.right)
is_same(tree_a, different_root, on_pair=lambda p, q: calls.append(1))
print(f"roots differ: {len(calls)} call, nothing below the roots is examined")

# 100000-node chains: recursive code fails, the stack version does not.
long_a = long_b = None
for v in range(100000):
    long_a, long_b = Node(v, left=long_a), Node(v, left=long_b)
print("iterative on two 100000-node chains:", match_iterative(long_a, long_b))
try:
    is_same(long_a, long_b)
except RecursionError:
    print("recursive on the same chains: RecursionError")


# Check against tuple comparison on random pairs, and count calls <= 2 * min(n, m) + 1.
def random_tree(rng, size):
    if size == 0:
        return None
    left_size = rng.randint(0, size - 1)
    return Node(rng.randrange(3), random_tree(rng, left_size),
                random_tree(rng, size - 1 - left_size))


def as_tuple(node, flip=False, values=True):
    if node is None:
        return None
    a, b = (node.right, node.left) if flip else (node.left, node.right)
    return (node.val if values else 0, as_tuple(a, flip, values), as_tuple(b, flip, values))


def copy(node, flip=False):
    if node is None:
        return None
    a, b = (node.right, node.left) if flip else (node.left, node.right)
    return Node(node.val, copy(a, flip), copy(b, flip))


def count(node):
    return 0 if node is None else 1 + count(node.left) + count(node.right)


rng = random.Random(0)
verdicts = set()
for _ in range(2000):
    a = random_tree(rng, rng.randint(0, 8))
    kind = rng.choice(["copy", "mirror", "other"])
    b = copy(a, flip=(kind == "mirror")) if kind != "other" else random_tree(rng, rng.randint(0, 8))
    same = as_tuple(a) == as_tuple(b)
    mirror = as_tuple(a) == as_tuple(b, flip=True)
    verdicts.update([("same", same), ("mirror", mirror)])
    assert is_same(a, b) == match_iterative(a, b) == same
    assert is_mirror(a, b) == match_iterative(a, b, mirror=True) == mirror
    assert is_same(a, b, values=False) == (as_tuple(a, values=False) == as_tuple(b, values=False))
    assert is_mirror(a, b, values=False) == (as_tuple(a, values=False) == as_tuple(b, flip=True, values=False))
    seen = []
    is_same(a, b, on_pair=lambda p, q: seen.append(1))
    assert len(seen) <= 2 * min(count(a), count(b)) + 1
print("2000 random pairs: all versions agree with tuple comparison; calls <= 2 * min(n, m) + 1;",
      "both True and False seen:", all(v in verdicts for v in [("same", True), ("same", False),
                                                              ("mirror", True), ("mirror", False)]))

Run in a python:3.12 container, it prints:

is_same(a, copy of a)              : True
is_same(a, mirrored a)             : False
is_mirror(a, mirrored a)           : True
is_mirror(a, a)                    : False
is_symmetric(a), is_symmetric(sym) : False True
same shape, ignoring values        : True (with values: False )

pairs compared by is_mirror(a, mirrored a):
  (1, 1) (2, 2) (4, 4) (None, None) (None, None) (None, None) (3, 3) (None, None) (5, 5) (None, None) (None, None)
  11 calls for a tree with 5 nodes (2 * 5 + 1)
roots differ: 1 call, nothing below the roots is examined
iterative on two 100000-node chains: True
recursive on the same chains: RecursionError
2000 random pairs: all versions agree with tuple comparison; calls <= 2 * min(n, m) + 1; both True and False seen: True

Walkthrough of the mirror comparison

The listed pairs are the calls made by is_mirror(tree_a, mirrored_a), in order. The root pair (1, 1) matches. The next pair is not tree_a's left child against the other tree's left child: it is tree_a's left child (2) against the other tree's right child (2), then 4 against 4 one level down, then three empty-against-empty pairs. The root's second pair is tree_a's right child (3) against the other's left child (3), then (None, None) and (5, 5), then two more empty pairs. All 11 calls succeed, so the answer is true.

The same trees fail the plain identity test: is_same(a, mirrored a) is false, since the first mismatch is 2 against 3. A tree that is not symmetric (tree_a) is not its own mirror (is_mirror(a, a) is false), while the symmetric tree passes.

Structure only, ignoring values

Passing values=False skips the value comparison, so only the shape is compared. In the run, tree_a and other_values have the same shape (true) but different values (false). The same flag works for the mirror version.

Complexity

• Time O(min(n, m)) for trees with n and m nodes: the walk stops at the first difference and never goes beyond the smaller tree. When the trees are equal, the recursion makes 2n + 1 calls: n calls for pairs of real nodes and n + 1 for pairs of empty spots. That is 11 for the five-node example, and in the random check the call count never exceeded 2 times the smaller size plus 1.
• Space O(min(h1, h2)) for the recursion, where h1 and h2 are the heights (the recursion also stops at the shorter tree). For balanced trees that is about log2(n); for a skewed tree (one where every node has at most one child, so it is a chain) it equals the number of nodes.
• The recursion limit: CPython allows 1000 nested calls by default, so two chains of more than about a thousand nodes raise RecursionError, as the 100000-node run shows. match_iterative keeps a stack of node pairs instead and handles the same chains; passing mirror=True crosses the pairing exactly as is_mirror does.

Edge cases and common mistakes

• Two empty trees are identical and also mirror images. One empty and one non-empty tree are neither.
• Checking only that both nodes exist and then comparing values is not enough: check each child's emptiness before reading its val, which the two None checks do.
• Writing the mirror comparison with the pairing uncrossed (left with left) tests identity again. Cross both pairings.
• A symmetric-tree check must compare the root's left subtree with its right subtree as a mirror pair, which is what is_symmetric does.
• Comparing only value lists can declare different trees equal. The tree 2 with a left child 1, and the tree 1 with a right child 2, both read 1, 2 in inorder (visit the left subtree, then the node, then the right subtree) yet differ in shape and root. Shape must be part of the comparison.

Running the code

Save the listing as compare_trees.py and run it with Python 3.12. It uses only the standard library, so there is nothing to install.

python3 compare_trees.py

Situation
At my previous job a high-traffic checkout flow started failing for ~8% of users during peak hours — frontend showed a “Payment failed” modal while backend logs had intermittent 502s from the payment microservice.

Task
As the primary full‑stack on call, I needed to isolate whether this was a frontend bug, API regression, or infra issue, coordinate fixes across teams, and restore full service with minimal customer impact.

Action

• Triage: I put up a temporary banner and routed new checkouts to a degraded-but-working payment endpoint (feature-flagged) to reduce user impact.
• Isolate: Captured client-side telemetry (Sentry) and correlated timestamps with backend traces (OpenTelemetry). Frontend showed correct payloads; backend traces revealed spikes in request latency and a growing connection pool exhaustion in the payment service’s HTTP client.
• Coordinate: Notified backend and infra engineers via a dedicated Slack channel and shared traces and heap/connection metrics. I reproduced the issue in staging by simulating concurrent checkouts.
• Fix: On backend, we identified an unclosed HTTP response body in a recent release that prevented connections returning to the pool. I authored a hotfix to properly close responses, added connection timeout configs, and wrote an integration test. I deployed the hotfix behind a canary, monitored metrics, then rolled to 100%.
• Frontend follow-up: I added retry logic with exponential backoff for idempotent errors and improved user messaging to avoid alarming users during transient failures.

Result
Within 45 minutes we reduced failed checkouts from 8% to <0.5%. Post-incident, we added automated synthetic load tests, updated runbooks, and added the integration test to CI. I documented the root cause and coordinated a postmortem that prevented recurrence.

Direct answer

For a read-heavy workload with moderate writes, for example a 90% read / 10% write split, the default lean should be read replicas, because they scale read capacity without adding a second consistency model to reason about. Add a cache on top only for a narrow, measured set of hot keys that replicas still cannot serve cheaply or quickly enough. The decision comes down to three questions: can the application tolerate replication lag or cache staleness, is the read traffic skewed enough that a small cache absorbs most of it, and is there enough engineering capacity to build correct cache invalidation.

Structured elaboration

Decision rule: if managed read replicas are available with a replication lag the application tolerates, start there. Add a cache only where a specific, measured hot-key or hot-query pattern needs sub-database latency or needs to shed load the replicas can't absorb cheaply.

The absorbed framing of a 90% read / 10% write split is the same decision restated: the write share matters because every write still has to land on the primary and propagate down to every replica. At 10% writes this is a non-issue; if the write share climbed toward 40-50%, the datastore choice itself would need revisiting (see write-heavy architecture reasoning), not just the cache-versus-replica question.

Worked example

Assume a baseline read load of 10,000 requests per second (RPS) and, illustratively, that each database read replica sustainably serves 2,000 RPS at acceptable latency.

Without a cache: replicas needed $= 10{,}000 / 2{,}000 = 5$ replica nodes (plus the primary handling writes).

With a cache in front, assume an 80/20 access skew (a common real-world pattern: 20% of keys account for 80% of reads) and a 90% cache hit rate on that hot 20%:

$\text{DB-bound reads} = (0.8 \times 10{,}000 \times (1-0.9)) + (0.2 \times 10{,}000) = (8{,}000 \times 0.1) + 2{,}000 = 800 + 2{,}000 = 2{,}800 \text{ RPS}$

Replicas needed with the cache in place: $\lceil 2{,}800 / 2{,}000 \rceil = 2$ replicas.

That's a drop from 5 replica nodes to 2 from caching just the hot 20% of keys, which is why a targeted cache is usually layered on top of replicas rather than chosen instead of them: it earns its operational cost only where the skew is large enough to matter.

Trade-offs & pitfalls

• Adding a cache first because it "feels faster," without first measuring read skew, risks solving an already-adequate problem while introducing invalidation bugs for no real gain.
• Replicas trade consistency for scale: if a user reads immediately after writing in the same session, that read must be routed to the primary or to a lag-aware router, or the user will see stale data from their own write.
• Cache stampede on a mass invalidation event can hit the primary at exactly the worst moment, right after the thing that made the cache go stale in the first place; request coalescing and staggered TTLs guard against this.
• A self-run cache cluster is a second system to operate, patch, and monitor; a managed database's built-in replicas usually cost less operational attention than they save, which is why replicas are the default and the cache is the exception.

Direct answer. Separate the disagreement about the FIX from the disagreement about the RELATIONSHIP: state the specific, observable risk you're flagging, ask questions before asserting you're right, and be explicit about what would change your mind -- the goal is a better outcome for the code, not winning the exchange.

Structuring the conversation

1. Lead with the specific concern, not a verdict: 'I'm worried this fix only handles the null case but not the empty-string case -- can you walk me through why that's covered?' invites a conversation; 'this fix is wrong' invites defensiveness.
2. Separate technical disagreement from personal friction: if the other engineer becomes defensive, explicitly name that you're both trying to ship something correct, not litigating who's right: 'I want to make sure we don't ship a regression, not relitigate the whole approach.'
3. Ask for their reasoning before pushing your own further: they may have context you don't (a constraint from an earlier decision, a reason the simpler fix was deliberately avoided) -- understanding that first often resolves the disagreement faster than restating your position louder.
4. Propose a concrete, falsifiable test: 'Can we add a test for the empty-string case? If it passes, I'm satisfied; if it fails, that confirms the gap I'm flagging.' This moves the conversation from opinion to evidence both people can agree on.
5. Know when to escalate, and how: if the disagreement is genuinely unresolved after a good-faith exchange, loop in a third reviewer or a tech lead as a NEUTRAL tie-breaker, framed as 'let's get another perspective,' not 'let's prove I was right.'

The outcome

In the case I'm describing, the falsifiable test resolved it directly: we added the test for the empty-string case, watched it fail against the original fix, and the colleague agreed within minutes that the gap was real -- at that point we were looking at the same failing assertion together, not debating opinions. The fix was updated to cover both cases before merge, so nothing shipped broken, and the review thread stayed short and non-adversarial because the test carried the argument instead of either of us needing to insist we were right. A secondary, longer-term outcome was that the same colleague started adding an empty-string case to their own tests going forward without being asked, which suggested the exchange changed a habit, not just that one PR. No escalation to a third reviewer was needed in this instance; the disagreement stayed contained to the two of us and closed out the same day.

What I'd do differently in hindsight (if reflecting on a past instance)

Often the friction comes from feedback that read as a verdict rather than a question -- 'this is wrong' instead of 'walk me through this case.' The adjustment that tends to help most is leading with curiosity and a concrete, testable case rather than a general critique, since a concrete case is something both people can verify together instead of debate.

Trade-offs and pitfalls

• Over-indexing on 'always ask, never assert' can read as passive or indecisive when you ARE confident and the stakes are high (a security or correctness issue) -- calibrate directness to how confident you are and how much is at stake, not a uniform script.
• Escalating too quickly, before attempting a good-faith direct conversation, can read as going over someone's head and damage trust even if you were technically right -- reserve escalation for genuine deadlock, not the first sign of disagreement.

Direct answer

Quicksort is in-place with average time $O(n \log n)$ but a worst case of $O(n^2)$ on an unlucky pivot sequence; merge sort and heap sort both guarantee $O(n \log n)$ in every case. Merge sort needs $O(n)$ extra space and is stable; heap sort needs only $O(1)$ extra space but is not stable; quicksort's extra space is $O(\log n)$ for the recursion stack on average, but can grow to $O(n)$ in the worst case. For nearly-sorted data, pick an adaptive sort such as TimSort (the hybrid merge/insertion sort behind Python's and Java's built-in sort); when a guaranteed worst case matters more than average speed, pick heap sort or merge sort, never plain quicksort.

Structured elaboration

Nearly-sorted input

Plain quicksort and plain top-down merge sort are not adaptive: both do the same $O(n \log n)$ work regardless of how ordered the input already is. TimSort is: it scans for existing ascending or descending runs, extends and merges them, and degrades toward close to linear work as the input approaches already-sorted. For nearly-sorted data, reach for TimSort (or, if you must hand-roll something, a natural merge sort) rather than a textbook quicksort or merge sort.

Worst-case guarantees matter more than average speed

Both heap sort and merge sort guarantee $O(n \log n)$ in every case; quicksort does not, no matter how the pivot is chosen, because an adversary (or, unintentionally, already-sorted or already-reverse-sorted input under a naive pivot rule) can always construct a sequence that degrades a fixed pivot strategy to $O(n^2)$. Choose heap sort when the extra $O(n)$ memory merge sort needs is unavailable and stability is not required; choose merge sort when stability is required alongside the worst-case guarantee and the memory budget allows it.

Two side notes worth naming explicitly

• Parallelization on resource-constrained devices: merge sort's divide phase maps cleanly onto independent worker threads or cores (each half sorts independently before a merge step), which is attractive on a multi-core mobile device; the cost is the extra O(n) buffer merge sort needs, which is a real constraint on memory-limited hardware. Quicksort's partitions can also be sorted concurrently, but partition sizes are unpredictable (a skewed pivot gives one thread almost all the work), so load balancing is harder to reason about.
• Cross-language floating-point sort determinism: when the same data is sorted by comparator across different languages or platforms, an unstable sort's tie-breaking for equal keys is unspecified and can differ, and NaN comparisons under IEEE 754 floating point are neither less-than nor greater-than any value, which breaks the total-order assumption most sort implementations rely on. If reproducible ordering across systems matters (for example, deterministic test fixtures or replaying a pipeline), use a stable sort and either exclude or explicitly place NaNs, rather than relying on the default comparator.

Worked example

A concrete way to see the worst case: implement a plain quicksort that always pivots on the last element, and run it on an already-sorted array.

def quicksort_last_pivot_count(a: list[int]) -> int:
    """
    Naive quicksort that always pivots on the last element.
    Returns the number of comparisons performed (element-to-pivot checks).
    """
    comparisons = 0

    def sort(lo: int, hi: int) -> None:
        nonlocal comparisons
        if lo >= hi:
            return
        pivot = a[hi]
        store = lo
        for i in range(lo, hi):
            comparisons += 1
            if a[i] < pivot:
                a[i], a[store] = a[store], a[i]
                store += 1
        a[store], a[hi] = a[hi], a[store]
        sort(lo, store - 1)
        sort(store + 1, hi)

    sort(0, len(a) - 1)
    return comparisons


if __name__ == "__main__":
    for n in [6, 10, 20]:
        already_sorted = list(range(n))
        c = quicksort_last_pivot_count(already_sorted)
        expected = n * (n - 1) // 2
        print(f"n={n}: comparisons={c}, n(n-1)/2={expected}")

Running this prints:

n=6: comparisons=15, n(n-1)/2=15
n=10: comparisons=45, n(n-1)/2=45
n=20: comparisons=190, n(n-1)/2=190

Every partition step on already-sorted input with a last-element pivot puts everything on one side, so the recursion depth is n and the total comparisons are exactly $n(n-1)/2 = \Theta(n^2)$, confirmed by the counts matching the closed-form prediction at every size tested. A randomized or median-of-three pivot choice avoids this specific failure mode but does not eliminate the worst case in general, only make it exponentially unlikely to hit by chance.

Trade-offs & pitfalls

The most common wrong turn is treating quicksort as unconditionally the fastest choice: on already-sorted or reverse-sorted input under a naive pivot rule, it is the slowest of the three by an order of magnitude, as the worked example shows directly. A second common gap is forgetting that merge sort's memory cost is real: at large enough n, the O(n) auxiliary buffer competes with other memory pressure, which is exactly why external (disk-based) sorting is built on multi-way merge rather than quicksort, since merge sort's sequential access pattern suits disk or network I/O far better than quicksort's more random access pattern. A third trap is ignoring stability when it silently matters: if you sort by a secondary key after already sorting by a primary key, only a stable sort preserves the primary ordering among equal secondary keys; using an unstable sort there produces a result that looks correct on small examples but is wrong in general.

Direct answer

Handling a producer spike safely means combining five things: size the queue and its partitions to absorb a bounded amount of lag, autoscale consumers off a lag metric rather than a fixed count, rate-limit or throttle producers once the queue's high-watermark is crossed, retry transient failures with a bounded backoff before routing to a dead-letter queue (DLQ, a holding area for messages that repeatedly fail processing), and propagate the backpressure signal back to producers so they slow down instead of continuing to push into an already-saturated pipeline.

Structured elaboration

flowchart LR
  P[Producer] -->|publish| RL[Ingress rate limiter]
  RL -->|accepted| Q[Partitioned queue / broker]
  Q --> CG[Consumer group]
  CG -->|success| DS[Downstream service]
  CG -->|retries exhausted| DLQ[Dead-letter queue]
  Q -->|lag metric| AS[Autoscaler]
  AS -->|scale consumers| CG
  Q -->|429 / Retry-After past watermark| RL
  RL -->|backpressure signal| P

1. Partitioning and queue sizing. Partition by a key that spreads load evenly (and watch for a hot key overwhelming a single partition). Size the buffer so it can absorb the maximum lag you're willing to tolerate before you consider the system degraded:

$\text{buffer size} \approx \text{peak message rate} \times \text{max tolerable lag (s)} \times \text{avg message size}$

2. Consumer autoscaling. Scale consumer count off consumer-group lag (how far behind the latest message the consumer group is), not CPU alone, since a slow downstream dependency can starve consumers of CPU while lag still grows. Use a sticky partition-assignment strategy to avoid unnecessary rebalancing churn when scaling.

3. Producer rate limiting and backpressure propagation. A token-bucket limiter at the ingress accepts bursts up to a defined rate. When the broker's queue depth or lag crosses a high-watermark, ingress starts returning a rejection (HTTP 429 with a Retry-After header, or the internal-service equivalent) so well-behaved producer clients back off with exponential backoff and jitter rather than continuing to push.

4. Retry and DLQ design. Consumers retry transient failures a bounded number of times with exponential backoff, tracking attempt count in message metadata. After the retry budget is exhausted, the message moves to a DLQ with enough context (original offset, error, timestamp) to investigate and replay later. Retries that would otherwise repeatedly hammer a struggling downstream dependency should integrate with a circuit breaker (a separate high-availability pattern that stops sending traffic to an unhealthy dependency; not re-derived here, just named as the mechanism this design composes with) so a consumer stops attempting work it already knows will fail, and rejects at a rate proportional to the downstream's observed health rather than retrying blindly.

5. Ordering, priority, and duplicates. If different message classes have different urgency, separate priority queues (or topics) let urgent work skip the line, but this breaks strict cross-class ordering; combined with at-least-once delivery, reordering across priority tiers increases the chance of duplicate or out-of-order processing at the consumer. If ordering matters within a given key, route that key to a single partition; consumers must be idempotent (safe to process the same message twice) regardless, since at-least-once delivery is the realistic guarantee here.

6. Monitoring and alerting. Track consumer lag per partition, queue size in bytes, incoming and outgoing throughput, DLQ growth rate, and producer-rejection rate. A per-partition lag heatmap surfaces hot partitions that an aggregate lag number would hide.

Worked example

Queue sizing. Given a peak message rate of 5,000 messages/second, a maximum tolerable consumer lag of 300 seconds, and an average message size of 2 KB:

$5{,}000 \times 300 \times 2\text{KB} = 3{,}000{,}000 \text{KB} = 3{,}000 \text{MB} = 3 \text{GB}$

Adding 1.5x headroom for burst variance beyond the stated peak:

$3 \text{GB} \times 1.5 = 4.5 \text{GB}$

Message-pattern choice for a real-time notification system. A concrete system illustrates why the messaging pattern matters, not just the queue sizing:

Autoscale cost-blowup case. A team scaling consumers directly off instantaneous lag saw a scale-out storm: every consumer group scaled up in lockstep at the exact same lag threshold, adding far more capacity than the actual backlog needed and driving cost up without proportionally reducing lag, because the scale signal itself spiked in a coordinated, self-reinforcing way. The fix was two-fold: batch messages per consumer poll so each consumer does more useful work per unit of scaling, and smooth the autoscale trigger by scaling off a windowed average of lag rather than its instantaneous value, so a brief coordinated spike doesn't trigger a coordinated scale-out.

Trade-offs & pitfalls

Anti-patterns to avoid, all variants of "the queue or the pattern doesn't actually distribute the load":

• A single global queue serving millions of messages with no partitioning, which caps throughput at whatever one consumer thread can pull.
• Long-running, lock-holding database transactions inside a message handler, which serialize otherwise-parallel consumers against each other.
• Cron jobs scheduled to run at the same wall-clock time on every node, creating a synchronized load spike instead of smoothed background work.
• Synchronous cross-service call chains inside the consumer path, which mean one slow downstream service directly throttles the whole pipeline's throughput.

Choosing among load-shedding strategies. These are not interchangeable; they trade off differently:

• Aggressive autoscaling reduces lag but increases cost and rebalance frequency; warm standby consumers and a sticky assignor reduce the churn cost of scaling.
• DLQ messages are not "handled," they're deferred. A growing, unmonitored DLQ is a silent failure; alert on DLQ growth rate, not just its existence.

Direct answer

This is Python's classic mutable-default-argument bug. def append_to_list(item, lst=[]): looks like a fresh empty list is created every call, but Python evaluates a default argument's value exactly once, when the def statement itself runs, not on every call. Since [] is mutable, every caller who doesn't pass their own lst shares that same one list object across every call to the function, for the lifetime of the program. The fix: default to None, an immutable sentinel, and create a new list inside the function body when the caller didn't provide one.

Structured elaboration

Approach. Python binds a function's default argument values once, at definition time, to the function object itself, not per call. For an immutable default like 0 or None this is invisible, since you can't mutate an int or None in place, so nobody notices the "only once" behavior. For a mutable default like [], {}, or a custom mutable object, it means every call that relies on the default is silently operating on the same shared object, so state written by one caller leaks into every subsequent caller.

Review comment. "Bug: lst=[] is a mutable default argument. Python evaluates it once, at function-definition time, so every call that doesn't pass its own lst shares and mutates the same list, and state leaks between unrelated calls. Please default to None and create a new list inside the function body, and add a regression test asserting two calls with the default argument don't share state."

Worked example

The buggy behavior, demonstrated by actually calling the function twice with no lst argument:

def append_to_list_buggy(item, lst=[]):
    lst.append(item)
    return lst

print(append_to_list_buggy(1))
print(append_to_list_buggy(2))

Output:

[1]
[1, 2]

The second call's result contains 1 from the first call, that's the state leak the review comment flags: the caller of append_to_list_buggy(2) almost certainly expected [2], not [1, 2].

The corrected implementation and a unit test that would have caught the bug:

def append_to_list(item, lst=None):
    if lst is None:
        lst = []
    lst.append(item)
    return lst

def test_append_to_list_does_not_share_state():
    a = append_to_list(1)
    b = append_to_list(2)
    assert a == [1]
    assert b == [2]

test_append_to_list_does_not_share_state()
print("test_append_to_list_does_not_share_state: PASS")

Output:

test_append_to_list_does_not_share_state: PASS

Complexity

Appending one item is O(1) amortized (meaning an occasional slower operation averages out across many calls) time and O(1) additional space per call, aside from the list's own growth. The fix doesn't change that complexity, it changes which list object gets mutated: a fresh one per call instead of one shared object.

Edge cases

• A caller who explicitly passes their own list should still get in-place appending onto that list, that behavior is preserved by both versions.
• A caller who passes something that isn't a list (a tuple, None explicitly) needs a decision: raise a clear error, or duck-type accept anything with an .append method, either is defensible, but it should be intentional and documented, not accidental.
• The bug bites hardest in a loop calling the SAME function repeatedly with no lst argument across many call sites, since the shared list keeps growing without bound, which starts as a correctness bug and becomes a memory-safety concern too.

Trade-offs and pitfalls

The same pattern applies to any mutable default, a dict, a set, or a custom mutable object, not just a list, so a reviewer who's learned to spot this once should generalize the check rather than pattern-matching on lst=[] specifically. A linter (Python's Pylint rule W0102, or Ruff's rule B006) can catch this entire class of bug automatically; it's worth suggesting the team turn that check on in continuous integration (CI) so it doesn't depend on a human catching it in review every time, though that's a process improvement to raise as a follow-up, not a reason to skip flagging this instance now.

Direct answer

A hash map counts occurrences or detects duplicates in O(n) time using O(n) auxiliary space (n = number of elements, or the number of distinct elements if that's smaller), at the cost of losing the original relative order between distinct keys unless that order is tracked separately. Sorting does the same job in O(n log n) time, using O(1) to O(n) auxiliary space depending on the sort algorithm, but naturally groups equal elements adjacently, and a stable sort additionally preserves the relative order of equal elements from the input. The right default for "count occurrences" or "detect duplicates" is the hash map, because its time complexity is strictly better; sorting earns its keep when the data must end up ordered anyway, or when memory for an auxiliary hash structure is the binding constraint.

Structured elaboration

Where the time complexity gap comes from. A hash map answers "have I seen this key, and how many times" in expected O(1) time per lookup/update, so processing n elements is O(n) total. A comparison-based sort cannot do better than O(n log n) in the worst case: this follows from the recurrence a typical divide-and-conquer sort like merge sort satisfies, T(n) = 2*T(n/2) + O(n) (split into two halves, recursively sort each, then merge in linear time), which by the Master theorem resolves to T(n) = Theta(n log n), since the work of combining subproblems (O(n) per level) matches the growth rate of the recursive branching exactly (a = 2 subproblems of size n/b = n/2, and n^(log_b(a)) = n^1, matching f(n) = O(n)). Concretely, doubling n from, say, 1,000 to 2,000 elements roughly doubles the hash-map approach's work, but more than doubles the sort's work (2,000 * log2(2,000) is proportionally larger than 1,000 * log2(1,000)), and this gap widens as n grows.

Memory overhead. A hash map's O(n) space is not just n data slots: a hash table typically keeps its load factor (fraction of slots occupied) below some threshold to keep lookups fast, meaning it holds some fraction of empty slots as overhead, plus per-entry bookkeeping (a stored hash code, pointers for collision chains, or open-addressing probe metadata) beyond the raw key and count value. An in-place comparison sort (like heapsort or an in-place quicksort variant) can use O(1) auxiliary space instead, though a stable sort like merge sort (or Python's Timsort, which is stable) typically needs O(n) auxiliary space to merge into, so "sorting uses less memory" is only true for the specific unstable, in-place sort algorithms, not sorting in general.

Stability. A stable sort preserves the relative order of elements that compare equal; this matters when equal-looking rows carry other differing fields the caller cares about (say, sorting purchase records by customer ID while wanting same-customer records to stay in their original timestamp order). A hash map used purely for counting or membership-testing has no concept of "relative order" of distinct keys at all, though a Python dict (used since Python 3.7) specifically preserves the insertion order of its keys, meaning a dict-based deduplication pass naturally reports first-occurrence order for free without needing a separate ordered structure.

Practical considerations for data scientist workflows. pandas.Series.value_counts() is hash-based internally and defaults to returning results ordered by count (its sort parameter defaults to True, sorted descending by count, i.e. ascending=False), which is a presentation-time sort layered on top of a hash-based count, not evidence that counting itself needs sorting. Similarly, DataFrame.groupby() defaults to sort=True for its output group-key ordering (verified against pandas 3.0.3), which again is an ordering choice applied after a hash-based grouping operation, and can be turned off (sort=False) when the caller only needs the aggregated result and doesn't care about output key order, trading a small amount of avoided sort work for unordered output.

Worked example

Pinned data (n = 8 elements), comparing the hash-based approach (pandas value_counts(), which uses a hash table internally) against a manual sort-then-scan approach, and an explicit order-of-growth comparison for n = 8:

import pandas as pd
import math

data = [7, 3, 7, 1, 3, 3, 9, 1]  # n = 8, pinned

s = pd.Series(data)

counts_hash = s.value_counts()  # hash-based; default sort=True (by count, descending)
print("value_counts() (hash-based):", counts_hash.to_dict())

first_seen_order = list(dict.fromkeys(data))
print("first-occurrence order via dict-based dedup:", first_seen_order)

sorted_data = sorted(data)
print("sorted array:", sorted_data)
sort_counts = {}
i = 0
while i < len(sorted_data):
    j = i
    while j < len(sorted_data) and sorted_data[j] == sorted_data[i]:
        j += 1
    sort_counts[sorted_data[i]] = j - i
    i = j
print("counts via sort-then-scan:", sort_counts)

print("both methods agree on counts:", set(counts_hash.items()) == set(sort_counts.items()))

n = len(data)
print(f"n = {n}")
print(f"hash-map approach: ~{n} O(1) operations (one dict update per element)")
print(f"comparison-sort approach: work scales with n * log2(n) = {n} * {math.log2(n):.0f} = {n * math.log2(n):.0f} (order-of-growth illustration, not a literal comparison count)")

Output (actual run, pandas 3.0.3):

value_counts() (hash-based): {3: 3, 7: 2, 1: 2, 9: 1}
first-occurrence order via dict-based dedup: [7, 3, 1, 9]
sorted array: [1, 1, 3, 3, 3, 7, 7, 9]
counts via sort-then-scan: {1: 2, 3: 3, 7: 2, 9: 1}
both methods agree on counts: True
n = 8
hash-map approach: ~8 O(1) operations (one dict update per element)
comparison-sort approach: work scales with n * log2(n) = 8 * 3 = 24 (order-of-growth illustration, not a literal comparison count)

Both approaches agree on the actual counts ({1: 2, 3: 3, 7: 2, 9: 1}, just presented in different key order), confirming they're computing the same underlying answer. value_counts() sorts by count descending, the manual sort-then-scan naturally produces sorted-key order, and the dict-based dedup preserves original first-occurrence order ([7, 3, 1, 9]), a third distinct ordering, none of which is "more correct" than another since the underlying counts are identical.

Trade-offs and pitfalls

• Defaulting to sorting out of habit, when the task is purely "count" or "detect duplicates" with no downstream need for ordered output, pays an unnecessary O(n log n) versus O(n) cost; naming the hash-map option first and explaining why it wins on pure counting is the stronger answer.
• Conversely, if the output must be presented in sorted order regardless (a leaderboard, a sorted report), sorting isn't optional overhead added on top of counting, it's part of the actual requirement, so comparing "hash map wins" against a workflow that needs sorted output anyway is comparing the wrong things; the honest framing is "hash map for the counting step, sort only if and when order is actually required downstream."
• Memory overhead from a hash table's load-factor slack and per-entry bookkeeping is real but usually small relative to sorting's own auxiliary needs for a stable algorithm; the actual crossover point depends on implementation details (language, specific hash table and sort implementation) rather than a fixed rule of thumb.
• pandas.Series.value_counts()'s default sort behavior is a common source of confusion: it does NOT mean the counting itself requires a sort. Passing sort=False avoids the extra ordering step when only the counts matter, not the presentation order.
• Relying on dict key-insertion-order preservation for "first occurrence order" is a real, documented Python behavior (since Python 3.7) worth naming, but it is language-specific; the same trick cannot be assumed in a language whose hash-map implementation makes no ordering guarantee.

What happened, in plain terms

Cache poisoning here means the cache KEY, not just the value, was built by directly concatenating raw user input, for example a profile cache key built from an unvalidated request parameter instead of a validated, structured identifier. If two different users can, through malicious or just malformed input, cause the SAME string to be used as a key, one user's cached response gets served to the other: an overwrite and a direct data leak, not a cosmetic bug.

Prevention: code-level controls

• Never build a cache key from raw, unvalidated user input. Use a fixed, structured key template where every variable slot is a value the server already trusts, an authenticated user id from the session, not a value pulled directly from a query parameter or body.
• If user input genuinely must appear in a key, for example a search query used as part of a results cache key, hash or encode it through a fixed transform rather than embedding the raw string, so crafted input can't produce a colliding or delimiter-breaking key, a raw string containing the key delimiter itself is a classic way this goes wrong.
• Centralize key construction in one shared function, not left to each call site to build key strings by hand, so this rule is enforced once and can't be silently skipped in a new code path.

Prevention: infra-level controls

• Access controls scoped to key prefix, if the cache backend supports it, restrict a given service's credential to only read or write keys matching a pattern, so a bug in one service's key construction can't accidentally read or overwrite a DIFFERENT service's namespace.
• Validate at the edge or gateway before request parameters ever reach the code that builds a cache key, so malformed or adversarial input is rejected before it can influence caching behavior at all.

Monitoring signals to detect poisoning

• Unexpected key cardinality growth: if a key template is supposed to produce a small, bounded set of distinct keys, one per user id, a known population size, and the observed count is far higher, that signals unbounded input reaching key construction somewhere.
• Cross-user data mismatch reports: a user reporting they're seeing someone else's data is a strong, if lagging, signal; this should also be catchable BEFORE customer reports, via an automated canary check verifying a known test account's cached data matches what was written for that account.
• Suspicious characters in live keys: a periodic job scanning a sample of live keys for characters that shouldn't appear in a well-formed key, raw whitespace, delimiter characters, unexpectedly long keys, as evidence unsanitized input reached key construction.

Immediate mitigation and rollback

1. Flush the affected namespace, the specific key prefix implicated, not necessarily the whole cache, to remove poisoned entries immediately; a full flush is the last resort if the blast radius can't be scoped, since it also drops legitimate data and spikes database load from the resulting miss storm.
2. Roll back the code path that introduced the vulnerable key construction to the last known-good deploy, rather than hot-patching under incident pressure.
3. Force cache bypass for the affected endpoint, temporarily reading straight from the source of truth, if the code rollback can't happen immediately.
4. Notify and remediate affected users once the scope is understood, which users' data was exposed to which others, since this is a data-exposure incident with likely disclosure obligations, not just a performance bug.

Long-term process changes

• A code review checklist item for any new cache-key construction: does it use the shared key-building function, and does every variable slot come from a trusted, server-derived value.
• A static-analysis or lint rule flagging raw user-input variables interpolated directly into a string passed to a cache set or get call, catching this class of bug before review even needs to.
• A security review gate for any new cache key SCHEME, not every individual usage, but any time a new pattern of what goes into a key is introduced, since this is exactly the kind of decision that's cheap to review once and expensive to fix after it's shipped and poisoned real data.

Trade-off

Centralizing key construction and adding a lint rule costs upfront engineering time and adds friction to introducing new cache usages, but the alternative, catching this class of bug only via a production incident and a customer data-exposure disclosure, is dramatically more expensive, which is why this is worth doing systemically rather than patching just the one call site that caused this incident.