Amazon Staff Software Engineer Interview Preparation Guide

At a handful of nodes a fixed heartbeat timeout works fine: miss N beats, declare the node down. At several thousand nodes spread across racks and regions, the same fixed threshold produces both false positives (a node under scheduling pressure or behind a congested link gets marked down while still alive) and slow true detections (a threshold loose enough to avoid those false positives takes too long to catch a real failure), because network and scheduling jitter is not uniform across the cluster. A Phi Accrual failure detector replaces the single global timeout with a statistical model of each node's own recent heartbeat behavior, so the question becomes how improbable this silence is given what has actually been observed from that specific node, rather than whether more than T seconds have passed, and it outputs a continuously increasing suspicion level, phi, instead of a binary up-or-down verdict.

Membership and probing, before the suspicion model

• Partial views and gossip: each node keeps a small, mostly random subset of the membership rather than the full list, and periodically gossips membership updates and heartbeats to a few random peers, so state propagation stays cheap instead of all-to-all.
• Direct and indirect probing (SWIM-style; SWIM: a gossip-based membership protocol combining direct pings with an indirect fallback): a node pings a random peer directly, and if it gets no acknowledgment, asks a handful of other random members to ping that peer on its behalf, since one lossy path between two specific nodes should not be read as evidence the target itself is down.
• A minimal membership-manager state machine per monitored node: ALIVE, SUSPECT, DEAD. Failed direct-plus-indirect probes move a node from ALIVE to SUSPECT rather than straight to DEAD, and the suspicion is gossiped with an incarnation number, so a node that is actually alive can refute it by re-announcing itself with a higher incarnation before it is declared DEAD and dropped from membership.

From a binary probe result to a continuous suspicion level

Probing only tells you whether a heartbeat arrived, which is still binary. Phi accrual sits on top of that: instead of one global timeout, each node keeps a short sliding window of the actual inter-arrival times it has observed from a given peer, uses that history to estimate how spread out that peer's heartbeats normally are, and converts the elapsed time since the last heartbeat into a suspicion level using roughly:

where $P_{later}(t)$ is the estimated probability, given that peer's own recent history, that a heartbeat still arrives more than $t$ time units after the previous one. As $t$ grows past what the peer's history says is normal, $P_{later}(t)$ shrinks and phi grows smoothly and without bound, instead of snapping from 0 to 1 at one fixed cutoff.

Why this matters at thousands of nodes: a peer on a congested cross-region link naturally has wider jitter in its own history, so it takes a longer silence to reach the same phi value as a peer on a quiet local link, without anyone hand-tuning a per-peer timeout. It also lets different consumers of the same signal act at different confidence levels: something that only needs to stop routing traffic to a possibly-dead node can act at a low phi and cheaply reverse course if the node turns out fine, while something that removes a node from a lock's quorum permanently can wait for a much higher phi, all from the same underlying measurement.

Worked example: computing phi from a pinned heartbeat history

Take a 6-sample sliding window of observed inter-arrival times, in milliseconds, for one peer: [1000, 1300, 700, 1100, 900, 1200].

Mean $\mu = 1033.33$ ms, population standard deviation $\sigma = 197.2$ ms.

Approximating the interval distribution as Normal($\mu, \sigma^2$), so that $P_{later}(t) = \tfrac{1}{2}\,\mathrm{erfc}\!\left(\tfrac{t-\mu}{\sigma\sqrt{2}}\right)$ (erfc is the complementary error function, a standard tool for turning a distance from the mean into the probability mass remaining in the distribution's tail beyond that point), gives:

Tracing the 1500 ms row end to end: standardize the elapsed time against this peer's own mean and spread, $z = (1500 - 1033.33) / (197.2 \times \sqrt{2}) = 466.67 / 278.88 \approx 1.673$; convert that into a tail probability, $P_{later}(1500) = \tfrac{1}{2}\,\mathrm{erfc}(1.673) \approx \tfrac{1}{2} \times 0.0180 \approx 0.00898$; then take $-\log_{10}$ of that probability, $\phi(1500) = -\log_{10}(0.00898) \approx 2.05$. The other three rows fall out of the same three steps with a different elapsed time plugged in.

At t = 1000 ms, right around this peer's own mean, phi stays near zero: nothing unusual. At t = 1500 ms, phi crosses 2, a mild anomaly worth noting but not worth acting on for most purposes. By t = 2500 ms, phi is in the double digits, meaning the observed silence is astronomically improbable given this specific peer's recent behavior, which is enough statistical confidence for even a conservative consumer to move the node to SUSPECT, or to DEAD if it was already SUSPECT and never refuted with a higher incarnation.

Trade-offs and pitfalls

Phi is not a probability itself, it is a log-scaled confidence score, and reading a given phi value as a direct percentage chance of failure is a common misunderstanding; the number only means something relative to whatever threshold a given consumer chooses. A second pitfall is picking one global phi threshold across a heterogeneous fleet, which reintroduces the exact problem this design was meant to solve, since the entire benefit comes from calibrating to each peer's own recent history rather than from a smarter constant. Third, phi accrual detects the absence of a heartbeat; it cannot distinguish a genuinely dead node from a network partition dropping every packet between two specific nodes while both are alive and healthy elsewhere, so membership decisions that need to be safe, like removing a node from a lock's quorum, still need a consensus-backed or fencing mechanism layered on top of the suspicion signal, not phi alone.

Direct answer

Backward and forward compatibility for an evolving API or message schema both rest on the same principle: only add optional things, never repurpose or remove what already exists, so an old reader can ignore fields it doesn't recognize and a new reader can supply sensible defaults for fields an old writer never sent.

Structured elaboration

• In a relational database: add new columns as nullable (or with a default), never repurpose an existing column's meaning, and treat removing a column as a multi-step deprecation (stop writing to it, confirm nothing reads it, then drop it), the same expand-contract discipline used for any schema migration.
• In a message schema (Avro/Protobuf): both formats have explicit compatibility rules for exactly this scenario. Protobuf: every field has a unique numbered tag; adding a new field with a new tag number is safe for both old and new readers (old readers simply ignore the unrecognized field, new readers see a default if an old writer never sent it); renaming a field is safe (only the tag number matters on the wire, not the name); but reusing a tag number for a different field, or changing a field's type incompatibly, breaks compatibility. Avro: relies on both the writer's and reader's schema being available at deserialization time, with defined rules for how a reader schema resolves fields present in the writer schema but not the reader's (and vice versa), which is why Avro deployments typically pair with a schema registry to track compatibility across versions centrally.

Worked example

A concrete safe evolution: an Order message adds a new optional discount_code field with a fresh tag number. Old consumers, compiled against the schema before the change, simply never see discount_code and continue working unaffected (forward compatibility: old code tolerates new data). New consumers reading a message produced by an old producer that never set discount_code see it as unset/default (backward compatibility: new code tolerates old data). Contrast with an UNSAFE change: renaming a field's tag number, or changing discount_code from a string to a nested message, both of which would misinterpret bytes on the wire for whichever side didn't get the corresponding update at the same time.

Trade-offs and pitfalls

• The single most common way this compatibility discipline breaks in practice is repurposing a field for a new meaning without changing its identifier (its tag number, or its column name); this passes casually because the schema still "type-checks," but it silently misinterprets historical data or in-flight messages produced under the old meaning.
• A schema registry (for Avro/Protobuf in a streaming system) or an automated compatibility-check step in CI (for a relational migration) is what turns "we're supposed to follow these rules" into "a violation is caught before it ships," which matters because a compatibility violation is often invisible in a single service's own tests and only surfaces when an old and new version run side by side in production.
• Backward and forward compatibility are genuinely two different guarantees and it's easy to satisfy one while breaking the other; a new required (non-optional) field satisfies "old readers tolerate new data" (nothing about old readers changed) but breaks backward compatibility, since new readers now expect the field on every message, and an old writer's message, produced with no knowledge of the new requirement, would be missing it and rejected as invalid by the new reader.

Direct answer

I distinguish by pattern, not just output level. Burnout or disengagement usually shows up as a broad decline across previously strong areas, paired with a real change in energy or affect (a person's visible mood and emotional expression). A skill gap is usually narrower, tied to a specific type of task, and doesn't come with that affect change. Once burnout is suspected, the shift is from output-focused coaching to a wellbeing-first conversation and workload adjustment.

Distinguishing signals

The diagnostic move

Because the same output pattern (missed deadlines, lower-quality work) can come from either cause, guessing from behavior alone risks the wrong intervention. More skill-focused coaching aimed at someone who's actually burned out just adds pressure. The reliable move is to ask directly and non-accusatorially rather than only inferring, since it's the fastest way to tell the two apart.

What to do differently once suspected

Shift the conversation from task correction to workload and wellbeing. Reduce scope or redistribute urgent items in the short term rather than expecting normal output immediately. Check in more on process and how they're doing than on deliverables for a while. Point toward available support resources where they exist. Avoid escalating straight to a formal performance conversation while this is unresolved, but also avoid treating it as an indefinite excuse, set an actual review point to reassess rather than letting it run open-ended.

Worked example

A mentee whose work had been consistently strong started slipping across several unrelated tasks, not just one. The decline was recent and came with noticeably less participation in discussions, which pointed away from a narrow skill gap. A direct, private conversation surfaced an unsustainable workload building up over recent weeks. The short-term adjustment was reprioritizing their task list and explicitly deprioritizing anything non-urgent, with a check-in scheduled two weeks out to see whether things had actually improved rather than assuming they had.

Trade-offs and pitfalls

A common mistake is treating every dip in output as a skill or effort problem and escalating straight to a formal process. The stronger approach separates "can't" (skill), "won't" (motivation or disengagement), and "can't sustain right now" (burnout), because they call for different responses, while staying alert that a genuine performance issue can coexist with real burnout, one doesn't automatically rule out the other. It's also a pitfall to assume burnout excuses declining output indefinitely: there still needs to be a check-in cadence, and if it doesn't resolve, it may need to go beyond what a mentor alone can fix, involving a manager or people-ops rather than absorbing an open-ended situation solo.

Direct answer. Migrate incrementally by introducing a narrow, explicit interface where the global currently is, routing all access through it, and converting call sites one at a time -- never attempt to delete the global in one step across a codebase that depends on it everywhere.

Why this specific bug is hard to pin down

A global mutable singleton means ANY part of the codebase can read or write shared state at ANY time, so a race condition's trigger might be two completely unrelated modules that happen to touch the singleton concurrently -- the bug's symptom (a corrupted value, an intermittent wrong result) is far from its cause (an unguarded write somewhere else entirely), which is exactly what makes 'intermittent race condition from global state' notoriously hard to debug by inspection alone.

A stepwise migration

1. Wrap the global behind an explicit access interface (a class with getter/setter methods, or accessor functions) even before changing anything about HOW it's stored -- this doesn't fix the race yet, but it gives you a single choke point to instrument and later change.
2. Instrument that choke point (logging, or a debug-build assertion) to find every actual call site touching the shared state, since 'grep for the global variable name' often misses reflection/dynamic access patterns in some languages.
3. Introduce proper synchronization AT THE CHOKE POINT first (a lock, or better, an immutable-value-with-atomic-swap pattern) -- this alone may resolve the race without yet removing the global's global-ness, buying safety quickly.
4. Migrate callers to receive the state via injection (constructor/parameter) instead of reaching for the global directly, one call site or one module at a time, verified independently at each step.
5. Once no caller reaches the global directly anymore, replace it with a properly-scoped instance owned by whichever component actually needs it (often per-request, per-session, or per-worker rather than truly global).

Balancing safety with velocity

Step 3 (synchronize at the existing choke point) often resolves the ACUTE production pain (the race condition) quickly, buying time to do steps 4-5 properly without the pressure of an active incident -- don't let 'we should also remove the global entirely' block shipping the immediate concurrency fix.

Trade-offs and pitfalls

• A lock introduced hastily at the choke point can turn a race condition into a DEADLOCK or a throughput bottleneck if not scoped carefully (locking too broadly, or nesting locks inconsistently across call sites) -- test the fix under realistic concurrent load, not just for absence of the original symptom.
• Don't declare victory once the crash stops reproducing in testing; intermittent concurrency bugs can hide for a long time even after a real fix, and equally, a synchronization fix can mask the symptom without removing the underlying race (e.g., locking the read but not a related write elsewhere) -- confirm the fix addresses the actual mechanism, not just the reproduction you happened to have.

Goal: get new engineers productive in weeks, confident in architecture and delivery within 3 months. Prioritized plan:

1. Week 0 (On day 1) — Foundations

• Provide a one-page "developer playbook" (repo layout, common commands, CI/dev workflow, contacts).
• Setup checklist: local dev server, credentials, IDE config, run tests.
  Milestone: green build locally within 24–48h.

2. Week 1 — Guided exploration (pairing + small tasks)

• Assign a mentor (1:4 ratio) for daily pairing sessions.
• Give two practical exercises: fix a low-risk bug and add a small unit test. Include step-by-step acceptance criteria.
  Milestone: merged first PR and passed CI.

3. Weeks 2–4 — Context and ownership

• Rotation: 1-week shadow across backend, frontend, infra to see end-to-end flow.
• Deeper project doc: architecture diagrams, data flow, deployment pipeline, common antipatterns.
• Practical exercise: implement a small feature touching the pipeline end-to-end.
  Milestone: deliver feature to staging and own rollback/runbook.

4. Month 2–3 — Independent contribution + feedback loops

• Reduce pairing to weekly; mentor reviews focused on design.
• Conduct a knowledge-capture task: update or write documentation for the areas they touched.
• Hold a brown-bag where they present their feature and lessons.
  Milestone: independent release and a documented postmortem of the task.

Documentation improvements (continuous, high-impact):

• Single source of truth (consolidated wiki) with searchable architecture diagrams and troubleshooting playbooks.
• "How-to" runbooks for common tasks and FAQ.
• Living onboarding checklist auto-linked in PR templates.

Mentorship & rotations:

• Mentors get 2–3 hours/week protected time; use a rotation schedule so new hires see multiple owners.
• Pair new hires with rotating code reviewers for broader perspective.

Measurement:

• Track time-to-first-merge, time-to-first-staging-release, and new-hire NPS. Aim to cut time-to-first-merge by 50% and achieve >8/10 NPS within 3 months.

This plan balances immediate wins, contextual learning, documentation hygiene, and mentor-backed autonomy to accelerate ramp-up while reducing bus factor.

Direct answer

Keep a hash map from key to a node holding the value and a frequency count, and a separate doubly linked list (a list where each node points to both its neighbors, so removal and insertion at any known node are O(1), no shifting required) per frequency value. Eviction always pops from the lowest-frequency list, and within that list the head is the least-recently-used (LRU) entry, so the head is exactly the least-frequently-used (LFU) entry with ties broken by recency. Tracking the current minimum frequency separately means you never have to scan for the lowest bucket.

Structured elaboration

Three pieces of state:

• key_node: hash map from key to its node (value, frequency).
• freq_lists: hash map from frequency to a doubly linked list of nodes at that frequency, ordered by recency (oldest at the head, newest at the tail).
• min_freq: the smallest frequency that currently has at least one entry.

On get(key) (and on put for an existing key): look up the node in O(1) via key_node, remove it from its current frequency's list, increment its frequency, and append it to the new frequency's list (append means "just used," so it goes to the tail, the recent end). If removing it emptied the old list and that old frequency was min_freq, bump min_freq by one, since a bucket can only ever empty at the current minimum (nothing decreases frequency).

On put(key, value) for a new key at full capacity: evict the head of freq_lists[min_freq] (LFU, LRU tie-break), remove it from key_node, then insert the new key at frequency 1 and reset min_freq to 1 (a brand new key is always tied for lowest).

Every step touches only hash map entries and linked-list splices at already-known nodes, so both operations run in O(1) average time.

Worked example

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

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


class _FreqList:
    """Doubly linked list of nodes sharing one frequency, ordered by
    recency (head = least recently used within this frequency)."""

    def __init__(self):
        self.head = _Node()
        self.tail = _Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def append(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        node.prev.next = node
        self.tail.prev = node
        self.size += 1

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def pop_lru(self):
        node = self.head.next
        self.remove(node)
        return node


class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.min_freq = 0
        self.key_node: dict[int, _Node] = {}
        self.freq_lists: dict[int, _FreqList] = {}

    def _bump(self, node):
        old_freq = node.freq
        self.freq_lists[old_freq].remove(node)
        if self.freq_lists[old_freq].size == 0:
            del self.freq_lists[old_freq]
            if self.min_freq == old_freq:
                self.min_freq += 1
        node.freq += 1
        self.freq_lists.setdefault(node.freq, _FreqList()).append(node)

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

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.key_node:
            node = self.key_node[key]
            node.value = value
            self._bump(node)
            return
        if self.size == self.capacity:
            evict = self.freq_lists[self.min_freq].pop_lru()
            del self.key_node[evict.key]
            if self.freq_lists[self.min_freq].size == 0:
                del self.freq_lists[self.min_freq]
            self.size -= 1
        node = _Node(key, value)
        self.key_node[key] = node
        self.freq_lists.setdefault(1, _FreqList()).append(node)
        self.min_freq = 1
        self.size += 1


cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))   # 1, freq(1) becomes 2
cache.put(3, 3)       # capacity full; key 2 is the only entry at min_freq=1, evicted
print(cache.get(2))   # -1, evicted
print(cache.get(3))   # 3, freq(3) becomes 2
cache.put(4, 4)       # freq-1 bucket is empty so min_freq=2; key 1 is LRU there, evicted
print(cache.get(1))   # -1, evicted
print(cache.get(3))   # 3
print(cache.get(4))   # 4

Running this prints, in order:

1
-1
3
-1
3
4

Key points

• Each frequency bucket is itself an LRU list, which is what makes the tie-break automatic: the head is always the oldest entry at that frequency.
• min_freq only ever needs to increase, and only when the bucket it points at empties out, so tracking it costs O(1) instead of scanning.

Complexity

for space (one node per stored key, plus the bucket lists which partition those same nodes).

Edge cases

• capacity == 0: put is a no-op, get always returns -1.
• Repeated put on an existing key must bump frequency the same way get does (shown above), not just overwrite the value.
• A put that overwrites a key that would otherwise trigger eviction must update, not evict, since the key is already present.

Trade-offs & pitfalls

The classic bug is forgetting to advance min_freq when the bucket it points at becomes empty. It's tempting to just track the smallest key of freq_lists, but that requires a scan; keeping min_freq as its own O(1)-updated variable is what preserves the overall bound. In Python, a bucket can be implemented as an OrderedDict instead of a hand-rolled doubly linked list (using move_to_end and popitem(last=False)), trading a little control for much less code; for an interview, either is acceptable as long as you can name why it's still O(1). Also worth naming as depth beyond what most interviews require: an LFU cache is more complex to build and reason about than a plain LRU cache, so in practice teams only reach for LFU when access patterns are genuinely skewed by frequency rather than recency, and even then often prefer an approximate LFU (a lossy frequency sketch) over an exact one to bound memory growth.

Direct answer

The recovery and the prevention are two different problems: recovery is about restoring safety in real time, using compensating steps if the clean rollback opportunity has already passed, while prevention is about making the skipped step structurally hard to skip again, not about writing a stricter policy that says not to skip it.

Structured elaboration

• Stabilize first, investigate after. In the moment, the priority is getting the system back to a safe state, via compensating changes if the original rollback path is no longer clean, not by forcing a rollback that is now riskier than staying and fixing forward. Root-cause work waits until stability is restored.
• Run the review blameless but specific. Start with a plain factual timeline (what changed, who was involved, what the alerts showed, what mitigation was tried and when) before any discussion of what should have happened differently. Starting with why someone skipped the step short-circuits the investigation into individual blame before the systemic contributors are even on the table.
• Separate the latent condition from the active slip. The person skipping the step is the active trigger; the latent conditions are what made skipping possible and unnoticed, an unclear or untested runbook, no automated enforcement of the required step, no alert that would have caught the incomplete rollback on its own. Fixing only the active trigger, retraining the person or writing a sterner policy, leaves the latent conditions in place for the next person under the same pressure.
• Make the fix structural, not procedural, wherever possible. A checklist that can be silently skipped is weaker than a deployment gate that mechanically requires the step to complete before the change is considered done, or an automated alert that detects an incomplete rollback on its own rather than depending on someone noticing.
• Assign every remediation a specific owner and a verification method, not just a due date. Updating the runbook is not done until someone has actually walked through it in a rehearsal and confirmed it works under pressure, not just that the document was edited.

Worked example

A team's deploy causes a regression, the documented rollback step gets skipped under time pressure, and the change stays live, extending the outage. Recovery: rather than forcing the now-risky rollback, the on-call team makes the current state safe first, a targeted fix or a feature-flag disable that does not require replaying the skipped step, and confirms user impact has stopped before anything else happens. The review afterward establishes the timeline first, then surfaces that the rollback step was skipped not out of carelessness but because the runbook described it in a way that was easy to misread under pressure, and there was no automated check that would have caught an incomplete rollback on its own. The fixes that come out of it are structural: the deployment tool is changed so the rollback step is enforced rather than optional, the pipeline will not mark the deploy as rolled back until the step's postcondition is actually verified, and a monitor is added that specifically detects a rollback initiated but not completed, rather than relying on the on-call engineer to notice. Each fix gets an owner and is verified with an actual rehearsal, a scheduled drill that exercises the new gate, before the review is considered closed, not just marked done in a tracker.

Trade-offs and pitfalls

Blameless framing can tip into avoiding accountability entirely if it is not paired with real, tracked remediation: no blame has to mean the process gets fixed, not that nothing changes. The opposite failure is over-correcting into heavy process, an approval gate added at every step, that slows every future deploy to prevent a low-frequency failure, which teams then find ways to route around under pressure, recreating the same latent condition in a new form. The third is closing the review once the runbook is updated without verifying the automated gate actually catches the failure mode in a drill: a fix that was never rehearsed is a hypothesis, not a confirmed fix.

Direct answer

With CPU trending 30% to 60% over six months, disk at 55% and growing roughly 40 GB a week, and P95 latency (the response time under which 95% of requests complete) up from 80 ms to 180 ms, the deciding question isn't "horizontal or vertical" in general, it's "which specific resource is actually driving the latency increase, and does that resource scale by adding boxes or by making one box bigger." CPU trending upward with rising latency points toward horizontal scaling if the workload is stateless; the disk growth trend is a separate, more urgent problem that needs its own answer regardless of which scaling path is chosen.

Structured elaboration

Decision indicators and thresholds:

• CPU utilization: sustained above roughly 70% average, or frequent spikes above 85%, favors horizontal scaling if load is CPU-bound and spread evenly across requests; a load that CPU-bound but genuinely bursty (short spikes, not sustained) is weaker evidence for adding permanent capacity of either kind.
• Memory pressure: swapping, out-of-memory (OOM) events, or sustained utilization above roughly 75% points toward vertical scaling (more RAM) or an application-level fix, since horizontal scaling doesn't help a single request that needs more memory than one instance has.
• Disk capacity growth: a clear growth trend needs a capacity projection (see the worked example) and, once the projection crosses a risk threshold, more storage now, independent of the CPU/latency decision; horizontal scaling only helps disk pressure if instances can share storage or offload to object storage.
• Latency root cause: profile whether the P95 increase correlates with CPU or memory contention (favors horizontal) versus I/O wait on disk (favors better storage, provisioned I/O capacity, or caching, which is a different lever than adding compute instances).
• Failure domain: a single node is a single point of failure regardless of how well-provisioned it is; horizontal scaling improves availability on its own merits, separate from the capacity question.

Risk factors:

• Statefulness. If the service holds session or request state on local disk or in memory, horizontal scaling requires externalizing that state first (or sticky routing as a stopgap), which is real engineering work, not a configuration change.
• Operational complexity. More instances means load-balancing, orchestration, and deployment-pipeline changes that a single larger machine doesn't need.
• Cost comparison. Compare the hourly cost of one larger machine against several smaller ones, including any per-core or per-instance licensing costs that can make vertical cheaper even when it's operationally worse.

Non-technical constraints:

• Licensing that's priced per core or per instance can make vertical scaling cheaper, or make running many small instances prohibitively expensive, independent of the technical merits.
• Operational capacity, meaning whether the team can actually run and monitor a multi-instance, load-balanced deployment, not just whether the architecture supports one.
• Compliance, such as data-residency or encryption requirements that constrain which storage or scaling options are viable at all.

Worked example

Disk exhaustion projection. The scenario states disk usage at 55% and growth of roughly 40 GB per week, but does not state the volume's total size, so a specific "weeks until full" figure can't be derived from the numbers given as-is. Making the missing input explicit as a stated assumption: assume a 1,000 GB (1 TB) volume, a common default cloud block-storage size.

$\text{Remaining capacity} = (1 - 0.55) \times 1{,}000\text{GB} = 450\text{GB}$
$\text{Weeks until full} = \frac{450\text{GB}}{40\text{GB/week}} \approx 11.25 \Rightarrow \approx 11 \text{ weeks}$

At roughly 11 weeks to exhaustion under that assumed volume size, the recommended action is to add capacity (resize the volume or move growing data to object storage) well before that point, both because provisioning takes lead time and because performance often degrades before a disk is literally full. The actual number of weeks depends entirely on the real volume size, which should be pulled from the infrastructure configuration rather than assumed, before this projection is used to schedule any real work.

Applying the CPU/latency indicator. CPU has doubled (30% to 60%) over six months while P95 latency has more than doubled (80 ms to 180 ms) over the same window; a latency increase that outpaces the CPU increase is a signal worth investigating on its own; it can mean the service is approaching a nonlinear point on its CPU-versus-latency curve (queueing effects tend to worsen faster than linearly as utilization climbs), which is itself an argument for adding capacity before CPU utilization reaches the 70-85% range where that nonlinearity typically bites hardest.

Trade-offs & pitfalls

• Don't let a single trending metric decide the whole answer. CPU, memory, disk, and latency are telling four different stories here; disk needs action on its own timeline regardless of what CPU says, and conflating the two into one decision risks solving the wrong problem first.
• A capacity projection built on an unstated assumption (like the volume size above) is only as good as that assumption. Always state it explicitly and replace it with the real number before using the projection to justify a purchase or a deadline.
• Licensing and operational capacity can override the "objectively better" technical answer. A team correctly diagnosing that horizontal scaling is the right long-term architecture can still be blocked by per-core licensing costs or a lack of operational readiness to run a fleet instead of one box.
• Vertical scaling on a stateful workload just delays the eventual horizontal refactor, if growth continues; treat a vertical resize under these conditions as buying time for the state-externalization work, not as a substitute for it.

Approach: convert to subset-sum target = S/2. Use DP boolean table dp[i][t] = whether using first i numbers we can reach sum t, then reconstruct one subset by backtracking. Because S ≤ 2000, a 2D DP is fine; we’ll show space-optimized 2D→1D for DP state and keep a parent table for reconstruction. Also discuss bitset optimization (O(n * S / word_size)) with faster constants but harder to reconstruct.

Python implementation (boolean DP with reconstruction):

def can_partition(nums):
    S = sum(nums)
    if S % 2: 
        return False, []
    target = S // 2
    n = len(nums)
    # dp[t] = whether sum t achievable; parent[i][t]=True if used nums[i-1]
    dp = [False] * (target + 1)
    dp[0] = True
    parent = [ [False]*(target+1) for _ in range(n) ]
    for i, val in enumerate(nums, start=1):
        # iterate descending to avoid reuse
        for t in range(target, val-1, -1):
            if not dp[t] and dp[t-val]:
                dp[t] = True
                parent[i-1][t] = True
    if not dp[target]:
        return False, []
    # reconstruct one subset
    res = []
    t = target
    for i in range(n-1, -1, -1):
        if parent[i][t]:
            res.append(nums[i])
            t -= nums[i]
    return True, res

Key points:

• Time: O(n * target) ≈ O(n * S). Space: O(target) for dp, plus O(n * target) for parent (needed for reconstruction).
• Bitset optimization: represent achievable sums as bitset; update with shift: bits |= bits << val. Time becomes O(n * (S / word_size)) with much smaller constants and O(S / word_size) memory. Reconstruction is possible by storing snapshots or using divide-and-conquer recovery but increases complexity or memory.
• Trade-offs: 1D DP + parent table is simple and easy to reconstruct but uses O(n*S) memory for parents. Bitset is fast and memory-efficient but requires extra work to reconstruct a subset (store checkpoints or run forward/backtracking with additional passes). Edge cases: empty array, single element, zeros in input.

Direct answer

A straightforward recursive flatten walks the nested structure, recursing into every sub-list and appending every non-list element directly to the result. It is correct and easy to read, but its recursion depth equals the input's NESTING depth, not its total element count, so an extremely deeply nested input (thousands of levels of [[[...]]]) can exceed the language's recursion limit and crash with a stack overflow, even though the total amount of data is tiny. An iterative version using an explicit stack does the identical traversal without ever growing the call stack, and handles arbitrary nesting depth safely.

Structured elaboration

The recursive approach

For each item in the input list: if it is itself a list, recursively flatten it and extend the result with what comes back; otherwise, append it directly. This mirrors the problem's own recursive structure (a nested list is either an element or a list of nested lists) almost exactly, which is why it reads so naturally, but that same one-to-one mirroring is exactly what ties its stack depth to the input's nesting depth.

Why recursion depth is the real concern here

Python's default recursion limit, retrievable via sys.getrecursionlimit(), is 1000. This limit exists to protect the underlying interpreter stack from being exhausted, which would crash the process outright rather than raising a catchable Python exception; the recursion limit is what turns that hard crash into a catchable RecursionError instead. A list nested 1500 levels deep, [[[...[1]...]]], has only a single element, but flattening it recursively requires 1500 nested calls, comfortably past the default limit, so the recursive version raises RecursionError on an input that is trivially small in terms of total data.

The iterative alternative with an explicit stack

Replace the call stack with an explicit Python list acting as a stack, where each stack entry is an ITERATOR over one level of nesting rather than a raw list. Repeatedly pull the next item from the iterator at the top of the stack: if it is a list, push an iterator over IT onto the stack and continue; if it is a plain element, append it to the result; if the top iterator is exhausted, pop it off and continue with whatever is now on top. This performs the exact same traversal as the recursive version, but the "depth" it tracks lives on the heap (as entries in the stack list), bounded only by available memory, not by the interpreter's fixed recursion limit.

Worked example

import sys

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

def flatten_iterative(nested):
    result = []
    stack = [iter(nested)]
    while stack:
        top = stack[-1]
        try:
            item = next(top)
        except StopIteration:
            stack.pop()
            continue
        if isinstance(item, list):
            stack.append(iter(item))
        else:
            result.append(item)
    return result

example = [1, [2, [3, 4], 5], 6]
print(flatten(example))
print(flatten_iterative(example))

depth = sys.getrecursionlimit() + 500
deeply_nested = 1
for _ in range(depth):
    deeply_nested = [deeply_nested]

try:
    flatten(deeply_nested)
    print("recursive: no error")
except RecursionError:
    print("recursive: RecursionError")

print("iterative:", flatten_iterative(deeply_nested))

Output:

[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
recursive: RecursionError
iterative: [1]

Both implementations agree exactly on the question's own example, [1, [2, [3, 4], 5], 6] -> [1, 2, 3, 4, 5, 6]. The recursion-depth concern is demonstrated directly, not just asserted: building a list nested 500 levels past the default recursion limit and flattening it recursively does raise RecursionError (confirmed against Python's default limit of 1000), while the iterative version flattens the exact same deeply nested input to [1] without any error.

Trade-offs and pitfalls

Raising sys.setrecursionlimit() to a larger number is a tempting quick fix, but it does not remove the underlying risk, it only moves the crash point further out, and pushing it too far can crash the whole PROCESS with a C-level stack overflow instead of a catchable Python exception, since the interpreter's own limit exists specifically to stay within the real stack memory available. The iterative version is the more ROBUST general answer for this reason: it trades a small amount of code complexity, managing an explicit stack of iterators rather than relying on the language's call stack, for a traversal that cannot fail on input shape alone, only on genuinely running out of memory. Also worth naming: neither version currently guards against a value that is directly self-referential (a list containing itself), which would recurse or loop forever regardless of which approach is used; that is a distinct edge case from nesting depth and would need explicit cycle detection if the input could ever be adversarial or attacker-controlled rather than merely deeply nested.