Amazon SDE III (Senior Software Engineer) Interview Preparation Guide

Garbage collection (GC) is the JVM automatically reclaiming memory for objects no longer referenced, and a stop-the-world pause is a phase where some GC work briefly halts all application threads, adding directly to request latency during that pause. An SLO (service level objective) like "p99 under 200ms" is exactly the kind of target a long GC pause can blow through in one shot.

How cache size and churn drive GC pressure

A large in-process cache, millions of entries in Caffeine, gives the GC a much bigger live set, objects it must repeatedly scan and NOT collect on every cycle, since the cache still references them, and this alone lengthens cycles even with nothing being evicted. Churn, a high eviction and insertion rate, makes it worse: every evicted entry becomes garbage the GC then has to reclaim, so a cache with high turnover (short TTL, small max size relative to traffic) generates a steady stream of short-lived garbage on top of an already-large long-lived heap, close to a GC's worst case, a mix of a big long-lived footprint and heavy short-lived churn.

JVM and GC tuning

Use a low-pause-focused collector, G1GC is the modern default and a reasonable starting point; ZGC or Shenandoah trade some throughput for much shorter target pause times and are worth evaluating specifically once GC pause is confirmed to be the latency bottleneck. Set an explicit pause-time goal with G1 (-XX:MaxGCPauseMillis=50) rather than only sizing the heap and hoping. Size the heap deliberately, an oversized heap means longer, though less frequent, cycles when they do happen, an undersized heap means more frequent cycles, this is a real sizing exercise, not just "give it more RAM." Monitor GC logs for pause duration and frequency trends over time, correlated against your cache size metrics, to actually confirm the cache is the driver rather than assuming it.

Off-heap and serialization alternatives

Move the cache's bulk data off the regular GC-managed heap, an off-heap store paired with Caffeine, or something like Chronicle Map, or a Redis sidecar instead of a very large in-process cache. Off-heap memory is not scanned by the GC at all, which removes the big-live-set problem directly, at the cost of needing serialization on every access, objects have to be marshaled into and out of the off-heap buffer, a real CPU trade-off worth making only once GC pause is demonstrably the dominant cost, confirmed from the GC logs, not assumed.

The mirror-image effect: a GC pause causing a miss storm

A long stop-the-world pause freezes request processing, so requests queue up during the pause and then all get processed in a burst right after it ends. If a meaningful share of those queued requests are for keys that were about to expire or were not yet cached, the pause effectively synchronizes a burst of cache misses immediately after it ends, which looks like an unrelated miss storm but is actually caused by the GC pause, not a coincidence. To catch this, correlate GC pause timestamps directly against the cache miss-rate time series, not just latency, a miss-rate spike that reliably follows GC pause events by roughly the pause duration is the fingerprint. Mitigate with the same pause-time tuning above, and by adding TTL jitter so expirations are not already clustered and ready to compound with a GC-caused processing backlog.

Direct answer. Give each filterable field its own query parameter with an explicit, documented syntax (a range as min_price/max_price, a boolean as a plain true/false flag, an enum as a comma-separated allow-list, free text as a dedicated q parameter), and put sorting in a single sort parameter that names fields with an optional leading minus for descending order (sort=-created_at,price), rather than inventing a generic query language the client has to learn.

Concrete contract.

GET /products?category=electronics&min_price=20&max_price=200&in_stock=true&sort=-created_at,price&q=wireless

• category: exact-match enum, comma-separated for multiple values (category=electronics,books)
• min_price / max_price: a range filter as two separate parameters, not one combined string the server has to parse
• in_stock: a plain boolean flag
• sort: a comma-separated list of field names, a leading - meaning descending; the FIRST field is the primary sort key, later ones are tiebreakers
• q: a single free-text parameter for full-text search, kept separate from the structured filters above so the two can be combined without ambiguity about which is which

Why this stays discoverable and unambiguous. Each parameter maps to exactly one concept and one value shape; a client (or someone reading a URL in a support ticket) can tell what the request means without needing your API's full documentation open. The alternative, a single opaque filter=... string encoding a small query language, is more powerful but requires the client to learn a syntax; reserve that only if you genuinely need boolean combinations (AND/OR/NOT across arbitrary fields) that a flat parameter list cannot express, which most product-list endpoints do not.

Guarding against expensive ad-hoc queries. Three concrete guardrails: (1) a hard cap on how many fields can appear in sort at once (say, three), since each additional sort key can force the database into a more expensive multi-column sort if there is no index that matches the exact combination; (2) an explicit ALLOW-LIST of filterable and sortable fields, rejecting (400) any parameter name not on the list, rather than silently accepting and ignoring an unsupported one, which hides a client bug; (3) for the free-text q parameter specifically, route it to a purpose-built search index (not a live LIKE '%term%' scan of the primary table), since unindexed free-text search is exactly the kind of client-constructed query that degrades everyone else's performance the moment the dataset is large.

Trade-offs and pitfalls. The most common mistake is exposing every column in the underlying table as a filterable parameter "for flexibility", which both makes the API's real contract unclear (nothing distinguishes an intentionally-supported filter from an accidentally-exposed internal column) and means a client can construct a filter/sort combination with no supporting index, turning an innocent-looking request into a full table scan.

Direct answer
"Unclear requirements" is a real cause sometimes and a convenient explanation other times, so the first job is figuring out which, using evidence rather than taking the explanation at face value. Look at the pattern across several instances, not just the latest miss, separate estimation problems from execution problems from actual requirement gaps, then fix the specific mechanism, not the person's attitude.

Diagnose using the pattern, not the excuse

• Pull several recent examples, not just the most recent miss. Was the requirement genuinely ambiguous every time, or does "unclear requirements" get invoked even when the ticket had clear acceptance criteria? The former is a process problem; the latter is a signal something else is going on (confidence, avoidance, poor estimation).
• Look for where in the workflow it breaks down: did they ask clarifying questions before starting and get bad answers, or did they not ask and guess? Did the requirement change mid-task without being re-scoped? Did they commit to something they didn't actually understand, to avoid looking behind?

Separate the possible root causes

• Genuine ambiguity: the requirement really was underspecified and nobody caught it before work started.
• Estimation or planning gap: the requirement was clear but the person didn't break it down enough to notice the ambiguous parts until they hit them.
• Avoidance: asking clarifying questions feels risky (looks like not knowing), so they guess and then have a ready explanation when it goes wrong.
• Skill gap under a different name: they may not yet have the judgment to know what "clear enough to start" looks like.

Fix the mechanism that matches the cause

• Genuine ambiguity: introduce a lightweight definition-of-ready check before work starts, owned jointly, not something you police alone.
• Estimation or planning: practice breaking a ticket into sub-tasks together and flag the ambiguous piece explicitly before committing to a date.
• Avoidance: make asking clarifying questions cheap and normal, model it yourself, and separate "I don't know yet" from an evaluation of competence.
• Skill gap: pair on a couple of tickets so they see what "clear enough" actually looks like in practice, rather than being told about it abstractly.

Worked example
A mentee on a team I supported kept missing sprint commitments, and the stated reason was always some version of unclear requirements. Looking at the last four tickets together, not just the most recent one, a pattern showed up: on three of the four, the acceptance criteria were actually written clearly, but the mentee hadn't asked any clarifying questions before starting, then hit an edge case mid-task and treated the whole ticket as ambiguous from the start. On the fourth, the ticket genuinely was underspecified.

The fix wasn't "communicate more clearly" in the abstract. It was two things: a short pre-work check where we'd both look at a ticket before it was picked up and flag anything genuinely unclear (catching the real ambiguity case), and a habit of the mentee sending one clarifying question per ticket before starting, even a small one, to break the avoidance pattern. The signal it was working wasn't a single metric; it was that "unclear requirements" stopped being the explanation for misses, because the real ambiguity was being caught earlier and the avoidance pattern had a lower-stakes outlet.

Trade-offs and pitfalls

• Taking "unclear requirements" at face value every time lets a deeper issue (avoidance, skill gap) hide behind a plausible-sounding excuse indefinitely.
• Assuming it's never true is just as wrong; requirements genuinely are underspecified sometimes, and treating every instance as a character problem erodes trust.
• The fix has to match the actual cause. A definition-of-ready checklist won't help someone avoiding asking questions, and coaching someone to "just ask more" won't help if the requirements really were bad.

Direct answer

A risk register earns its keep only if it changes a real decision at least once. Otherwise it is a document nobody reads. For each risk you track what it is, its likelihood, its impact, who owns watching and mitigating it, what specific signal would trigger it moving from "watching" to "active," its current status, and a mitigation or contingency ready before you need it. Organizing this as risks, assumptions, issues, and dependencies together, sometimes called a RAID log, keeps it from quietly drifting into just another to-do list.

Structured elaboration

The fields, and why each one earns its place: risk description, written specifically ("the vendor's API might miss its date," not "external dependencies"); likelihood and impact, a plain high, medium, or low scale is enough, more precision than that is theater; owner, a named person watching this specific risk, not a team; trigger, the exact signal that means the risk has moved from possible to actually happening, for example "the vendor has not confirmed a date by a specific checkpoint"; mitigation, what reduces the likelihood or impact before it happens; contingency, what you do if it happens anyway; and status, reviewed on a cadence rather than logged once and forgotten.

Risks get identified from more than a single kickoff brainstorm: pull from what has derailed similar programs before, ask each workstream owner what actually worries them, and look hardest at anything outside your direct control, a vendor, another team's roadmap, unproven technology, since teams focused on their own execution systematically underweight exactly those.

Prioritization is what decides which risks "make the cut" for active tracking: plot likelihood against impact. Anything low on both gets acknowledged once and left alone, since tracking everything turns the register into noise nobody reads closely. Anything high on either axis gets a named owner and a mitigation in place before the program passes its next milestone.

Worked example

A multi-quarter program migrating a batch reporting pipeline to a new scheduler carried this entry: "the new scheduler vendor's managed rollout might slip past our cutover date." Likelihood medium, impact high, since it would delay three downstream teams. Owner: the program's technical lead. Trigger: "the vendor has not confirmed general availability four weeks before our planned cutover date." Mitigation: keep the old scheduler running in parallel through the transition window. Contingency: delay cutover by four weeks and absorb the cost of running both systems in parallel during that stretch.

At the four-week mark before the planned cutover, the vendor had in fact not confirmed general availability, tripping the trigger exactly as defined. Because the risk already had a name, a defined trigger, and a pre-agreed contingency, the response at the next steering-committee review was not a scramble: the program lead requested the four extra weeks of budget that had already been scoped for exactly this scenario. The request was approved in that same meeting, because the cost and the rationale had been laid out in the register weeks earlier rather than argued from scratch under pressure, and cutover moved by four weeks instead of either rushing an unready vendor or missing the original date with no plan at all.

Trade-offs and pitfalls

The most common failure is a register built once at kickoff and never revisited, so it becomes historical trivia instead of a live decision tool. A second is tracking too many low-likelihood, low-impact items, which trains reviewers to skim past the whole document and miss the one entry that actually matters. A third is a risk assigned to a team rather than a person, so when it triggers, nobody specifically notices because everyone assumes someone else is watching it.

Strength 1 — Clean, maintainable code: I consistently write modular, well-documented code with clear naming, unit tests, and small, focused PRs. This reduces bugs and speeds onboarding for teammates.

Strength 2 — Systematic debugging and root-cause analysis: I use logging, profiling, and binary search in commits to isolate defects quickly; I pair with others to transfer debugging heuristics.

Strength 3 — Cross-functional communication: I translate technical trade-offs into product impacts, run effective design reviews, and align engineering work with PM and design priorities.

Area for development — Advanced distributed systems design (consensus, partition tolerance, high-throughput scaling).

3-month concrete plan (weekly):

• Weeks 1–4: Foundations
  • Weekly: Read and summarize 1 chapter of “Designing Data-Intensive Applications” + implement small exercises (replication, sharding) in Python.
  • Resource: DDIA book, Stanford CS244 lecture videos.
• Weeks 5–8: Practical labs
  • Weekly: Build/extend a toy service (gossip-based membership, leader election) + write tests; follow blog posts (e.g., AWS Architecture).
  • Pair once per week with a senior engineer for design feedback.
• Weeks 9–12: Advanced topics & review
  • Weekly: Implement a simple Paxos/Raft demo or use open-source Raft library to add leader failover; conduct load tests and improve throughput.
  • Prepare a 20-minute tech talk for the team in week 12.

Validation:

• Measurable: Completed exercises, GitHub repo with incremental commits and tests, automated load-test results showing improvements, and positive peer feedback from the tech talk and pairing sessions.

Direct answer

The 0/1 knapsack DP state is dp[c] meaning "maximum total value achievable using a budget of exactly (or up to) c," updated per item by dp[c] = max(dp[c], dp[c - weight] + value), iterating capacities in descending order so each item is only used once. If the question changes from "maximize value" to "is some exact target sum achievable at all," the state becomes a boolean reachable[s] instead of a running maximum, using the identical recurrence shape (reachable[s] = reachable[s] or reachable[s - weight]) but tracking reachability instead of an optimum. This exact-sum variant is the same shape as the well-known Partition Equal Subset Sum problem, which asks whether a set of numbers can be split into two subsets with equal totals.

Structured elaboration

Value-maximization DP.

def knapsack_max_value(weights, values, capacity):
    """
    0/1 knapsack: maximum total value without exceeding capacity, each item
    at most once. dp[c] = best value achievable with budget c.
    Time O(n * capacity), Space O(capacity) (rolling 1D array).
    """
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):   # descending: each item used at most once
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

Feasibility (exact-sum) DP. Change the table's meaning from "best value so far" to "is this sum reachable," and change the update from a max to a boolean OR:

def subset_sum_feasible(weights, target):
    """
    Can some subset of weights sum to exactly target?
    reachable[s] = True if sum s is achievable using a subset of items seen
    so far. Same 0/1 recurrence as knapsack, but the DP value is a boolean
    "reachable" flag instead of a running maximum.
    Time O(n * target), Space O(target).
    """
    reachable = [False] * (target + 1)
    reachable[0] = True
    for w in weights:
        for s in range(target, w - 1, -1):
            if reachable[s - w]:
                reachable[s] = True
    return reachable[target]

Partition Equal Subset Sum is exactly this feasibility check with target set to half the total sum of the input numbers (if the total is odd, an equal split is impossible immediately, no DP needed). The same feasibility shape also applies to budget-constrained subset-selection outside pure combinatorics: for example, choosing dashboard KPIs or metrics under a display-cost budget, where each metric has a fixed "screen cost" and you want to know whether some subset exactly fills an allotted display budget (or, with the max-value version, which subset of metrics maximizes total business value within that budget).

Worked example

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_max_value(weights, values, 5))

Output: 7 (taking the weight-2/value-3 and weight-3/value-4 items exactly fills the capacity-5 budget for total value 7; no other combination of these items reaches higher value within capacity 5).

nums = [1, 5, 11, 5]
total = sum(nums)
print(total, total % 2 == 0, subset_sum_feasible(nums, total // 2) if total % 2 == 0 else None)

Output: 22 True True. The total is 22 (even), so an equal split needs a subset summing to 11; subset_sum_feasible confirms 11 is reachable (via 5 + 5 + 1), so [1, 5, 11, 5] can be partitioned into two equal-sum halves.

Trade-offs & pitfalls

Key points

• Greedy selection by value-to-weight ratio is optimal for the fractional knapsack (where you can take a fraction of an item) but is not guaranteed optimal for 0/1 knapsack, since taking a high-ratio item can leave awkward leftover capacity that a different combination would have used better.
• The feasibility DP is strictly cheaper to reason about than the value-maximization DP (booleans instead of running maxima), but it answers a narrower question: it tells you whether a target is reachable, not which subset achieves it, unless you also track parent pointers or reconstruct the choice by scanning backward through the table.
• Both DP variants are pseudo-polynomial: their cost scales with the numeric capacity or target value, not just the number of items, so a very large capacity or target (in the millions) can make the DP impractical even though the item count is small; that is where a greedy approximation or a meet-in-the-middle exact method becomes attractive.

Complexity

• Value-maximization: time $O(n \cdot W)$, space $O(W)$, where n is the item count and W is the capacity.
• Feasibility: time $O(n \cdot T)$, space $O(T)$, where T is the target sum.

Edge cases

• Target or capacity of 0: dp[0]/reachable[0] are the trivial base cases (empty selection), both handled directly.
• An item heavier than the remaining capacity: naturally excluded by the descending-range guard (w - 1 lower bound), never considered for smaller capacities.
• Odd total sum in the partition-equal-subset-sum framing: no DP needed at all, an equal-value split is impossible by simple arithmetic before touching the table.

A good harness has four jobs: make the bad interleaving likely, check an invariant so a bad run is detected, record the seed so a failure can be repeated, and optionally control the schedule so a seed replays the same interleaving. I would build it in layers, because each layer costs more and each catches something the previous one cannot. Layers 1 to 3 need no special tooling; layer 4 is the specialised one, worth its cost only where the interleaving space is small enough to control.

Terms used below: a barrier is a starting gate that holds every thread until all have arrived, then lets them go together. CPU pinning fixes a thread to one core, which changes which threads truly run at the same time. ThreadSanitizer is a compiler-added checker that reports data races (unsynchronised accesses to the same memory from two threads). A yield point is a place in the code where the running thread offers to stop so another may run. A cooperative scheduler only switches threads at those points. To bisect is to halve a search range repeatedly (fewer threads, fewer operations, an earlier code version) to find the smallest case that still fails.

Layers of perturbation

1. Many threads and many runs from a common start. Release all threads from a barrier together, run thousands of short iterations (each with a fresh object), and run on a loaded machine. Cheap, but timing-dependent.
2. Inject delays at suspicious points. Random sleep or yield between the steps of an operation widens the race window.
3. Vary the environment: thread count above and below the core count, CPU pinning, background CPU hogs, a debug build, an optimised build, and sanitiser builds (ThreadSanitizer finds data races but will not find logic errors).
4. Control the scheduler (the deterministic case). Run exactly one thread at a time, and at each yield point let a seeded random number generator choose who runs next. The same seed gives the same interleaving, so a failure becomes a number you can rerun, bisect and put in a regression test.

Checking: the invariant is the oracle

A race rarely crashes. The invariant is a property that must be true after every correct run, and checking it is the oracle: the part of the test that decides pass or fail. Define what must always hold (here: balance plus successful withdrawals equals the starting amount) and assert it after each run. Without this the harness reports "pass" on corrupted data.

The harness, runnable

The bug under test splits a check and an update into two critical sections (an atomicity violation: no data race, so a data-race detector stays silent). The three modes are plain, random-sleep perturbation, and the seeded scheduler:

// Stress harness: plain run, random-perturbation run, and a seeded cooperative scheduler.
// Bug under test: an atomicity violation. Each lock section is correct (no data race),
// but "read balance" and "write balance" are separate critical sections.
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <cstdint>
#include <cstdio>
#include <mutex>
#include <random>
#include <thread>
#include <vector>
using namespace std;

enum Mode { PLAIN, CHAOS, CONTROLLED };
constexpr int THREADS = 2, OPS = 2, START = 4;

struct Sched {                       // exactly one thread runs between yield points
    mutex m; condition_variable cv; int cur = 0; vector<bool> alive; mt19937_64 rng; uint64_t hash = 14695981039346656037ULL; vector<int> picks;   // FNV-1a 64-bit offset basis; picks: the order of turns
    explicit Sched(uint64_t seed) : alive(THREADS, true), rng(seed) { pick(); }
    void pick() { vector<int> c; for (int i = 0; i < THREADS; ++i) if (alive[i]) c.push_back(i);
                  if (c.empty()) return;
                  cur = c[rng() % c.size()]; picks.push_back(cur); hash = (hash ^ (uint64_t)cur) * 1099511628211ULL; }
    void begin(int me) { unique_lock l(m); cv.wait(l, [&] { return cur == me; }); }
    void yield_point(int me) { unique_lock l(m); pick(); cv.notify_all(); cv.wait(l, [&] { return cur == me; }); }
    void finish(int me) { unique_lock l(m); alive[me] = false; pick(); cv.notify_all(); }
};

struct Ctx { Mode mode; Sched* s; mt19937 rng; };
void point(Ctx& c, int me) {         // a yield point: where an interleaving may change
    if (c.mode == CONTROLLED) c.s->yield_point(me);
    else if (c.mode == CHAOS && c.rng() % 4 == 0) this_thread::sleep_for(chrono::microseconds(c.rng() % 50));
}

struct Account { mutex m; int balance = START; int ok = 0; };

bool withdraw_buggy(Account& a, Ctx& c, int me) {
    int b; { lock_guard g(a.m); b = a.balance; }
    point(c, me);                                    // gap between check and act
    if (b < 1) return false;
    { lock_guard g(a.m); a.balance = b - 1; ++a.ok; }
    return true;
}
bool withdraw_fixed(Account& a, Ctx&, int) {
    lock_guard g(a.m);                               // check and act in one critical section
    if (a.balance < 1) return false;
    --a.balance; ++a.ok; return true;
}

struct Result { bool bad; uint64_t hash; int balance, ok; vector<int> picks; };
Result run_once(bool fixed, Mode mode, uint64_t seed) {
    Account acc; Sched sched(seed); vector<thread> ts;
    atomic<int> go{0};
    for (int t = 0; t < THREADS; ++t) ts.emplace_back([&, t] {
        Ctx c{mode, &sched, mt19937(seed * 31 + t)};
        if (mode == CONTROLLED) sched.begin(t); else { go++; while (go < THREADS) {} }
        for (int i = 0; i < OPS; ++i) { (fixed ? withdraw_fixed : withdraw_buggy)(acc, c, t); }
        if (mode == CONTROLLED) sched.finish(t);
    });
    for (auto& t : ts) t.join();
    bool bad = acc.balance + acc.ok != START || acc.balance < 0;
    return {bad, sched.hash, acc.balance, acc.ok, sched.picks};
}

int main() {
    const char* mn[] = {"plain", "chaos (random sleeps)", "controlled (seeded)"};
    const int RUNS = 300;
    for (bool fixed : {false, true})
        for (Mode m : {PLAIN, CHAOS, CONTROLLED}) {
            int fails = 0; long first = -1;
            for (int s = 0; s < RUNS; ++s) { if (run_once(fixed, m, s).bad) { ++fails; if (first < 0) first = s; } }
            printf("%-6s %-22s %3d of %d runs broke the invariant (first failing seed: %ld)\n",
                   fixed ? "fixed" : "buggy", mn[m], fails, RUNS, first);
        }
    // Reproduce: the same seed gives the same interleaving and the same outcome.
    for (int s = 0; s < RUNS; ++s) {
        Result a = run_once(false, CONTROLLED, s);
        if (!a.bad) continue;
        Result b = run_once(false, CONTROLLED, s), c = run_once(false, CONTROLLED, s);
        printf("seed %d x3: schedule hash %016llx %016llx %016llx, balance %d %d %d, successful withdrawals %d %d %d (balance + withdrawals should be %d)\n",
               s, (unsigned long long)a.hash, (unsigned long long)b.hash, (unsigned long long)c.hash,
               a.balance, b.balance, c.balance, a.ok, b.ok, c.ok, START);
        break;
    }
    // The picks behind two seeds: the schedule is just this list.
    for (int s = 0; s < 2; ++s) {
        Result r = run_once(false, CONTROLLED, s);
        printf("seed %d picks:", s);
        for (int d : r.picks) printf(" T%d", d);
        printf(" -> balance %d, successful withdrawals %d, invariant %s\n", r.balance, r.ok, r.bad ? "broken" : "holds");
    }
}

Built with g++ -O2 -std=c++20 -Wall -Wextra -pthread stress.cpp -o stress && ./stress in the gcc:14 image (GCC 14.4, aarch64). P, C and the plain/chaos first failing seeds S are nondeterministic and change from run to run; every other line is deterministic and was identical in every run:

buggy  plain                    P of 300 runs broke the invariant (first failing seed: S)
buggy  chaos (random sleeps)    C of 300 runs broke the invariant (first failing seed: S)
buggy  controlled (seeded)    223 of 300 runs broke the invariant (first failing seed: 0)
fixed  plain                    0 of 300 runs broke the invariant (first failing seed: -1)
fixed  chaos (random sleeps)    0 of 300 runs broke the invariant (first failing seed: -1)
fixed  controlled (seeded)      0 of 300 runs broke the invariant (first failing seed: -1)
seed 0 x3: schedule hash 6b30c4d80283c1b8 6b30c4d80283c1b8 6b30c4d80283c1b8, balance 2 2 2, successful withdrawals 4 4 4 (balance + withdrawals should be 4)
seed 0 picks: T0 T1 T1 T0 T0 T1 -> balance 2, successful withdrawals 4, invariant broken
seed 1 picks: T0 T0 T0 T1 T1 T1 -> balance 0, successful withdrawals 4, invariant holds

How to read it: the schedule hash is a fingerprint of the scheduler's choices. Every time the seeded scheduler picks which thread runs next (the pick function), it folds that thread's number into a running hash (FNV-1a: xor in the thread number, then multiply). Two runs whose picks were the same sequence end with the same hash, so equal hashes tell you the same order of thread turns was replayed (a different order would, with overwhelming probability, give a different hash). The spin barrier line go++; while (go < THREADS) {} has each thread add one to a shared counter and loop until both threads have arrived, so the plain and chaos modes start together. In controlled mode the barrier is replaced by sched.begin(t), which makes each thread wait until the scheduler says it is that thread's turn.

How a seed becomes an interleaving (the last two lines of the output print the pick sequence for seeds 0 and 1): pick is called once at the start, once at every yield point, and once when the first thread finishes, six times in all, and each call chooses the thread that runs next. Seed 0 gives T0 T1 T1 T0 T0 T1: T0 reads the balance 4 and yields; T1 reads 4 too and yields back to itself, writes 3, reads 3 for its second try and yields; T0 resumes and writes 4 - 1 = 3 from its stale read (a lost update), reads 3, yields, is picked again, writes 2 and finishes; T1 resumes with its stale read of 3 and writes 2. Four withdrawals succeeded, the balance is 2 and should be 0: the invariant breaks. Seed 1 gives T0 T0 T0 T1 T1 T1: T0 runs both withdrawals before T1 starts, so nothing interleaves, the balance ends at 0 with 4 withdrawals, and the invariant holds. A seed fails only when its picks hand the CPU to the other thread between a read and the matching write.

What this shows, from repeated runs of the program (the table above shows one run):

• Plain is timing-dependent, and its rate depends on the environment. On the test host the plain count was usually small but varied a lot from run to run, and under ThreadSanitizer's slowdown it was far higher. The same bug looks rare or common depending on the machine and build, which is why a green plain run proves little.
• Perturbation raises the rate over plain: random sleeps put the failure in nearly every one of the 300 runs on the test host, where plain managed a small fraction of that. Chaos is still timing-dependent, so on another host or under other load its count can differ.
• Controlled mode is repeatable. It fails in 223 of 300 rather than 300 of 300 because each seed picks one random order, and some orders (like seed 1 above) never put another thread between a thread's read and write; chaos mode sleeps inside that gap, so it hits more often. Controlled mode's count is deterministic: it was 223 on every run, and seed 0 produced the identical schedule hash and outcome three times. A failing seed is a reproducer.
• The fixed version (check and update under one lock) passes all three modes, the same harness that caught the bug. The controlled-mode pass is the weakest of the three: the fixed code has no yield point inside its lock (yielding while holding the lock would deadlock a one-thread-at-a-time scheduler), so the scheduler never gets a chance to interleave it. The plain and chaos passes carry the evidence. A ThreadSanitizer build of this program gave no warnings, which is why the invariant check carries the weight.

Making failures reproducible

• Log the seed and the thread count in every failure message, and rerun the seed in controlled mode.
• Shrink: reduce threads and operations while the seed still fails, until the schedule is a handful of steps.
• Keep the failing seeds as permanent regression tests.

Limits, and my recommendation

The controlled scheduler only perturbs at the yield points you place, and the yield point calls must be in the code under test (or in a wrapper around the lock). It cannot expose a race between plain memory accesses you did not instrument. I would run layers 1 to 3 in CI on every change (cheap, probabilistic), a sanitiser job for data races, and layer 4 for the components where an invariant can be stated and the interleaving space is small.

Direct answer

Recommend a managed cloud relational database as the default for a genuinely transactional application, and use its autoscaling or serverless compute tier, not a switch to NoSQL, to absorb unpredictable traffic, unless the actual access pattern (not just the traffic shape) is key-value or document-shaped. "Unpredictable traffic" is a billing and capacity question; it is a different axis from "what consistency guarantees does this data need," and the two get conflated more often than they should.

Structured elaboration

A comparison table built for a proposal has to survive being read on its own, without the surrounding argument:

Worked example

Take an app with a baseline of 50 requests a second that spikes to roughly 2,000 requests a second during flash sales a few times a month. A traditionally provisioned relational tier sized for the spike sits mostly idle the rest of the month, an expensive way to buy headroom used a few hours a month; sized for the baseline, it falls over during the spike. A serverless or autoscaling relational tier removes that trade-off by scaling compute up for the spike and back down after, billed closer to actual usage, while keeping the same transactional guarantees the checkout flow (an inventory decrement that must not double-sell the same item) needs. Moving to NoSQL instead would solve the traffic-shape problem just as well, but only by also giving up the multi-row transaction the checkout flow depends on, which is a bigger change than the stated problem, unpredictable traffic, actually calls for.

Trade-offs & pitfalls

The most common bad move here is chasing "unpredictable traffic" straight into a data-model change, when the actual requirement is a multi-row transactional consistency the application genuinely needs. Many managed relational services now offer serverless or autoscaling compute tiers specifically to absorb spiky traffic without abandoning ACID, which is usually the better fix for a transactional app with unpredictable load than switching data models entirely. The reverse mistake also happens: defaulting to relational out of habit for an access pattern that really is "fetch by key" with no cross-item transaction ever required, in which case a NoSQL store's operational simplicity and native burst tolerance are the honestly better fit.

Direct answer
A compact but effective test suite for divide(a, b) needs three cases targeting distinct failure/behavior classes: division by zero (the documented exception path), very large integers (numeric-precision behavior when the result is a float), and negative inputs (sign-handling correctness across all three sign combinations).

Structured elaboration and worked example (executed; the original draft's if/raise/try bodies were flattened to a single indent level and the three def test_...: lines were also missing (), an unconditional SyntaxError that never ran, fixed below)

def divide(a: int, b: int) -> float:
    if b == 0:
        raise ZeroDivisionError("division by zero")
    return a / b

def test_division_by_zero():
    try:
        divide(10, 0)
        assert False, "should have raised"
    except ZeroDivisionError:
        pass

def test_very_large_integers():
    a, b = 10**18, 3
    result = divide(a, b)
    assert abs(result - a/b) < 1e-6

def test_negative_inputs():
    assert divide(-10, 2) == -5.0
    assert divide(10, -2) == -5.0
    assert divide(-10, -2) == 5.0

Running this: ALL divide TESTS PASSED.

Rationale for each test

• test_division_by_zero: pins down the DOCUMENTED contract (raise ZeroDivisionError, not return inf, nan, or crash with a different exception type); this matters because Python's native / operator on ints already raises ZeroDivisionError for integer division by zero, so this test is really confirming the function doesn't ADD a try/except that swallows or converts that exception into something else.
• test_very_large_integers: 10**18 is well beyond what a 64-bit float can represent exactly (float has about 15-17 significant decimal digits of precision, and 10**18 has 19 digits), so the test deliberately uses an approximate comparison (abs(result - a/b) < 1e-6) rather than exact equality, because exact equality would be testing a precision guarantee the function's own float return type cannot actually provide; the test's real purpose is confirming the function doesn't crash or produce a WILDLY wrong result (e.g. from an integer-overflow bug in a hypothetical alternate implementation), not asserting bit-exact precision.
• test_negative_inputs: covers all three sign combinations (negative/positive, positive/negative, negative/negative) specifically because a naive implementation using integer division (//) instead of true division (/) can behave inconsistently for negative operands in some languages (Python's // floors toward negative infinity, which is a real, distinct trap from truncating division); asserting all three combinations against /-based expected values confirms the function is using true division consistently, not accidentally mixing in floor-division semantics anywhere.

Trade-offs & pitfalls
A test suite that only checks divide(10, 0) raises SOME exception, without asserting the SPECIFIC exception type (ZeroDivisionError), would still pass against a buggy implementation that raises a generic Exception or a misleading TypeError, silently breaking any caller that specifically catches ZeroDivisionError; asserting the exact exception type, as done above, is what makes this a meaningful contract test rather than a vague 'it errors somehow' check.

Direct answer. Each of these patterns replaces a specific structural smell with an object that owns the varying behavior: Factory replaces scattered new/construction logic with one place that knows how to build the right thing; Strategy replaces a growing conditional with a swappable, self-contained behavior object; Adapter wraps an incompatible interface so callers don't have to special-case it.

Factory: fixing scattered, duplicated construction logic

# Before: construction logic (which concrete model to instantiate) repeated at every call site
if model_type == "linear": model = LinearModel(config)
elif model_type == "tree": model = TreeModel(config)

# After: one place owns the decision
class ModelFactory:
    _registry = {"linear": LinearModel, "tree": TreeModel}
    @classmethod
    def create(cls, model_type, config):
        return cls._registry[model_type](config)

Fixes: duplicated/scattered construction logic (a form of shotgun surgery -- adding a new model type meant editing every call site before; now it's one registry entry).

Strategy: fixing a conditional that keeps growing

class DiscountStrategy:
    def apply(self, total: float) -> float: raise NotImplementedError

class BulkDiscount(DiscountStrategy):
    def apply(self, total): return total * 0.9 if total > 100 else total

class LoyaltyDiscount(DiscountStrategy):
    def apply(self, total): return total * 0.95

def checkout(total, strategy: DiscountStrategy):
    return strategy.apply(total)

Fixes: the exact if/elif-growth problem covered earlier (replace-conditional-with-polymorphism) -- adding a new discount type means a new DiscountStrategy subclass, not editing checkout.

Adapter: fixing an incompatible third-party interface

class LegacyPaymentGateway:
    def do_charge(self, amount_str: str) -> dict: ...

class PaymentGatewayAdapter:
    """Adapts the legacy string/dict interface to the typed interface new code expects."""
    def __init__(self, legacy: LegacyPaymentGateway): self._legacy = legacy
    def charge(self, amount_cents: int) -> ChargeResult:
        raw = self._legacy.do_charge(str(amount_cents))
        return ChargeResult(success=raw["ok"])

Fixes: new code doesn't need to special-case the legacy gateway's stringly-typed, differently-shaped interface at every call site; the adapter absorbs that mismatch in exactly one place.

Trade-offs and pitfalls

• Introducing any of these three for a case with only ONE variant/implementation and no evidence a second is coming is speculative generality -- the pattern earns its keep once there are genuinely multiple interchangeable behaviors or implementations, not preemptively.
• Factory and Strategy can be over-engineered into deep class hierarchies for what could be a simple dictionary of functions in a language with first-class functions -- match the pattern's ceremony to the actual complexity of what's varying.