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

Direct answer

A cross-team initiative I was part of missed its goals because of how, not what, we coordinated: unclear ownership across the teams involved, and assumptions that stayed unstated until they caused real problems. The lasting change wasn't a one-time apology or a single retro action item; it was a concrete shift in how the teams handed work to each other afterward, and I could point to whether that same failure mode recurred as the real evidence it stuck.

Structured elaboration

What broke, specifically

Swap in whatever cross-team dependency applies in your own world (a shared data pipeline, an API contract, a joint launch). In this skeleton, a project spanning several teams missed its deadline and caused repeated problems during a pilot phase because of two gaps: an unstated assumption about how a downstream team's dependency actually worked, and no clear escalation path when a blocking issue crossed a team boundary, so problems sat for days before the right people even knew about them.

How I ran the postmortem

• Built a timeline from evidence (incident counts, missed dates, rollback frequency), not memory or opinion.
• Separated the technical root causes from the collaboration root causes, since they needed different fixes.
• Named my own part in the failure to the group first, rather than only pointing at others' misses.

What actually changed afterward, and how I know

Concrete artifacts, not intentions: a documented dependency map required before a cross-team project kicks off, a clear ownership assignment per milestone naming who is accountable for what, and a pre-cutover checklist signed off by every team with something at stake, not just the owning team.

When the real obstacle is culture, not process

Sometimes the harder problem isn't a missing checklist, it's shifting a broader culture away from punitive postmortems toward ones people are actually honest in, particularly when some teams still default to blame. Modeling that shift means naming your own contribution to the failure before asking anyone else to, keeping the review focused on the system and the decision points rather than individuals, and treating a later postmortem where someone from a still-blame-oriented team volunteers a candid mistake as the real signal that the culture is moving, not just a nice-to-have.

Worked example

A multi-team initiative to consolidate several systems onto a shared platform missed its timeline and caused a string of problems during a pilot rollout. The retro traced the root cause to two things: application teams weren't told about a change in how long access credentials would remain valid under the new platform, and there was no agreed escalation path when a blocking issue spanned two teams. The concrete changes that came out of it were a mandatory dependency map and sign-off checklist before any team's cutover, and a named escalation contact per team for the duration of the rollout. A better signal of real progress on culture came from a smaller moment: at the next postmortem, a team that had previously stayed quiet about its own mistakes volunteered, unprompted, that a missed step on their side had contributed to a separate incident, which said more about the blame reflex fading than anything written in a process document.

Trade-offs and pitfalls

• A postmortem that produces only reflections ('we should communicate better') without a concrete, checkable change is the most common failure of this kind of story; the interviewer is listening for what's different in the next project, not what was learned.
• Owning your own part in the failure has to be genuine, not a rhetorical move before pivoting to blame others; if it reads as performative, it undercuts the whole story.
• A culture shift away from blame doesn't happen from one retro; it shows up gradually, in whether people volunteer uncomfortable information without being asked, and that takes sustained modeling, not a single well-run session.
• Watch for a story that only describes what changed for the team that failed, rather than what changed structurally for how all the involved teams hand off work to each other, since the initiative broke because more than one team was involved.

Direct answer

Precompute a running-total array prefix where prefix[i] is the sum of the first i counts, built once in O(n). Any inclusive range sum [left, right] is then prefix[right + 1] - prefix[left], O(1). When a new minute of events arrives, append one new prefix entry (last + new_count) in O(1) rather than recomputing anything. A "last W minutes" query is just a range-sum query where the range is derived from the current length, so it reuses the same O(1) machinery.

Approach

1. Build: prefix = [0]; for each count in order, append prefix[-1] + count. prefix has n+1 entries so that prefix[0] = 0 represents "the sum of zero elements," letting the range-sum formula work uniformly even for a range starting at index 0.
2. Range query [left, right] inclusive: prefix[right + 1] - prefix[left]. This is O(1) regardless of range width, because the two boundary lookups already encode the running total up to each endpoint.
3. Streaming update: appending a new minute's count is prefix.append(prefix[-1] + new_count), O(1) amortized (Python list append), since it only ever adds one new entry using the existing last total; nothing earlier in prefix needs to change. This is what makes the update efficiently incremental: each new event only costs one addition, never a recomputation of the whole array.
4. Windowed query ("last W minutes"): since the array is indexed one entry per minute in arrival order, the last W minutes are just the range [n - W, n - 1] (clamped to 0 if W exceeds the history length), so this reuses the same O(1) range-sum formula directly.

Complexity

Build: O(n) time, O(n) space for the prefix array. Range query: O(1). Streaming append: O(1) amortized. Windowed query: O(1), same as any other range query, because the window boundary is derivable directly from the current array length.

Edge cases

• Windowed query wider than the history so far (e.g. asking for the last 60 minutes when only 5 minutes of data exist): clamp the left boundary to 0 rather than going negative, returning the sum of everything available.
• Zero-length range (left == right + 1, i.e. querying an empty window): returns 0 correctly, since prefix[right+1] - prefix[left] collapses to prefix[left] - prefix[left].

class MinuteEventCounter:
    def __init__(self, counts):
        self.prefix = [0]
        for c in counts:
            self.prefix.append(self.prefix[-1] + c)

    def range_sum(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

    def append(self, count):
        self.prefix.append(self.prefix[-1] + count)

    def last_window_sum(self, window_minutes):
        n = len(self.prefix) - 1
        left = max(0, n - window_minutes)
        return self.range_sum(left, n - 1)


counts = [10, 0, 5, 20, 3]
counter = MinuteEventCounter(counts)

print(counter.range_sum(0, 4))
print(counter.range_sum(2, 3))

counter.append(7)
print(counter.range_sum(0, 5))

print(counter.last_window_sum(3))
print(counter.last_window_sum(60))

Output:

38
25
45
30
45

Five minutes of counts [10, 0, 5, 20, 3] sum to 38 overall, and minutes 2-3 (5 + 20) sum to 25, both matching the range-sum formula directly. After a sixth minute (7 events) streams in, the full six-minute sum is 45. The last-3-minutes window covers minutes 3, 4, 5 (20 + 3 + 7 = 30); asking for a 60-minute window when only 6 minutes of history exist correctly clamps to the whole history's sum, 45.

Trade-offs and pitfalls

• This O(1)-per-minute update relies on the array being indexed one entry per minute, in order, with no gaps (exactly the shape given in the question). If events instead arrived with irregular or sparse timestamps (not one guaranteed entry per minute) and a windowed query meant "events from timestamp T-60min to now" rather than "the last 60 array slots," you would need to look up the index corresponding to a given timestamp first, which is a binary search over a parallel timestamps array (O(log n)), not O(1); the O(1) windowed-query property here is a direct consequence of the question's stated per-minute indexing, not something that survives arbitrary timestamp irregularity for free.
• Prefix sums do not support efficient updates to a value that has already been counted (e.g. correcting minute 2's count after the fact): that would require rebuilding every later prefix entry (O(n)) with this simple array, whereas a Fenwick tree (binary indexed tree) supports both point updates and prefix queries in O(log n) each, at the cost of noticeably more implementation complexity than this straight prefix array. For a purely append-only stream (as asked here), the simple array is the right level of machinery; reach for a Fenwick tree only once in-place corrections to historical counts become a real requirement.
• Memory grows without bound on an infinite append-only stream: since every new minute keeps a running prefix entry forever, a long-lived service would eventually want to either cap the retained history (e.g. only keep the last 24 hours of prefix entries, discarding older ones once no query can reference them) or periodically "re-base" by dropping fully-expired history and adjusting subsequent range-sum math accordingly.

Direct answer

A hash map alone gives $O(1)$ key lookup but has no notion of access order, so evicting the least-recently-used (LRU) entry would mean scanning every entry to find it, which is $O(n)$. Pairing the hash map with a doubly linked list solves this: the hash map maps each key directly to its node in the list, and the list keeps nodes ordered by recency, most-recently-used at the head and least-recently-used at the tail, so a lookup, a reorder-on-access, and an eviction (pop the tail) are all $O(1)$.

Approach

• Maintain a doubly linked list of nodes (key, value), ordered by recency, with dummy head and tail sentinels so inserting or removing at either end never has to special-case an empty list.
• Maintain a hash map from key to the node holding that key, so you never search the list by value; you always jump straight to the node.
• get(key): if the key isn't in the map, return the miss sentinel. Otherwise move that node to the front (most-recently-used position) and return its value.
• put(key, value): if the key exists, update its value and move it to the front. Otherwise create a new node, add it to the front, and if that pushes the map over capacity, remove the node just before the tail sentinel (the actual least-recently-used entry) and delete it from the map too.

class Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map: dict[int, Node] = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: Node) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        if key in self.map:
            node = self.map[key]
            node.value = value
            self._remove(node)
            self._add_to_front(node)
            return
        node = Node(key, value)
        self.map[key] = node
        self._add_to_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]


if __name__ == "__main__":
    cache = LRUCache(2)
    cache.put(1, 1)
    cache.put(2, 2)
    print(cache.get(1))   # 1 (1 is now most recent)
    cache.put(3, 3)       # capacity 2: evicts key 2 (least recently used)
    print(cache.get(2))   # -1
    cache.put(4, 4)       # evicts key 1
    print(cache.get(1))   # -1
    print(cache.get(3))   # 3
    print(cache.get(4))   # 4

Running this prints, in order: 1, -1, -1, 3, 4, which matches the standard LRU trace (put 1, put 2, get 1 promotes key 1, put 3 evicts key 2 since it's now the least recent, put 4 evicts key 1 since 3 was inserted more recently).

Key points

• Every present key has exactly one node in the map and exactly one node in the list; those two structures are kept in lockstep on every operation.
• The head and tail sentinels remove every edge-case branch for "the list is empty" or "the list has one element" from _remove and _add_to_front.
• Deterministic cache keys: the map key must be a stable, complete representation of the thing being cached. If two logically identical requests can hash to different keys, for example because a key is built from an unordered dict or kwargs whose iteration order isn't fixed, or because it omits a parameter that actually affects the result, you get both a spurious cache miss and duplicate storage for what should have been one entry. Build cache keys from a canonical, fully-ordered encoding of every input that affects the output.
• LRU vs. LFU: this design evicts by recency. A least-frequently-used (LFU) policy instead evicts the entry with the smallest access count, which needs a frequency counter per entry plus a way to find the minimum count in $O(1)$ (typically a doubly linked list of frequency buckets, each bucket holding the keys at that frequency). LFU is worth reaching for when recency is a noisy signal, for example a periodic bulk scan that touches every key once would evict your actual hot set under plain LRU even though those keys are still frequently used elsewhere.

Complexity

Time: $O(1)$ for get and put. Space: $O(n)$ for $n$ cached entries (one hash map entry plus one list node per key).

Edge cases

• capacity <= 0: put is a no-op and get always misses.
• Updating an existing key on put must still move it to the front; forgetting that is the most common bug in this design.
• Capacity of exactly 1: every new put after the first immediately evicts the previous entry.
• A workload dominated by a one-time bulk scan defeats plain LRU by evicting the genuinely hot set; that's the scenario where LFU or a hybrid recency-plus-frequency policy earns its extra bookkeeping.

Direct answer

Pick your two or three highest-signal learning experiences, whatever mix of formal and self-directed they are, and for each one name the skills you acquired and one portfolio example where you applied them. Then call out the single most impactful learning experience and say why it mattered more than the rest.

Structured elaboration

Any mix is a valid answer

This question is written to be answered equally well by a degree, a bootcamp, or entirely self-directed study. Don't apologize for an unconventional path, and don't assume a degree alone answers the "how did it prepare you" half.

Per-item pairing

For each learning experience you mention:

• Name the skills you acquired, specifically, not just the credential title.
• Give one portfolio example where you applied them: a project, a repository, a shipped piece of work.
• If the item is a capstone, thesis, internship, or a personal or open-source project, say how you applied that knowledge afterward, in a job or a later project, not just how it went at the time.
• Where you can, name at least two measurable outcomes for it: adoption, a metric you tracked, a concrete result, not just that you finished it.

Naming the standout

Close by naming the single most impactful learning experience and why it mattered. Every candidate has one item that taught them disproportionately more than the others; naming it, with the specific reason, turns a list into a story.

Worked example

"Two things shaped how I work. First, a formal degree gave me the fundamentals: I still use the systems-thinking habits from that coursework, and the clearest example is a capstone project where I designed and built a small end-to-end application, which is what I point to when someone asks for early proof of ability.

Second, and more impactful, was self-directed study after graduating: I worked through an open-source project on my own time to close a gap the degree hadn't covered, contributed a feature that got merged, and later reused that same codebase as a reference when I joined a job that needed similar work.

If I had to name the single most impactful one, it's the open-source work, because it's the only one where nobody assigned the problem to me. Picking my own problem and following it through to something someone else found useful taught me more about finishing work than any assignment did."

Trade-offs & pitfalls

• Listing every course or certification without a paired example turns this into a transcript reading, not a story.
• Treating a formal degree as self-explanatory skips the "how did it prepare you" half of the question entirely.
• Apologizing for a non-traditional path, rather than pairing it with the same evidence a degree would need, undersells it.
• Naming several items with equal weight instead of calling out the most impactful one misses the part of the question asking you to make a judgment.

Direct answer

Time-to-live (TTL) expiry, explicit invalidation, versioning with entity tags (ETags), and write-through invalidation each guarantee freshness differently: TTL is a passive timer, explicit invalidation is an active push the moment data changes, ETag versioning lets clients cheaply confirm whether their copy is still valid, and write-through invalidation updates the cache synchronously as part of the write itself. For a product-pricing service that must show a price change within 5 seconds, the answer is to combine write-through updates for immediacy with a short TTL as a safety net, since relying on either alone leaves a gap: write-through alone has no fallback if an update is missed, and TTL alone cannot guarantee anything faster than the TTL window itself.

Structured elaboration

The four base strategies

• TTL: each cache entry is set to expire automatically after a fixed duration. Simple and requires no coordination, but guarantees only "stale for at most the TTL," never immediate freshness.
• Explicit invalidation: the service that changed the data actively removes or refreshes the specific cache key, typically by publishing an event over a message bus (a publish/subscribe, or pub/sub, mechanism) that every cache node or API server subscribes to, so all of them invalidate or refresh in step rather than each polling independently.
• Versioning with ETags: each response carries a version identifier; clients make conditional requests (If-None-Match) and the server replies with a cheap "not modified" if the version is unchanged, or the full payload if it changed. This mainly saves bandwidth and lets the client self-verify freshness; it does not by itself push updates to anyone.
• Write-through invalidation: on a write, the write path updates both the durable store and the cache atomically (or updates the store then immediately overwrites the cache entry) as part of the same operation, so the very next read already sees the new value with no propagation delay.

Coordination mechanics that make these strategies work at scale

• Pub/sub invalidation and race conditions: broadcasting an invalidation event over pub/sub is what lets many cache nodes and services stay in sync without polling each other, but it introduces a race condition risk: if the event is published before the underlying write is fully durable, or delivered out of order relative to a second write on the same key or a deployment that changes read logic, a subscriber can refresh into a value that is itself about to be overturned. Guard against this by publishing the invalidation only after the write is confirmed durable, and by making invalidation handlers idempotent so a duplicate or out-of-order event cannot leave the cache worse off than doing nothing.
• Soft-expiry (stale-while-revalidate) and cache tagging: rather than a hard TTL that forces every expiring request to wait on a fresh fetch, soft expiry serves the stale value immediately while triggering a background refresh, keeping latency low during the refresh window. Cache tagging (grouping many cache entries under a shared tag) lets one invalidation event clear every entry derived from a changed piece of data, without the writer needing to know every individual cache key that resulted from it.
• Key-prefix versioning across services sharing a distributed cache: when multiple services share one distributed cache, a global key-prefix version (bump a shared prefix like v42: to instantly make every key under the old prefix unreachable) gives a cheap way to invalidate an entire class of entries at once, without deleting them individually and without every service needing to agree on invalidation timing key-by-key. The cost is that it invalidates in bulk, which is a blunt instrument if only a subset of that prefix actually changed.
• Soft-delete-plus-revalidation: instead of removing a cache entry outright on a write, mark it stale and let the next read trigger revalidation against the source of truth. This suits high-read workloads well, since it avoids a thundering-herd of readers all missing the cache at once after a hard delete; it suits high-write workloads less well, since a key being marked stale repeatedly under heavy writes gains little over a plain short TTL and adds bookkeeping for no benefit.

Choosing for the 5-second product-pricing requirement

1. Primary mechanism: write-through update. When a price changes, the write path updates the database and updates (or invalidates) the cache entry as part of the same operation, so the instance that handled the write serves the new price immediately, with zero propagation delay for that instance.
2. Fan-out: explicit pub/sub invalidation. The price-change write also publishes an invalidation event so every other cache node and API server, not just the one that handled the write, drops or refreshes its copy without waiting for a TTL to expire.
3. Safety net: a short TTL, strictly shorter than the 5-second requirement, so that if an invalidation event is ever missed (a subscriber was briefly disconnected, a message was dropped), the entry expires and is refetched well within the service-level agreement (SLA) regardless. A TTL near 3 seconds gives roughly 2 seconds of margin against the 5-second requirement while still keeping the cache hit rate high between price changes, which are relatively infrequent events.
4. Client efficiency: ETags on top. Returning a version or ETag lets clients avoid re-downloading a price that has not changed, cutting bandwidth without weakening the freshness guarantee established by steps 1-3.

This mirrors the same trade-off shape as a high-write inventory system needing near-real-time correctness: write-through plus pub/sub invalidation carries the freshness guarantee, and TTL is there purely as the fallback for the failure case, not as the primary mechanism, because TTL alone cannot promise "within 5 seconds" without being set so short it defeats the purpose of caching in the first place.

HTTP-level mechanics for a semi-dynamic JSON API

The same ideas map onto standard HTTP headers when the pricing data is exposed through a semi-dynamic JSON API: Cache-Control and Surrogate-Control set the client-facing and edge-facing TTLs respectively (the edge can be allowed to cache slightly differently than the browser), Vary ensures responses that differ by request header are not cross-served, ETag enables the conditional-request savings described above, and stale-while-revalidate plus stale-if-error let the edge serve a slightly-stale price during a background refresh or during a brief origin outage rather than failing the request outright. These headers implement the same combination described above (short TTL as the backstop, revalidation as the mechanism that keeps it cheap) at the HTTP caching layer specifically.

Worked example

A price update for one SKU (stock-keeping unit, a unique product identifier) fires at time zero. The write-through update makes the originating instance's cache correct instantly. The pub/sub invalidation event reaches the other 9 API instances within roughly 200 ms under normal message-bus latency, well inside the 5-second budget. If one instance's subscriber connection had silently dropped an hour earlier (the failure case the safety net exists for), that instance would still be serving the old price from cache, until its 3-second TTL on that entry expires and the next read refetches the current price, landing at worst 3 seconds after the change, still inside the 5-second requirement.

Trade-offs & pitfalls

• Relying on TTL alone for a tight freshness requirement forces the TTL down to where it defeats caching's purpose (a 1-second TTL on a hot key approaches the request rate itself); combining it with an active-invalidation mechanism is what lets the TTL stay a safety net instead of the primary lever.
• Pub/sub invalidation requires reliable, idempotent delivery; treating it as guaranteed-delivery without a fallback (the TTL backstop above) is the single most common way "instant" cache invalidation quietly breaks under a dropped connection or a deploy.
• Key-prefix versioning is a fast, coarse bulk-invalidation tool, not a substitute for targeted invalidation; using it for every single-key change wastes cache warmth across unrelated keys under the same prefix.
• Soft-delete-plus-revalidation and hard TTL expiry solve similar problems differently depending on read/write ratio; picking soft-delete for a write-heavy key just adds bookkeeping overhead without the thundering-herd benefit it was designed for, since a write-heavy key rarely stays warm long enough for that benefit to matter.

Direct answer
Beyond word choice, deliberate pacing, brief pauses at key transitions, and periodic checkpoints where you invite a question all help a live audience stay oriented during a longer explanation.

Structured elaboration

• Pacing: slowing down slightly at the most important sentence (a conclusion, a number, a decision point) signals to the listener that this part matters more than the surrounding context, the same way bolding a phrase does on a page.
• Pauses at transitions: a brief pause when moving from one idea to the next gives the listener a moment to finish processing the previous point instead of having it run together with the next one.
• Checkpoints for questions: explicitly stopping every few minutes to ask "does that make sense so far, any questions before I move on?" catches confusion early, while it's still cheap to address, rather than at the end when the listener has been lost for a while.
• Choosing two or three of these deliberately, rather than trying to do everything at once, is more sustainable; trying to consciously manage every aspect of delivery simultaneously tends to make a speaker sound stilted.

Worked example
During a fifteen-minute technical walkthrough: slow down and pause briefly right before stating the recommendation ("...and so, the option we're proposing is [pause] option two"), then at the two natural section breaks (after background, and after the options), stop explicitly and ask "any questions before I move to the next part?" rather than only checking in at the very end.

Trade-offs and pitfalls

• Overusing dramatic pauses or slowing down on things that aren't actually the key point dilutes the technique; it works because it's used selectively.
• Checkpoints can eat into your time budget if the audience takes them as an invitation for a lengthy tangent; it can help to explicitly frame them as "quick check" rather than opening the floor fully.
• These techniques don't substitute for a clear structure; a well-paced explanation of a confusing structure is still confusing, just more pleasant to listen to.

Direct answer

Keep two pieces of state: the confirmed state (what the server has acknowledged) and an ordered list of pending operations (sent, not yet acknowledged). What the UI shows is always "confirmed state with every pending operation re-applied on top". Each operation gets a client-generated ID before it is sent, and every retry reuses that same ID, so the server can recognise a duplicate and not apply it twice. An ACK moves the operation into confirmed state; a NACK simply removes it from the pending list (which is the rollback); a conflict replaces confirmed state with the server's version and either re-applies the operation on top (rebase) or drops it and tells the user.

Approach

• Optimistic update means showing the result of a user action before the server confirms it, betting that the server will accept it.
• ACK / NACK: the server's positive and negative acknowledgements. A conflict is a third answer: "your change was based on an older version than mine" (a version here is a number the server increments every time it applies a change; a request carries the version the client last saw, and if that is older than the server's current version for the field being changed, someone else's change landed first).
• Idempotent means doing it twice has the same effect as doing it once. Networks lose replies, so the client must retry, and the server must make retries harmless.

Why "recompute from confirmed + pending" instead of undoing a change in place: with two or more ops in flight, undoing op 1 by hand can clobber op 2's effect. Recomputing makes rollback trivial and correct in any order: remove the op, recompute.

Code (JavaScript, runnable with Node)

// Optimistic updates over a realtime channel: a to-do list keyed by item id.
// State model: confirmed (last server-acknowledged state) + pending ops.
// The UI always shows: confirmed with every pending op re-applied on top.

let nextTemp = 0;
function newClientOpId() {
  // In a browser use crypto.randomUUID(); a counter keeps this demo deterministic.
  nextTemp += 1;
  return `op-${nextTemp}`;
}

function applyOp(state, op) {
  const s = new Map(state);
  if (op.type === 'add') s.set(op.itemId, { text: op.text, done: false });
  if (op.type === 'toggle' && s.has(op.itemId)) {
    s.set(op.itemId, { ...s.get(op.itemId), done: !s.get(op.itemId).done });
  }
  if (op.type === 'rename' && s.has(op.itemId)) {
    s.set(op.itemId, { ...s.get(op.itemId), text: op.text });
  }
  return s;
}

class OptimisticStore {
  constructor(send) {
    this.send = send;            // function(message) that writes to the channel
    this.confirmed = new Map();  // server-acknowledged state
    this.pending = [];           // ops sent (or queued) but not yet ACKed, in order
    this.view = new Map();       // what the UI renders
  }

  recompute() {
    this.view = this.pending.reduce(applyOp, this.confirmed);
  }

  // 1. apply locally  2. enqueue with a client id  3. send
  submit(op) {
    const clientOpId = newClientOpId();
    const entry = { ...op, clientOpId, attempts: 0, baseVersion: this.version ?? 0 };
    this.pending.push(entry);
    this.recompute();              // user sees the change immediately
    this.transmit(entry);
    return clientOpId;
  }

  transmit(entry) {
    entry.attempts += 1;
    // The SAME clientOpId is sent on every retry: that is what makes retries idempotent.
    this.send({ kind: 'op', clientOpId: entry.clientOpId, op: entry, baseVersion: entry.baseVersion });
  }

  // Called by the reconnect logic or a per-op timer: resend everything still unacknowledged.
  retryUnacked() {
    for (const entry of this.pending) this.transmit(entry);
  }

  // 4. handle server responses
  onMessage(msg) {
    const idx = this.pending.findIndex(p => p.clientOpId === msg.clientOpId);
    if (msg.kind === 'ack') {
      if (idx === -1) return;                       // duplicate ACK for an op already settled
      const [entry] = this.pending.splice(idx, 1);
      // Fold into confirmed. If the server rewrote the op (e.g. assigned a real id),
      // it sends the canonical op back and we apply that instead of our guess.
      this.confirmed = applyOp(this.confirmed, msg.canonicalOp ?? entry);
      this.version = msg.version;
    } else if (msg.kind === 'nack') {
      if (idx === -1) return;
      this.pending.splice(idx, 1);                  // drop it: rollback is just "stop re-applying it"
      this.lastError = `${msg.clientOpId} rejected: ${msg.reason}`;
    } else if (msg.kind === 'conflict') {
      if (idx === -1) return;
      // Server says our base was stale and sends its current authoritative state.
      this.confirmed = new Map(msg.serverState);
      this.version = msg.version;
      const [entry] = this.pending.splice(idx, 1);
      if (msg.retryable) {                          // rebase: re-apply on the fresh state and resend
        entry.baseVersion = msg.version;
        this.pending.splice(idx, 0, entry);
        this.transmit(entry);
      } else {
        this.lastError = `${msg.clientOpId} conflicted and was discarded`;
      }
    } else if (msg.kind === 'remote') {
      // Someone else's change: update confirmed, pending ops stay on top.
      this.confirmed = applyOp(this.confirmed, msg.op);
      this.version = msg.version;
    }
    this.recompute();
  }
}

// ---- A fake server, so the demo runs with no network ----
const server = { state: new Map(), version: 0, seen: new Map() };
function serverHandle(msg) {
  // Idempotency: a clientOpId already processed returns the stored reply, no second apply.
  if (server.seen.has(msg.clientOpId)) return server.seen.get(msg.clientOpId);
  let reply;
  if (msg.op.type === 'rename' && msg.op.text.length > 20) {
    reply = { kind: 'nack', clientOpId: msg.clientOpId, reason: 'text too long' };
  } else if (msg.op.type === 'rename' && msg.baseVersion < server.lastRenameVersion) {
    reply = { kind: 'conflict', clientOpId: msg.clientOpId, retryable: true,
              serverState: [...server.state], version: server.version };
    return reply;                                 // conflicts are not cached: a rebased resend must be evaluated
  } else {
    server.state = applyOp(server.state, msg.op);
    server.version += 1;
    if (msg.op.type === 'rename') server.lastRenameVersion = server.version;
    reply = { kind: 'ack', clientOpId: msg.clientOpId, version: server.version };
  }
  server.seen.set(msg.clientOpId, reply);
  return reply;
}

const outbox = [];
const store = new OptimisticStore(m => outbox.push(m));
const show = label => console.log(label.padEnd(34), JSON.stringify([...store.view]));

store.submit({ type: 'add', itemId: 'a', text: 'buy milk' });
store.submit({ type: 'toggle', itemId: 'a' });
show('after 2 local ops (no reply yet):');

// Network hiccup: the first send is delivered, its ACK is lost, and the client retries.
serverHandle(outbox[0]);                           // server applies op-1, reply lost
store.retryUnacked();                              // resends op-1 and op-2 with the same ids
console.log('outbox after retry:', outbox.length, 'sends: op-1 and op-2 each appear twice (original entry plus retry copy)');
for (const m of outbox.splice(0)) store.onMessage(serverHandle(m));
console.log('server applied op-1 once? version =', server.version, '(expected 2)');
show('after ACKs:');

store.submit({ type: 'rename', itemId: 'a', text: 'buy oat milk and bread, 2 loaves' });
show('optimistic long rename:');
for (const m of outbox.splice(0)) store.onMessage(serverHandle(m));
show('after NACK (rolled back):');
console.log('error shown to user:', store.lastError);

// Conflict: another user renames 'a' first; our rename was based on an older version.
store.submit({ type: 'rename', itemId: 'a', text: 'milk x2' });
serverHandle({ kind: 'op', clientOpId: 'other-user-1', op: { type: 'rename', itemId: 'a', text: 'milk (whole)' }, baseVersion: server.version });
store.onMessage({ kind: 'remote', op: { type: 'rename', itemId: 'a', text: 'milk (whole)' }, version: server.version });
show('remote change arrives, ours on top:');
for (const m of outbox.splice(0)) store.onMessage(serverHandle(m));   // conflict -> rebase -> resend
for (const m of outbox.splice(0)) store.onMessage(serverHandle(m));   // resend is accepted
show('after conflict + rebase + ACK:');
console.log('pending ops left:', store.pending.length, '| server:', JSON.stringify([...server.state]));

Output of node optimistic.js:

after 2 local ops (no reply yet):  [["a",{"text":"buy milk","done":true}]]
outbox after retry: 4 sends: op-1 and op-2 each appear twice (original entry plus retry copy)
server applied op-1 once? version = 2 (expected 2)
after ACKs:                        [["a",{"text":"buy milk","done":true}]]
optimistic long rename:            [["a",{"text":"buy oat milk and bread, 2 loaves","done":true}]]
after NACK (rolled back):          [["a",{"text":"buy milk","done":true}]]
error shown to user: op-3 rejected: text too long
remote change arrives, ours on top: [["a",{"text":"milk x2","done":true}]]
after conflict + rebase + ACK:     [["a",{"text":"milk x2","done":true}]]
pending ops left: 0 | server: [["a",{"text":"milk x2","done":true}]]

What the run shows:

• Retry without double-apply. op-1's message reaches serverHandle three times in total: once from the direct serverHandle(outbox[0]) call that simulates delivery with a lost reply, then twice more when the batch loop replays both the still-queued original entry and its retry copy (neither was ever removed from outbox). op-2 reaches it twice: its original and its retry, both replayed for the first time in that same batch loop. Yet server.version ends at 2: each op is applied exactly once (server.seen catches every later call for the same clientOpId and returns the cached reply instead of re-applying), and on the client side pending only lets the very first ack through for each op, ignoring the rest because the op is no longer pending by then.
• Rollback on NACK. The long rename displayed instantly, the server rejected it, and the view went back to "buy milk" without any hand-written undo code.
• Conflict and rebase. Another user's rename landed first. The client took the server's state, re-applied its own rename on top, re-sent it with the newer base version, and ended with nothing pending and client and server agreeing.

Key points

1. Apply locally: submit() pushes the op onto pending and recomputes the view before any network I/O.
2. Enqueue with a temporary ID: clientOpId is created on the client. In a browser use crypto.randomUUID() (the demo uses a counter only to make output deterministic). If the op creates an entity, the client can also mint a temporary entity id; the ACK then carries the server's canonical op (canonicalOp) with the real id, and the client applies that instead of its guess.
3. Send: transmit() always sends the same clientOpId for the same op.
4. Handle responses: ACK folds the op into confirmed; NACK drops it and surfaces an error; conflict resets confirmed to the server's state and rebases or discards; a remote message (someone else's change) updates confirmed while local pending ops stay on top.
5. Reconcile: after every message, recompute() rebuilds the view, so the screen is always consistent with what the client knows.

Idempotency considerations for retries

• The key is the op, not the attempt. Generate clientOpId once per user action and persist it with the pending op (for example in IndexedDB) so a page reload or reconnect retries with the same id instead of minting a new one.
• The server stores the outcome, not just "seen". The fake server caches the full reply per clientOpId and returns it for duplicates, so a retry after a lost ACK gets the same ACK (and the same assigned version) rather than an error.
• Do not cache conflicts. A conflict reply depends on the state at that moment; the rebased resend must be evaluated fresh. In the demo, conflicts return before the cache write.
• Bound the dedup memory. Keep ids for longer than the client's maximum retry window (for example 24 hours) and then expire them; key them per user or per document so one client cannot evict another's entries.
• Order matters for dependent ops. "Add item" then "toggle item" must reach the server in order. Resending the whole pending list in order on reconnect (as retryUnacked() does) preserves that; the server can additionally reject an op whose target does not exist yet, and the client retries it after the earlier op is ACKed.

Complexity

• submit and every response do one recompute(), which is O(P x cost of applyOp) where P is the number of pending ops. P is normally 0 to a handful, so this is cheap; if P could grow large (long offline editing), snapshot the view and replay only ops after the changed one.
• Finding the op for a reply is O(P) with findIndex; a Map from clientOpId to index makes it O(1) if P is large.

Edge cases

• Duplicate ACK or late ACK for an already-settled op: ignored (idx === -1).
• NACK for an op that later ops depend on (rename of an item whose add was rejected): recompute naturally drops the effect of the dependent op because applyOp ignores ops whose target is missing; the dependent op will itself be NACKed by the server.
• Reconnect: resend all pending ops in order with their original ids; the server's dedup makes this safe.
• Rebase is last-writer-wins for the field. In the demo the user's rename overwrote the other user's. For content where that loses work (document text), show the conflict to the user or use a merge strategy instead of silently rebasing.
• Never-answered ops: a per-op timer should trigger retryUnacked(), and after a few failures the UI should mark the item as "not saved" rather than showing it as saved forever.

Direct answer

A 10x jump in message throughput doesn't uniformly stress every part of a messaging app's design; it stresses the components whose load scales directly with message volume (the message broker, delivery workers, database writes for messages) and leaves largely untouched the components whose load scales with something else (user authentication, profile lookups, once-per-session connection setup). Deciding what to revisit versus leave alone comes down to tracing which components' load is actually a function of message throughput.

Structured elaboration

For each system component, ask: does its load scale with message volume, with active user count, or with something independent of both? That answer decides whether the 10x change touches it.

Scales with message throughput, revisit: the message broker/queue (partition count and per-partition throughput), delivery/fan-out workers, database write capacity for message storage, and any per-message monitoring or logging pipeline.

Scales with user count or session activity, mostly leave alone: authentication, user profile storage, push-notification token registration, and connection/session management, none of which get 10x busier just because message volume did.

Needs a fresh look regardless: cost forecasting (10x throughput changes the cost curve even where architecture doesn't change), and operational readiness (on-call load, alerting thresholds, and mean time to detect/restore all need revisiting because incidents become more consequential at higher throughput, even in components that didn't need architectural changes).

Worked example

Assume, as illustrative pinned inputs, 1 million monthly active users (MAU) sending an average of 50 messages/user/day:
$\text{baseline total msgs/day} = 1{,}000{,}000 \text{ MAU} \times 50 \text{ msgs/user/day} = 50{,}000{,}000 \text{ msgs/day}$
$\text{baseline avg} = \frac{50{,}000{,}000}{86{,}400\text{ s}} \approx 579 \text{ msgs/s}$
After the 10x throughput change:
$\text{after 10x} = 579 \times 10 \approx 5{,}787 \text{ msgs/s average}$
and, using an illustrative 4x peak-to-average ratio for messaging traffic during busy hours:
$\text{illustrative peak (4x average)} \approx 5{,}787 \times 4 \approx 23{,}148 \text{ msgs/s}$
That rise from roughly 579 to nearly 23,000 msgs/s at peak is what forces a hard look at broker partition count and delivery-worker concurrency. Meanwhile the authentication service, whose load tracks login attempts per MAU rather than messages sent, sees no comparable change and doesn't need re-architecting just because this number moved.

Trade-offs & pitfalls

• The most common mistake is treating a throughput change as a blanket "redesign everything" trigger; tracing each component's actual load driver is what separates urgent work from unaffected components.
• Cost still needs re-forecasting even for unaffected components' surrounding infrastructure (network egress, storage growth), because 10x more messages moving through the system has cost implications beyond the components that need architectural change.
• Don't defer operational readiness (alert thresholds, on-call capacity, incident runbooks) just because it isn't an architectural change; an incident at 10x throughput is a bigger incident even if the design handles the load correctly.
• If the 10x increase is concentrated in a small subset of highly active users rather than spread evenly, the actual bottleneck (a handful of hot conversations or channels) may look different from what a uniform-average calculation like the one above would suggest; validate the assumption behind the average before committing to a fix.

The idea

A string of parentheses is valid when, reading left to right, you never close more than you have opened, and by the end the counts are equal. Instead of generating every string and checking it, build the string one character at a time and only ever make a move that keeps it valid. That needs two rules: you may add "(" while fewer than n have been opened, and you may add ")" only while the number of ")" is less than the number of "(" so far. A step that would break a rule is never taken, so every string that reaches full length 2n is already valid.

This is backtracking: extend a partial answer by one choice, recurse, then undo that choice (here path.pop()) so the same list can be reused for the next choice.

Brute force and why it is not enough

Trying every string of "(" and ")" of length 2n and filtering for validity looks at 2^(2n) strings. For n = 10 that is 1,048,576 strings to find 16,796 valid ones. The two rules above cut off a doomed branch the moment it becomes doomed, so no work is spent on prefixes like "())".

The code

from math import comb


def generate_parentheses(n):
    result = []
    path = []

    def build(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        if opened < n:
            path.append("(")
            build(opened + 1, closed)
            path.pop()
        if closed < opened:
            path.append(")")
            build(opened, closed + 1)
            path.pop()

    build(0, 0)
    return result


print(generate_parentheses(3))

for n in range(0, 9):
    count = len(generate_parentheses(n))
    assert count == comb(2 * n, n) // (n + 1)
    print(n, count)

Output:

['((()))', '(()())', '(())()', '()(())', '()()()']
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430

The assert inside the loop checks each count against the closed formula C(2n, n) / (n + 1).

Worked trace for n = 2

Each line is one call. Indentation is the depth. A leaf at depth 4 is a finished string; the code then pops the last character and tries the other choice one level up.

def generate_parentheses_traced(n):
    result = []
    path = []

    def build(opened, closed, depth):
        print(f"{'  ' * depth}depth={depth} path={''.join(path)!r} opened={opened} closed={closed}")
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        if opened < n:
            path.append("(")
            build(opened + 1, closed, depth + 1)
            path.pop()
        if closed < opened:
            path.append(")")
            build(opened, closed + 1, depth + 1)
            path.pop()

    build(0, 0, 0)
    return result


print(generate_parentheses_traced(2))

Output:

depth=0 path='' opened=0 closed=0
  depth=1 path='(' opened=1 closed=0
    depth=2 path='((' opened=2 closed=0
      depth=3 path='(()' opened=2 closed=1
        depth=4 path='(())' opened=2 closed=2
    depth=2 path='()' opened=1 closed=1
      depth=3 path='()(' opened=2 closed=1
        depth=4 path='()()' opened=2 closed=2
['(())', '()()']

Reading it: the walk goes (, ((, ((), (()) and records "(())". It backs out to ((, which has no other legal move (a third "(" would exceed n = 2), then to (, where the second option, ")", leads to (), ()( and ()(). Two leaves, so two answers, and no dead ends at all for n = 2.

Why the counts are Catalan numbers

The Catalan numbers are the sequence 1, 1, 2, 5, 14, 42 ... defined by C(0) = 1 and C(n) = C(0)C(n-1) + C(1)C(n-2) + ... + C(n-1)C(0). Here is why that recurrence describes valid strings. In any non-empty valid string, the first "(" is closed by exactly one matching ")". Everything between them is a valid string of k pairs, and everything after is a valid string of n-1-k pairs, for some k from 0 to n-1. Each split gives a different string, and every string arises from exactly one split, so

C(3) = C(0)C(2) + C(1)C(1) + C(2)C(0) = 2 + 1 + 2 = 5.

Here is that argument on the five real strings for n = 3. For each string, find the ")" that closes the first "("; the text between them is the inside (k pairs) and the text after is the rest (2 - k pairs):

((()))  inside='(())' (2 pair(s))  after='' (0 pair(s))
(()())  inside='()()' (2 pair(s))  after='' (0 pair(s))
(())()  inside='()' (1 pair(s))  after='()' (1 pair(s))
()(())  inside='' (0 pair(s))  after='(())' (2 pair(s))
()()()  inside='' (0 pair(s))  after='()()' (2 pair(s))

The splits are k = 2 (two strings, C(2) = 2 choices of inside times C(0) = 1 choice of rest), k = 1 (one string: C(1) x C(1) = 1) and k = 0 (two strings: C(0) x C(2) = 2). That is 2 + 1 + 2 = 5, and every string appears under exactly one split because the first "(" has exactly one matching ")". The same program, shown in full in the Complexity section, prints this table.

The closed form is a formula that gives C(n) directly without computing the smaller values first: C(n) = C(2n, n) / (n + 1), where C(2n, n) is the number of ways to choose n positions out of 2n. The table above (1, 1, 2, 5, 14, 42, 132, 429, 1430 for n = 0 to 8) agrees with it.

Why the recursion's result count equals C(n): the split argument counts the valid strings of n pairs. The recursion produces exactly those strings, each once. It never produces an invalid string, because the two rules refuse any step that breaks validity. It never skips a valid one, because every prefix of a valid string obeys both rules, so the walk that spells it out is never blocked. And it never produces a string twice, because the sequence of characters chosen is the string, so two different walks give two different strings.

Recursion depth

Every call adds exactly one character, so a root-to-leaf path has 2n calls below the first one: 2n + 1 frames in total (the trace for n = 2 runs from depth 0 to depth 4, five frames). The depth grows linearly in n and is tiny next to the output: C(20) is 6,564,120,420 strings, so memory for the result, not the stack, is the limit long before Python's default 1000-frame recursion limit matters.

Complexity

• Number of calls: the program below prints 3, 8, 22, 64 and 196 calls for n = 1 to 5. Every call lies on a path from the root to some finished string, and each such path has 2n + 1 calls, so the total number of calls is at most (2n + 1) times the number of results. The table confirms it: n = 4 has 64 calls against a ceiling of 9 x 14 = 126.
• Time: O(n x C(n)) overall. Each of the C(n) results costs O(n) to join into a string, and the calls are bounded by (2n + 1) x C(n), which is also O(n x C(n)). How fast C(n) itself grows: C(2n, n) is about 4^n / sqrt(pi x n) (a standard Stirling-formula estimate for choosing n out of 2n), and dividing by n + 1 turns the n^(1/2) into n^(3/2). So C(n) is roughly 4^n / (1.77 x n^(3/2)), where 1.77 is sqrt(pi). In plain words, the output grows by a factor that climbs toward 4 with each extra pair: 3.0 from n = 4 to 5 (14 to 42), 3.3 from n = 7 to 8 (429 to 1430), and about 3.7 from n = 19 to 20. The printed values show the shape: n = 10 has 16,796 results and n = 20 has 6,564,120,420.
• Space beyond the output: O(n) for the path list and the recursion stack. The output holds C(n) strings of length 2n.

This program prints the five splits above, the call counts, and a comparison of C(n) with 4^n / n^(3/2) (the two differ by a factor that approaches sqrt(pi), about 1.77, as n grows):

from math import comb


def generate_parentheses(n):
    result = []
    path = []
    calls = 0

    def build(opened, closed):
        nonlocal calls
        calls += 1
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        if opened < n:
            path.append("(")
            build(opened + 1, closed)
            path.pop()
        if closed < opened:
            path.append(")")
            build(opened, closed + 1)
            path.pop()

    build(0, 0)
    return result, calls


def split_of(s):
    """Return (inside, after) around the ')' that matches the first '('."""
    depth = 0
    for i, ch in enumerate(s):
        depth += 1 if ch == "(" else -1
        if depth == 0:
            return s[1:i], s[i + 1:]


strings, _ = generate_parentheses(3)
for s in strings:
    inside, after = split_of(s)
    print(f"{s}  inside={inside!r} ({len(inside) // 2} pair(s))  after={after!r} ({len(after) // 2} pair(s))")

print("n  results  calls  (2n+1)*results")
for n in range(1, 6):
    res, calls = generate_parentheses(n)
    print(f"{n}  {len(res):7}  {calls:5}  {(2 * n + 1) * len(res):10}")

print("n  C(n)  4^n/n^1.5")
for n in (5, 10, 15, 20):
    print(n, comb(2 * n, n) // (n + 1), round(4 ** n / n ** 1.5))
print("3 kinds, n=2:", comb(4, 2) // 3 * 3 ** 2)

Output:

((()))  inside='(())' (2 pair(s))  after='' (0 pair(s))
(()())  inside='()()' (2 pair(s))  after='' (0 pair(s))
(())()  inside='()' (1 pair(s))  after='()' (1 pair(s))
()(())  inside='' (0 pair(s))  after='(())' (2 pair(s))
()()()  inside='' (0 pair(s))  after='()()' (2 pair(s))
n  results  calls  (2n+1)*results
1        1      3           3
2        2      8          10
3        5     22          35
4       14     64         126
5       42    196         462
n  C(n)  4^n/n^1.5
5 42 92
10 16796 33159
15 9694845 18482596
20 6564120420 12292913709
3 kinds, n=2: 18

Edge cases and common mistakes

• n = 0 returns one empty string (['']), matching C(0) = 1; n = 1 returns ['()']; a negative n returns [].
• Forgetting path.pop() after a recursive call corrupts every later string.
• Testing closed < n instead of closed < opened lets a string like "())" be built.
• Appending path itself to the result stores a list that keeps changing; join it into a string first, as the code does.
• Passing a new string at each call (build(prefix + "(")) is also correct and needs no pop, at the price of copying the prefix on every call.

Follow-ups

• Return only the count, not the strings: use the Catalan recurrence with memoization (remembering results already computed) in O(n^2) time.
• Several bracket kinds, "()", "[]" and "{}": each pair independently picks a kind, so the count becomes C(n) x 3^n and the recursion also has to remember which kind is open on top. The reason: each of the n pairs of brackets independently takes one of 3 kinds, giving 3^n labellings of the same shape. For n = 2 there are 2 shapes and 9 labellings of each, so 18 strings (the last line of the output above).
• Check whether a given string is valid: one pass with a counter.

Running the code

Python 3.12, standard library only.
python3 parentheses.py        (the first listing, saved as parentheses.py)
python3 parentheses_trace.py  (the second listing)
python3 parentheses_calls.py  (the listing in the Complexity section)

Method 1 — Heuristic + historical averages

• What: Use segmented historical travel times by route, time-of-day, day-of-week; add buffer for variance.
• Data inputs: past trip records (start/end, timestamps, durations), basic route geometry, calendar info (holidays).
• Engineering complexity: Low — ETL pipeline to aggregate, simple lookup service on backend, cached results in Redis; frontend shows stable ETA with confidence bands.
• Limitations: Cold-start for new routes/drivers, sparse data yields high variance, can't adapt quickly to live incidents.

Method 2 — Real-time GPS + map-matching with traffic feeds

• What: Continuously ingest vehicle GPS, map-match to road network, incorporate live traffic (third-party API) to compute shortest-time routes.
• Data inputs: streaming GPS, road graph, traffic API, current speed on segments.
• Engineering complexity: Medium — stream processing, map-matching library, route engine or SDK integration, websocket updates to clients.
• Limitations: GPS noise, network latency, dependency on external traffic provider costs/SLAs, degraded when GPS sparse.

Method 3 — ML model (feature-based + online learning)

• What: Train model (e.g., Gradient Boosted Trees or LightGBM + periodic retrain / incremental updates) predicting trip duration from features.
• Data inputs: historical trips, real-time telemetry, weather, driver behavior, POI/road features, temporal features.
• Engineering complexity: High — feature pipeline, model training/deployment, monitoring, A/B testing, CI for models; integrate predictions into API.
• Limitations: Cold-start for new areas/drivers (mitigate with transfer learning or hierarchical priors), requires labeling and data quality, risk of model drift needing ops.

For a full-stack role I'd prioritize incremental rollout: start with heuristics, add real-time map-matching, then deploy ML while exposing confidence and fallbacks in frontend UX.