Amazon Software Development Engineer (SDE) Interview Preparation Guide - Junior Level (1-2 Years)

Direct answer: With memoization over both parameters $a, b \in [0, N]$, the function's time and space complexity are both $O(N^2)$: there are at most $(N+1)^2$ distinct $(a, b)$ pairs, each computed once and cached, and each computed state does $O(1)$ additional work beyond its (already-cached) recursive calls.

Structured elaboration

Without memoization, a recursive function over two parameters typically branches into a small constant number of recursive calls per invocation (say, 2-3, depending on the recurrence), giving exponential blowup because the same $(a, b)$ pair gets recomputed many times along different call paths.

With memoization:

• The state space is the set of all reachable $(a, b)$ pairs, bounded by $(N+1) \times (N+1) = O(N^2)$.
• Each distinct state is computed exactly once; on every subsequent call with the same $(a, b)$, the cached value is returned in $O(1)$.
• Total time is (number of distinct states) $\times$ (work per state, excluding recursive calls) $= O(N^2) \times O(1) = O(N^2)$.
• Space is the memo table itself, $O(N^2)$ entries, plus the recursion-call-stack depth, which is at most $O(N)$ if each call reduces $a+b$ (or similar) by a bounded amount - so the stack does not dominate the table.

Worked example

Take a concrete instance: $F(a, b) = F(a-1, b) + F(a, b-1)$ for $a, b > 0$, with base cases $F(0, b) = F(a, 0) = 1$ (this is the grid-path-counting recurrence, structurally identical to many DP-over-two-indices problems like edit distance or 2D grid counting). For $N = 3$:

def make_F():
    memo = {}
    calls = {"count": 0}
    def F(a, b):
        calls["count"] += 1
        if a == 0 or b == 0:
            return 1
        if (a, b) in memo:
            return memo[(a, b)]
        memo[(a, b)] = F(a - 1, b) + F(a, b - 1)
        return memo[(a, b)]
    return F, memo, calls

F, memo, calls = make_F()
result = F(3, 3)
print(result, len(memo), calls["count"])

Executed: F(3, 3) returns 20 (the number of monotonic lattice paths, matching $\binom{6}{3} = 20$), the memo table ends with exactly 9 entries (all $(a,b)$ pairs with $1 \le a, b \le 3$, confirming $O(N^2)$ distinct non-base states), and the memoized version makes 19 total function calls. Running the same recurrence with the cache removed entirely (identical logic, no memo dict) makes 39 calls for the same $F(3,3)$ - already noticeably more at this tiny $N$, and the gap widens combinatorially as $N$ grows, since the non-memoized call count follows the same exponential recursion-tree growth as naive Fibonacci, while the memoized version stays pinned to $O(N^2)$ states.

Trade-offs & pitfalls

• The "$O(N^2)$" bound assumes each state does $O(1)$ work beyond its recursive calls; if the per-state work itself scales with $a$ or $b$ (e.g. a loop inside the recursive step), multiply accordingly.
• Watch the recursion-DEPTH bound separately from the state-count bound - a poorly-designed recurrence could have depth $O(N^2)$ even though there are only $O(N^2)$ states, risking a stack overflow for large $N$ that a bottom-up (tabulated) version would avoid.
• If the parameters aren't bounded by a clean $[0, N]$ grid (e.g. one parameter can itself be a large derived value), re-derive the actual reachable state space before assuming it's the full product of the two ranges.

Approach: use backtracking with in-place swapping to build permutations. At recursion depth d we choose each unused element for position d by swapping it into index d, recurse, then swap back to restore state. This avoids extra arrays per branch and is efficient for distinct integers.

function permute(nums) {
  const res = [];
  // helper: generate permutations with current index 'start'
  function backtrack(start) {
    if (start === nums.length) {
      res.push(nums.slice()); // record a copy
      return;
    }
    for (let i = start; i < nums.length; i++) {
      // choose: swap nums[i] into position start
      [nums[start], nums[i]] = [nums[i], nums[start]];
      backtrack(start + 1);
      // restore: swap back to undo choice
      [nums[start], nums[i]] = [nums[i], nums[start]];
    }
  }
  backtrack(0);
  return res;
}

// Example:
console.log(permute([1,2,3]));
// Output: 6 permutations: [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]

Backtracking choices: swapping is the choose step; recursive call explores deeper choices; swapping back is the un-choose (restore) step, ensuring other branches see original order. Alternatively you can use a used[] boolean array and build a current list, which uses O(n) extra per level.

Time complexity: O(n! * n) — there are n! permutations and copying each (nums.slice()) takes O(n). Space complexity: O(n) extra for recursion depth plus O(n! * n) for output; in-place approach uses O(n) auxiliary stack.

Requirements clarification:

• Business: maximize approved legitimate payments, minimize fraud losses, meet regulatory/audit needs.
• Non-functional: <100ms fraud-decision latency for 99th percentile, 99.99% pipeline availability, explainability for disputed transactions.

SLIs to track (metric name — rationale):

• decision_latency.p50/p95/p99 (ms) — user experience and time-to-decision.
• decision_throughput (decisions/sec) — capacity planning.
• decision_error_rate (%) — exceptions, model failures, timeouts.
• false_positive_rate (FPR) and false_negative_rate (FNR) per cohort — business impact.
• approved_amount_lift_after_review (%) — human review effectiveness.
• model_confidence_distribution — detect drift/confidence collapse.
• end_to_end_success_rate (%) — payments completed without retry.
• feature_ingest_lag (s) — stale features cause wrong scores.

SLOs & alert thresholds:

• decision_latency.p95 < 80ms, p99 < 120ms. Alert if p95 > 100ms for 5m.
• decision_error_rate < 0.1%. Pager if >0.5% for 3m.
• FPR increase >50% relative to baseline → immediate alert to fraud/product.
• model_confidence drop (>30% of predictions below threshold) → data-science pager.
• end_to_end_success_rate > 99.9% — paging on sustained drop.

Traces/metrics/logs for debugging:

• Traces: end-to-end trace ID linking API gateway → scoring service → feature store → model inference → decision store; include spans for feature fetch, model predict, rule engine, DB writes.
• Metrics: per-model latency, CPU/memory, GC pause, queue lengths, feature store cache hit rate.
• Logs: structured JSON per decision: trace_id, timestamp, features (hashed/partial for PII), model_version, score, decision, confidence, rule_matches, downstream actions, user/payment IDs (tokenized).
• Sampling: full logs for failed/flagged transactions; 1% sampling for normals.

Ensuring low-latency scoring:

• Precompute and cache heavyweight features in a real-time feature store (Redis/RocksDB) with TTL; batch-update offline features asynchronously.
• Use lightweight model runtime (ONNX/TorchScript) in-process or colocated microservice with fast gRPC calls; prefer CPU-optimized inference or tiny ensembles.
• Circuit-breakers and graceful degradation: fallback to rule-based quick decisions if model unavailable; log fallback decisions for audit.
• Autoscale inference pool based on queue length and p95 latency; use request batching where beneficial but bounded (e.g., 5–10ms extra).
• Optimize network: colocate services in same AZ, use keep-alive, use binary protocols.
• Regular performance testing and chaos experiments (latency injection, model-service outages).

Operational practices:

• Canary deployments and shadowing new models; compare live predictions to prod model via metrics and drift detection.
• Alert runbooks (who, steps, rollback) and playbooks for model/data issues.
• Retain explainability artifacts per decision for 30–90 days for disputes/audit.

This combination maps business risk to measurable SLIs, concrete SLOs, actionable alerts, and engineering controls to keep fraud decisions fast, reliable, and debuggable.

Direct answer

Store only the timestamps that currently fall inside the window in a deque (a double-ended queue supporting O(1) push and pop from both ends), rather than recomputing a count from the full event history. Each new event is appended to the back; each query pops expired timestamps off the front until only in-window events remain, then reports the deque's length.

Structured elaboration

Approach

• A plain running total can be incremented on arrival, but it has no way to know which additions have aged out of the last W seconds, so it can only grow, never correctly shrink.
• Keeping only the timestamps inside the window, instead of a total, turns "is this event still relevant" and "how many are relevant" into deque operations: pop from the front while the oldest entries are older than the window allows, then read the length.
• Because timestamps only ever arrive in non-decreasing order, once an entry is popped off the front for being too old, it never needs to be looked at again. Each entry is pushed exactly once and popped at most once over its whole lifetime in the structure.

from collections import deque


class WindowCounter:
    def __init__(self, window_seconds):
        self.window = window_seconds
        self.q = deque()  # event timestamps currently inside the window, oldest first

    def record(self, t):
        """Record an event at time t. Timestamps must arrive non-decreasing."""
        self.q.append(t)

    def count(self, now):
        """Return how many recorded events fall in (now - window, now]."""
        cutoff = now - self.window
        while self.q and self.q[0] <= cutoff:
            self.q.popleft()
        return len(self.q)

Key points

• deque gives O(1) append and popleft, unlike a plain list where popping the front is O(n).
• The "pop expired from the front" step, run on every record or query, is what keeps memory bounded to just the events inside the window.
• This only works because input timestamps are non-decreasing; out-of-order arrivals would need a different structure.

Worked example

window_seconds = 10, recording and querying at the same moment as each event arrives, in order [0, 3, 5, 9, 12, 15]:

wc = WindowCounter(window_seconds=10)
for t in [0, 3, 5, 9, 12, 15]:
    wc.record(t)
    print(f"t={t}: count={wc.count(t)}")

prints:

t=0: count=1
t=3: count=2
t=5: count=3
t=9: count=4
t=12: count=4
t=15: count=3

At t = 12, the cutoff is 12 - 10 = 2, so the timestamp 0 (which is <= 2) is popped, leaving {3, 5, 9, 12}, a count of 4. At t = 15, the cutoff is 5, so timestamps 3 and 5 (both <= 5) are popped, leaving {9, 12, 15}, a count of 3.

Trade-offs & pitfalls

Complexity

Time: amortized $O(1)$ per record or count call. "Amortized" here means that although a single count call could in principle pop many expired entries at once, each timestamp is pushed once and popped at most once over the structure's whole lifetime, so total work across n calls is $O(n)$, averaging to $O(1)$ per call even though any single call's worst case is $O(n)$.
Space: $O(k)$, where k is the number of events currently inside the window, bounded by the arrival rate times the window length rather than by total history.

Edge cases

• No events yet: the deque is empty, count returns 0.
• Window smaller than the gap between consecutive events: the deque may hold 0 or 1 entries at a time.
• A burst of many events at the same instant: all are held until they age out together.

This only works if timestamps are guaranteed non-decreasing, as from a single writer or a single ordered stream. If events can arrive out of order (merged from multiple producers, or delayed in transit), the front-popping logic breaks, since an old event could arrive after entries that looked older have already been discarded. That calls for a different structure: a min-heap keyed on timestamp, or a fixed-size time-bucketed histogram (a small array of counters, one per sub-interval, rotated as time advances) for approximate counting in bounded memory regardless of burst size.

Direct answer

Use synchronous scoring only when the action on the score must happen before the transaction completes, such as blocking a fraudulent charge. If the action can wait (nightly review, retraining labels), batch scoring buys a heavier, more accurate model at a fraction of the cost. The deciding question: what does a delayed decision cost you, versus an always-on low-latency fleet?

Structured elaboration

Real-time: one hop in a hard end-to-end latency budget, needs near-zero-staleness features (a hot feature store: a system that serves the same precomputed input values, like a rolling transaction count, to the model at scoring time; "hot" means it's updated in near real time rather than nightly), and an always-on fleet sized for peak plus a fallback if the call times out.

Batch: runs on a schedule, so it can use a bigger, slower model on cheaper bursty compute, but adds a detection lag equal to the batch interval, and a partial failure is a silent under-score, not an outage.

Worked example

A 250ms authorize/decline budget, with auth, ledger, and notification already at 180ms:

$\text{fraud model budget} = 250\text{ms} - 180\text{ms} = 70\text{ms}$

Subtract 20ms network/serialization overhead:

$\text{compute budget} = 70\text{ms} - 20\text{ms} = 50\text{ms}$

That rules out heavy ensembles (combining predictions from several models, which multiplies the per-request compute cost) needing multiple feature joins (a feature store lookup that assembles several separate precomputed values into one input record, each join adding its own latency): illustratively, a 3-model ensemble with 2 extra feature joins might cost 90-120ms on its own, already over the 50ms budget, which is what "rules out" means here concretely. For batch: 10 million transactions overnight, 500 records per inference batch, 50ms per batch on one GPU:

$\text{batches} = \frac{10{,}000{,}000}{500} = 20{,}000, \quad \text{GPU time} = 20{,}000 \times 50\text{ms} \approx 16.7\text{ min}$

Across 4 GPUs, about 4 minutes wall time, no idle fleet cost during the day.

Trade-offs and pitfalls

Real-time buys speed but pays for peak capacity around the clock and widens the request's failure surface. Batch is cheaper but the fraud can complete before you act. A common mistake is defaulting to real-time without pricing the fleet against the actual cost of delay. The answer flips when either side of that equation moves: if fraud losses from a delayed decision start to dwarf the cost of an always-on fleet, or a cheaper real-time model becomes accurate enough to fit the leftover latency budget, you're pushed toward real-time; if the model needs more compute than the authorization path can spare, or false declines against legitimate customers become the bigger cost, you're pushed back toward batch.

What the interviewer probes next

Hybrid streaming or micro-batch designs, detecting a batch job that fails partway through, and how the answer shifts if a missed fraud case gets an order of magnitude costlier.

Direct answer. Reduce complexity behind a safety net, not by refactoring blind: pin current behavior with characterization tests first, then extract the distinct decision paths into named, independently-testable pieces (guard clauses, a lookup table, or polymorphism, depending on the shape of the branching), verifying at each step that behavior hasn't changed.

The plan

1. Characterize first: since complexity > 20 usually means many untested or under-tested paths, write characterization tests pinning current output for a representative sample of inputs -- including ones that exercise DEEP branches, not just the common path -- before touching the function's structure.
2. Identify the SHAPE of the complexity: is it a long chain of independent guard conditions (flatten with early returns), a dispatch on a type/category (candidate for a lookup table or polymorphism), or genuinely tangled business logic with real interdependencies (harder -- may need domain input to safely simplify, not just mechanical restructuring)?
3. Extract incrementally, verifying at each step: pull out one clearly-bounded piece at a time (a single validation block, one branch of a decision), re-run the characterization tests, and only proceed once green -- resist the urge to restructure the whole function in one large edit.
4. Re-measure complexity after each extraction to confirm you're actually reducing it, not just moving it into a differently-shaped equally-complex helper.
5. Keep shipping features on the surrounding code by doing this extraction opportunistically alongside real work touching this function, rather than blocking a dedicated 'refactor sprint' that competes with feature delivery.

Confirming behavior is unchanged

• Diff the characterization tests' output before and after each extraction step -- any change is either an intentional, called-out fix (documented as such) or a regression to immediately revert.
• For inputs you can't easily enumerate exhaustively, consider property-based testing (generate many random inputs, assert output equivalence between old and new implementations run side by side) as an additional safety net beyond hand-picked characterization cases.

Trade-offs and pitfalls

• Reducing cyclomatic complexity by mechanically extracting helper functions without addressing WHY the logic is tangled (often: too many responsibilities, or business rules that were bolted on over time without a cohesive model) can just relocate complexity rather than remove it -- watch for 'complexity 22 became five functions each complexity 5' with no actual improvement in how hard the FULL flow is to reason about.
• Don't treat 'reduce complexity' as the end goal in isolation from readability; a function refactored down to complexity 8 that's now split across five oddly-named helpers you have to jump between can be a worse reading experience than a well-organized, slightly-higher-complexity original.

Direct answer

Make two passes over the array without ever dividing. In the first pass, fill the output with the running PREFIX product (the product of everything to the left of each index). In the second pass, walk from the right and multiply each entry by a running SUFFIX product (the product of everything to the right of each index). After both passes, output[i] holds the product of every element except nums[i].

Structured elaboration

Approach

def product_except_self(nums):
    n = len(nums)
    output = [1] * n

    prefix = 1
    for i in range(n):
        output[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):
        output[i] *= suffix
        suffix *= nums[i]

    return output


def naive_division(nums):
    """The disallowed shortcut, shown only to make its zero-element failure
    concrete rather than asserted: multiply everything once, then divide by
    each element in turn."""
    total = 1
    for x in nums:
        total *= x
    out = []
    for x in nums:
        if x == 0:
            out.append(None)  # division by the zero element is undefined
        else:
            out.append(total // x)
    return out

This is O(n) time (two linear passes) and O(1) extra space, not counting the output array itself, exactly as the question specifies, since only two running scalar accumulators (prefix and suffix) are kept alongside the output.

Why prefix and suffix products work, and why no division is needed

Every position i's answer is exactly (product of nums[0..i-1]) * (product of nums[i+1..n-1]), the product of everything strictly to the left, times the product of everything strictly to the right. The first pass computes and stores the left-hand factor for every index in one sweep (writing it into output[i] before nums[i] itself is folded into the running prefix). The second pass computes the right-hand factor the same way while sweeping backward, multiplying it directly into the value already stored. Because the two factors are built and combined without ever needing nums[i] itself in the final expression, this naturally avoids the "divide the total product by nums[i]" approach, which is both explicitly disallowed here and would break outright on any zero in the input (division by zero, or worse, silently wrong results if a naive implementation tries to special-case just one zero).

Leave-one-out features (the question's explicit ask)

The prefix/suffix accumulation pattern used here is the general technique behind computing a "leave-one-out" aggregate for every position without recomputing the whole aggregate from scratch each time. The most common leave-one-out feature in practice is a SUM (for example, "total spend across a group, excluding this member"), computed the same way with running prefix and suffix sums instead of products; the product version shown here applies the identical idea whenever the aggregate you need excluded is a product rather than a sum, for example computing a joint likelihood or a normalization factor across a set of independent factors while excluding one factor at a time.

Worked example

Executed with python3 s84.py (both functions defined above):

product_except_self([1, 2, 3, 4]) = [24, 12, 8, 6]
manual check: [24, 12, 8, 6]

Manually: excluding index 0 leaves 2*3*4=24; excluding index 1 leaves 1*3*4=12; excluding index 2 leaves 1*2*4=8; excluding index 3 leaves 1*2*3=6. All four match the function's output exactly.

product_except_self([1, 2, 0, 4]) = [0, 0, 8, 0]
naive division-based version on the same input = [0, 0, None, 0]  <- breaks on the zero element

With a zero present, every output except the one at the zero's own index is 0 (since every other output's product still includes the zero), while the output AT the zero's index is the product of everything else (1*2*4=8). A division-based approach (compute the total product, then divide by nums[i]) fails outright here: dividing by the zero element itself is undefined, shown above returning None rather than the correct value 8.

Trade-offs and pitfalls

• The division-based shortcut (multiply everything, then divide by nums[i] for each output) is both explicitly disallowed by the question and fundamentally broken the moment any element is zero; the executed comparison above makes this concrete rather than asserted.
• The two-pass prefix/suffix technique generalizes directly to any associative combining operation (sum, product, min, max, and so on) wherever a "leave-one-out" aggregate is needed without an inverse operation (subtraction for sum, division for product) available or safe to use.
• If the array can be very large and the values themselves can be large integers, the running prefix and suffix products can grow to very large magnitudes; in a fixed-width integer language (unlike Python's arbitrary-precision integers), this needs an explicit overflow check or a different numeric representation, which is worth naming even though Python itself does not hit this limit.

Direct answer

A retro after a release with repeated design-engineering friction should produce two things: an honest, specific account of where the handoff actually broke down, not a vague 'communication issues,' and a small number of concrete process changes, each with an owner and a way to tell in a quarter whether it worked. Running it well means separating fact-finding from diagnosis, and diagnosis from blame.

Structured elaboration

Design principles for the session

• Facts before diagnosis: start from a timeline of what actually happened (spec dates, handoff dates, bug counts, points where implementation and design diverged), not from opinions about who was at fault.
• Root cause, not the nearest symptom: 'engineering didn't follow the spec' is a symptom; the root cause might be that the spec didn't capture edge-case states, or that both sides were working from different versions of a shared design system mid-migration.
• Few, high-leverage commitments: two or three process changes people will actually do beat ten action items that quietly get dropped.
• Everyone leaves with the same understanding of what changed, not just what went wrong.

A workable structure

One illustrative shape, adaptable to a team's own rhythm:

What 'actually changes how the two teams work' looks like

The output isn't a list of intentions, it's a specific artifact or habit that exists after the meeting and didn't before: a shared checklist embedded in the handoff process, an automated check that catches a class of mismatch before it ships, or a standing short sync during implementation windows. Whatever it is, it needs a way to tell if it worked, not just that it happened.

Worked example

One team's root cause turned out to be that design tokens (colors, spacing values) were maintained in the design tool but hand-copied into code, so drift was inevitable and nobody could tell which side was 'correct' when they disagreed. The concrete fix was an automated export from the design tool into the codebase, checked by both a design reviewer and a frontend reviewer before merge, plus a short recurring sync during active implementation. A quarter later, the team had a real signal that it worked: noticeably fewer visual-mismatch comments on pull requests and less late-stage rework than the release that triggered the retro. The same root-cause pattern shows up in other domains as a hand-copied data contract or config value instead of a design token, so the same fix shape (automate the handoff, add a lightweight check, add a short sync during the risky window) generalizes well beyond design and engineering specifically.

Trade-offs and pitfalls

• A retro that produces ten action items usually produces zero completed ones; prioritizing ruthlessly matters more than being thorough.
• If the room jumps straight to solutions or blame instead of facts first, the real root cause, often structural or tooling-related rather than a person's failure, never surfaces.
• A retro that isn't revisited becomes theater. Put the check-in on the calendar before the room disperses, not as a vague intention afterward.
• Watch for a fix that only addresses this specific release's symptom (a one-off manual double-check) rather than the structural cause; it holds for one cycle and then quietly stops happening.

Direct answer

Check bipartiteness with a two-coloring BFS or DFS: assign the start node of each component color 0, every uncolored neighbor the opposite color of the node discovering it, and if a neighbor is ever found ALREADY colored the SAME color as the current node, that edge is a genuine conflict proving the graph is not bipartite, so it, and the coloring built so far, can be returned immediately. Since the graph may be disconnected, the outer loop must restart the coloring process from every not-yet-visited node, not just once from an arbitrary start, or entire components could be silently skipped.

Structured elaboration

Why two-coloring detects bipartiteness exactly. A graph is bipartite exactly when its nodes can be split into two groups such that every edge has one endpoint in each group, which is precisely what a valid two-coloring represents (color 0 = group A, color 1 = group B). BFS or DFS coloring greedily attempts to build such a coloring, and the greedy attempt is provably sufficient (not just a heuristic): if a valid two-coloring exists at all, the greedy alternate-color-along-each-edge process will find one, because the color of every node is fully determined (up to a global swap of which color means which group) by its distance parity from wherever the BFS/DFS started in its component.

Why an odd cycle is exactly what breaks it. Walking around any cycle, colors must alternate at every edge, so after an EVEN number of edges you return to the same color you started with (consistent), but after an ODD number of edges you return to the OPPOSITE color from where you started, a direct contradiction if that "return" edge closes the cycle back to the start node. This is why bipartiteness is exactly equivalent to having no odd-length cycle; the conflict-detecting edge in the algorithm below IS the edge that closes such an odd cycle.

Handling disconnection. Each connected component must be colored independently (nothing forces component A's coloring choice to relate to component B's, since no edge connects them), which is why the algorithm's outer loop iterates over every node as a potential fresh BFS start, skipping only nodes already colored by an earlier component's BFS.

Worked example

from collections import deque
from typing import Dict, List

def bipartite_check(adj: Dict[int, List[int]]):
    color: Dict[int, int] = {}
    for start in adj:
        if start in color:
            continue
        color[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in adj.get(u, []):
                if v not in color:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False, color, (u, v)
    return True, color, None

if __name__ == "__main__":
    # Component A: even cycle 0-1-2-3-0 (bipartite, length 4)
    # Component B: odd cycle 4-5-6-4 (triangle, NOT bipartite)
    # Component C: isolated node 7
    adj = {
        0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [2, 0],
        4: [5, 6], 5: [4, 6], 6: [5, 4],
        7: [],
    }
    is_bip, coloring, conflict = bipartite_check(adj)
    print("is_bipartite:", is_bip)
    print("coloring so far:", coloring)
    print("conflict edge:", conflict)

Output:

is_bipartite: False
coloring so far: {0: 0, 1: 1, 3: 1, 2: 0, 4: 0, 5: 1, 6: 1}
conflict edge: (5, 6)

Component A (the 4-cycle) colors cleanly with no conflict: 0 and 2 land color 0, 1 and 3 land color 1, and every edge in that cycle correctly connects opposite colors, confirming a 4-length (even) cycle is bipartite. Component B (the 3-cycle, a triangle) cannot: after coloring 4=0 and 5=1, node 6 is reached from 4 first (getting color 1, opposite of 4), but the edge 5-6 is then found connecting two nodes that are BOTH color 1, the odd-cycle contradiction, correctly reported as the conflict edge (5, 6). Component C (isolated node 7) is never reached by this trace since the graph is reported non-bipartite before the outer loop gets to it, which is correct behavior: once a conflict is found anywhere in the graph, the whole graph is non-bipartite and there is no need to keep coloring remaining components.

Trade-offs and pitfalls

• Common mistake: only running BFS/DFS once from a single arbitrary start node. On a disconnected graph, this silently leaves every OTHER component's nodes uncolored and unchecked, which can wrongly report a graph as bipartite if the conflict actually lives in an unreached component.
• The conflict edge is genuinely useful beyond a bare boolean, since it tells a caller exactly WHERE the odd cycle was detected (not the full cycle itself, but its closing edge), which is enough to start tracing the specific odd cycle if that is needed for follow-up diagnostics.
• Complexity is $O(V+E)$, since coloring is a direct BFS with no extra per-node or per-edge work beyond a color check, an important point to state explicitly since "detect an odd cycle" sounds like it could naively cost more (for example, if implemented as an explicit search for cycles rather than a direct coloring pass).
• Common mistake: returning the coloring so far as if it were a valid full coloring when the graph turns out non-bipartite. The coloring dict returned alongside a False result is a PARTIAL, invalid attempt (it necessarily contains the conflicting same-colored pair), not a usable 2-coloring; callers must check the boolean first and treat the coloring as meaningful only when True.

Direct answer
Five Whys means repeatedly asking 'why did that happen' about the answer to the previous why, until you reach a condition that is actually fixable rather than just another symptom. It typically takes about five iterations, though the number is a rule of thumb, not a hard rule: you stop when you hit something you can change, not necessarily on the fifth why.

Structured elaboration
For the incident (a key API returned errors for 45 minutes after a deploy, affecting a fifth of users), a Five Whys chain might look like:

1. Why did the API return errors? Because the newly deployed version crashed on a specific request shape.
2. Why did it crash on that request shape? Because a null field that used to always be populated was left unhandled by new code.
3. Why was the field null? Because an upstream service started omitting it after its own recent change, and the API's input validation did not reject the malformed payload.
4. Why did input validation not catch it? Because the API's schema validation checks types but not presence of this particular field, and there is no contract test between the two services that would have caught the mismatch before deploy.
5. Why is there no contract test between these services? Because the team has no standard practice requiring consumer-driven contract tests for internal service dependencies, so this class of breaking change can slip through again.

Root cause at the fifth why: the absence of a contract-testing practice between dependent services, which let an upstream breaking change reach production undetected. Remediation: add a consumer-driven contract test between the two services that fails the upstream service's CI if it would omit a field the downstream API depends on, and, as an immediate mitigation, add explicit null-handling and a clear 400 response for the malformed field so a similar future gap fails safely instead of crashing.

Worked example
The chain above IS the worked example. The key discipline: each why answers the previous one specifically, not by restating a broader class of the same problem ('bugs happen') or jumping straight to a process indictment ('nobody tests enough'). Each step should be falsifiable, meaning someone could look at logs, code, or configuration and confirm or reject it.

Trade-offs and pitfalls
Five Whys works well for a single, mostly-linear causal chain, but it can mislead on incidents with multiple independent contributing factors, because it forces a single narrative thread and stops once any plausible chain reaches a stopping point, even if a second, unrelated factor also mattered. In this incident, if the on-call engineer's alert also fired 15 minutes late due to an unrelated threshold problem, a rigid Five Whys chain focused only on the crash would miss that second, independently-worth-fixing gap. When you suspect multiple contributing factors, pair Five Whys with a fishbone diagram or explicit causal-chain mapping so parallel factors don't get dropped.