Amazon Data Scientist Interview Preparation Guide (Mid-Level)

Direct answer

Selection comes down to four criteria, weighted in this order when they conflict: relevance to the role you're interviewing for, ownership (how much of the outcome you personally drove), impact (the size and credibility of the result), and freshness (how clearly you can still recall and defend the details). A project that scores well on ownership and relevance usually beats a bigger-name project you can't speak to in depth.

Structured elaboration

• Relevance: does the work resemble what this team actually does day to day? An infrastructure migration story fades in a design interview, and vice versa.
• Ownership: did you make the pivotal decision, or were you one of eight people who each did a small slice? Interviewers weight decisions you can defend over decisions you merely participated in.
• Impact: is there a real before/after, ideally with a number, and can you explain how that number was measured, not just that it existed?
• Freshness: can you still answer follow-up questions about specifics (why that approach, what the failure mode was) without hedging?

A simple scoring pass: when you have more than one strong candidate, score each project 1 to 3 on each criterion (3 = strongest) and total them. This forces relevance and ownership to compete fairly against a project that just has the biggest headline number.

When your list is short

If you don't have several strong candidates to weigh, the four criteria still apply, but the move changes: instead of ranking multiple projects, depth-mine the one or two you have. Walk through the slice that was actually yours (not the whole team's or class's), a specific decision you made even in a small role, and what you learned or how you grew from doing it. Academic projects, coursework you extended past the assignment, and personal side projects all count, as long as you can speak to a real decision and a real outcome, even a small one. The interviewer is testing judgment and self-awareness here, not the size of the resume line.

Worked example

Three candidate projects for one interview:

B wins on total (11) even though A has the bigger headline number, because ownership and relevance carry it. That's usually the right call: A invites "what exactly did you personally do," and the honest answer is "one piece of a ten-person effort," which is a weaker answer than B's fully defensible ownership story.

Trade-offs and pitfalls

• Don't let a big company name or big number override ownership; the first follow-up is almost always "what did YOU do," and a thin answer there undoes the headline number.
• Freshness isn't just "when it happened," it's "can you still reconstruct the reasoning." A two-year-old project you documented well can outscore a six-month-old project you've half-forgotten.
• Relevance should map to the team, not just the job title; the same title on a fraud team and a growth team wants a different story.
• Keep a primary and a backup ready; sometimes the first follow-up reveals your primary pick was the wrong choice for this particular interviewer.

Direct answer

I would not agree yet. A rising Net Promoter Score (NPS) tells me that more survey respondents said they would recommend us. Before I treat that as "customers are happier" I want to know who answered, whether the rise is bigger than noise, and whether behaviour (retention, usage, support contact) moved the same way.

What NPS is

Customers answer one question, "How likely are you to recommend us to a friend or colleague?", on a 0 to 10 scale. Scores of 9 to 10 are promoters, 7 to 8 are passives, 0 to 6 are detractors.

NPS = % promoters - % detractors

The result runs from -100 to +100. Passives do not count in the formula.

What I would ask before agreeing

1. How many responded, out of how many invited, and did the response rate (answers divided by invitations) change? A different mix of respondents can move the score on its own.
2. Did the customer mix change (more enterprise, fewer trial users), or the survey wording, timing or channel?
3. How big is the rise relative to the survey's noise? See the example below.
4. What do the open-text "why" answers say? Did detractors shrink, or did promoters grow?
5. Did retention, renewals, usage depth and time to first value (how long new customers take to get their first real outcome) move in the same direction?

Worked example (illustrative responses, reproducible)

The code below measures noise, meaning the random wobble you get because a different set of customers answering would give a slightly different score even if nobody's feelings changed. To measure it, give every answer a value: +1 for a promoter, -1 for a detractor, 0 for a passive. NPS is 100 times the average of those values, which is exactly the share of promoters minus the share of detractors. The spread of the individual values is p + d - (p - d)^2, where p is the promoter share and d the detractor share. Dividing by the number of answers n and taking the square root gives the standard error: the typical amount the score would move if you re-surveyed a different random group of the same size.

standard error = 100 * sqrt( (p + d - (p - d)^2) / n )

Small surveys wobble more, because n sits under the square root. Two independent surveys combine their wobble as sqrt(se1^2 + se2^2), which is why a comparison between two quarters is noisier than either score alone.

Last quarter: 80 promoters, 70 passives, 50 detractors (200 answers), NPS +15. This quarter: 54, 36, 30 (120 answers), NPS +20. The VP sees +5.

from math import sqrt

def nps(promoters, passives, detractors):
    n = promoters + passives + detractors
    p, d = promoters / n, detractors / n
    score = 100 * (p - d)
    se = 100 * sqrt((p + d - (p - d) ** 2) / n)  # standard error of the score
    return score, se

q1, se1 = nps(80, 70, 50)
q2, se2 = nps(54, 36, 30)
diff = q2 - q1
se_diff = sqrt(se1 ** 2 + se2 ** 2)
print(round(q1), round(se1, 1))
print(round(q2), round(se2, 1))
print(round(diff), round(se_diff, 1), round(diff / se_diff, 2))

It prints 15 5.6, then 20 7.4, then 5 9.3 0.54. The standard error of the difference is about 9 points, so a 5-point rise is about half a standard error (5 / 9.3 = 0.54). A common rule of thumb is that a gap needs to be roughly two standard errors (here about 19 points, since 2 x 9.3 = 18.6) before you treat it as more than chance. With these samples a rise of 5 points cannot be told apart from chance, and the response count fell from 200 to 120, which itself needs explaining.

When another measure tells you more

Timing matters: CSAT and CES measure a moment, NPS measures a feeling about the relationship, so asking NPS right after a good support reply inflates it.

Limits of survey scores alone

Only responders are heard, scores can be gamed (asking only happy customers), and a number gives no reason. Pair every score with open-text answers and with behaviour. If NPS rises while renewals and usage are flat, believe the behaviour.

What I would tell the VP

"The rise is encouraging but not yet proof. Let me show you the segment split, the response counts and the retention trend next to it."

Direct answer

A novelty effect is a temporary inflation of an early treatment effect: users explore or click on something purely because it is new, and that extra engagement fades once the feature stops being novel, biasing an early readout upward. A primacy effect (sometimes called a change-aversion or resistance-to-change effect) is the opposite pattern: a change disrupts a habitual workflow, so users are temporarily worse off while they relearn it, biasing an early readout downward, then the effect climbs toward its true level as users adapt. Both biases fade over roughly the same kind of horizon, so trusting a week-one number without checking its trajectory can make you launch a fad or kill a genuine win too early.

Structured elaboration

Mechanism and direction

Diagnostics to tell a spike from a persistent effect

• Time-windowed effect plot: daily or weekly treatment effect with confidence intervals, ideally with a smoothed trend line (LOESS or a spline), not a single pooled average. A genuine effect looks like a roughly flat band around a nonzero value; novelty looks like a spike that decays toward that band; primacy looks like a trough that rises toward it.
• Exposure-age cohorts, not calendar time: plot the effect against days since each user's first exposure for a fixed cohort of users first exposed on the same day, rather than calendar date. A calendar-time plot mixes newly exposed users (still novel-biased) with long-exposed users (already stabilized) every single day, which can mask a real decay curve as a flat line.
• New vs. returning user split: novelty is usually concentrated in users encountering the feature for the first time; if the effect is similar in a segment already exposed for weeks, that argues against novelty as the explanation.
• Change-point or decay model on the daily series: fit a time-varying effect model, effect as a function of exposure age, and test whether the transient component is statistically distinguishable from zero, separately from the asymptotic (persistent) component.
• Placebo check: run the same time-windowed analysis on a pre-launch period with no real treatment; if spike-like patterns appear there too, the "decay" you see in the real experiment may just be normal week-to-week noise, not a novelty artifact.

Adjusting duration and analysis

• Pre-register the analysis window before launch rather than reading the metric the moment it looks good; a fixed rule such as "primary read is the average effect over exposure-days 21 to 35" prevents cherry-picking the peak or the trough.
• Extend the experiment until the exposure-age curve visibly plateaus, or the fitted transient component's confidence interval crosses zero, rather than for a fixed calendar duration chosen in advance.
• Report both the early-window and late-window effect side by side rather than a single blended number; a launch decision based only on the blended average silently averages a fading spike with a stabilizing floor.

Worked example

Two hypothetical (illustrative, not real study data) weekly average-treatment-effect readings for the same nominal conversion metric:

Both curves are converging toward roughly the same persistent level, one from above and one from below, which is exactly the signature that separates them from a flat, genuine effect that would show roughly the same number every week within noise.

If the transient component decays exponentially, $\Delta(t) = C + A e^{-\lambda t}$, where $A$ is the size of the initial novelty or primacy spike above the persistent effect $C$ (the extra amount present at $t=0$ that fades away over time), and the illustrative decay rate is $\lambda = 0.2$ per week, its half-life is:
$t_{1/2} = \frac{\ln 2}{\lambda} = \frac{0.693}{0.2} \approx 3.5 \text{ weeks}$
That is the kind of number worth pre-registering as a decision rule: run at least three half-lives (about 10 to 11 weeks here) before reading the persistent effect $C$, rather than picking an arbitrary duration.

Trade-offs and pitfalls

• Waiting out a full decay curve costs calendar time and opportunity cost on other experiments; for low-stakes features, teams sometimes accept the risk of a novelty-inflated launch decision rather than run for months.
• Segmenting by exposure age needs per-user first-exposure timestamps captured in the assignment log; if you only log calendar-date rollups, you cannot separate calendar effects from exposure-age effects after the fact.
• A curve that looks like decay can just as easily reflect unrelated seasonality (marketing pushes, holidays) that correlates with launch timing; a decay-shaped curve is suggestive, not conclusive, on its own.
• Don't assume every early spike is novelty and every early trough is resistance to change: an early spike can be a genuine effect solving a pent-up need immediately, and an early trough can be a real bug that later gets patched. The pattern is evidence, not proof, and should be paired with qualitative checks (support tickets, session recordings) before concluding the mechanism.

Direct answer

The nested loop is quadratic because for every one of the $n$ records on the left, it scans all $m$ records on the right looking for a key match, doing $n \times m$ comparisons total regardless of how many actually match. Building a dictionary keyed on the join key from one side first turns each lookup into an expected $O(1)$ hash-table probe instead of an $O(m)$ scan, bringing the whole join down to expected $O(n + m)$: build the index once, then probe it once per record on the other side.

Structured elaboration

Why the nested loop is quadratic: for each of the $n$ left records, the inner loop walks the entire right list looking for l[key] == r[key], whether or not it finds a match early. That is $n$ full passes over a list of size $m$, i.e. $O(n \times m)$ comparisons, degenerating to $O(n^2)$ when the two sides are similar in size.

The hash-based fix: build a dictionary once, mapping each join key to the list of records on the smaller side that carry that key (a key can map to more than one record, so store a list per key, not a single record). Then iterate the other side once, and for each record, look up its key in the dictionary directly instead of scanning. Dictionary lookup is expected $O(1)$ (amortized, assuming a reasonable key-hash distribution), so the whole pass over the second side is expected $O(m)$, and building the index was $O(n)$, giving expected $O(n + m)$ overall. This is the same idea a database's hash-join operator uses internally.

Which side to build the index on: build the hash table from the smaller of the two inputs and probe with the larger one. The index costs memory proportional to the side you build it from, so building on the smaller side minimizes peak memory; which side you probe with does not change the time complexity, only which side pays the memory cost.

Worked example

Verified on CPython 3.12, confirming the hash-based join produces the identical row set as the nested-loop version:

from collections import defaultdict

def nested_join(left, right, key):
    result = []
    for l in left:
        for r in right:
            if l[key] == r[key]:
                result.append({**l, **r})
    return result

def hash_join(left, right, key):
    if len(left) <= len(right):
        build, probe, build_is_left = left, right, True
    else:
        build, probe, build_is_left = right, left, False

    table = defaultdict(list)
    for b in build:
        table[b[key]].append(b)

    result = []
    for p in probe:
        for m in table.get(p[key], ()):
            combined = {**m, **p} if build_is_left else {**p, **m}
            result.append(combined)
    return result

left = [{"id": i, "l": f"l{i}"} for i in range(200)]
right = [{"id": i, "r": f"r{i}"} for i in range(100, 300)]

r1 = sorted(nested_join(left, right, "id"), key=lambda d: d["id"])
r2 = sorted(hash_join(left, right, "id"), key=lambda d: d["id"])
print("row counts equal:", len(r1) == len(r2), len(r1))
print("same content:", r1 == r2)

Output: row counts equal: True 100 and same content: True, confirming both approaches return the same 100 matched rows for this overlapping-range test data.

Trade-offs & pitfalls

• Complexity: nested loop is $O(n \times m)$ time, $O(1)$ extra space; hash join is expected $O(n + m)$ time, $O(b)$ extra space where $b$ is the size of whichever side you build the index from.
• Edge case: many-to-many joins (a key repeated on both sides) need every match emitted, storing a list per key (not overwriting a single slot per key) handles this correctly; a common bug is using a plain dict mapping key to one record, which silently drops all but the last record for a repeated key.
• Edge case: composite keys (joining on more than one column) work the same way as long as the key you hash on is itself hashable, typically a tuple of the individual field values rather than a single field.
• A related antipattern worth recognizing, even outside a join: building a dict of lists to group records by key, and then aggregating (summing, counting) by scanning each list afterward, pays the memory cost of holding every raw record in memory per key and then pays an extra full pass to aggregate. If you only need an aggregate (a count, a sum) and not the individual grouped records, aggregate incrementally as you go (defaultdict(int) with += on each record) instead of collecting a defaultdict(list) first and reducing it afterward; the collect-then-reduce version uses $O(n)$ memory it does not need to and does the aggregation work twice.
• Hash join assumes the build side fits in memory. If it does not, this degrades to either an external (disk-backed) hash join, partitioning both sides into buckets that each fit in memory, or a sort-merge join, sorting both sides by key and merging in one linear pass, at the cost of the sort itself ($O(n \log n)$).
• If the data is already sorted on the join key (for example, coming from an ordered log or an indexed source), a sort-merge join can beat a hash join outright, since it avoids building any auxiliary index at all; the hash-based approach is the right default only when you cannot assume sorted input.

Direct answer

Clean each column with its own targeted logic rather than one generic converter: strip whitespace and coerce id with pd.to_numeric(..., errors='coerce') into pandas' nullable Int64, and strip currency symbols, commas, and parenthesized negatives from amount with a small parsing function before converting to float64. Route every failed value through errors='coerce' (or an explicit try/except) rather than letting a bad row raise and kill the whole conversion, then build the failure report from wherever the coerced value came back missing but the raw value was not.

Implementation

import pandas as pd
import re

def clean_df(df):
    df = df.copy()

    # --- id: strip whitespace, coerce to nullable integer ---
    df["id_raw"] = df["id"]
    df["id_str"] = df["id"].astype(str).str.strip().replace({"nan": pd.NA})
    df["id_int"] = pd.to_numeric(df["id_str"], errors="coerce").astype("Int64")

    # --- amount: strip currency symbols/commas, handle parenthesized negatives ---
    df["amount_raw"] = df["amount"]

    def parse_amount(x):
        if pd.isna(x):
            return float("nan")   # NOT pd.NA: a float64 column needs a float NaN, not the pandas-NA scalar
        s = str(x).strip()
        negative = bool(re.match(r"^\(.*\)$", s))       # "(500.00)" style accounting negatives
        s = s.replace("(", "").replace(")", "")
        s = re.sub(r"[^\d.\-eE]", "", s)                 # drop currency symbols, commas, spaces
        try:
            v = float(s)
            return -v if negative else v
        except ValueError:
            return float("nan")

    df["amount_float"] = df["amount"].apply(parse_amount).astype("float64")

    # --- failure report: rows where the raw value existed but conversion failed ---
    failed_id = df[df["id_int"].isna() & df["id_str"].notna()][["id_raw", "id_str"]]
    failed_amount = df[df["amount_float"].isna() & df["amount_raw"].notna()][["amount_raw"]]

    report = {
        "total_rows": len(df),
        "successful_id": int(df["id_int"].notna().sum()),
        "failed_id_count": int(failed_id.shape[0]),
        "failed_id_samples": failed_id.head(5).to_dict(orient="records"),
        "successful_amount": int(df["amount_float"].notna().sum()),
        "failed_amount_count": int(failed_amount.shape[0]),
        "failed_amount_samples": failed_amount.head(5)["amount_raw"].tolist(),
    }

    result = df.drop(columns=["id_str"])
    return result, report

Worked example (verified against pandas 3.0.3)

raw = pd.DataFrame({
    "id":     [" 101 ", "102", " bad_id ", "104", None],
    "amount": ["$1,234.56", "(500.00)", "2,000", "oops", "$99.99"],
})
result, report = clean_df(raw)
print(result[["id_raw", "id_int", "amount_raw", "amount_float"]])

Actual output:

     id_raw  id_int amount_raw  amount_float
0      101      101  $1,234.56       1234.56
1       102     102   (500.00)       -500.00
2   bad_id     <NA>      2,000       2000.00
3       104     104       oops           NaN
4       NaN    <NA>     $99.99         99.99

and report:

{
  "total_rows": 5,
  "successful_id": 3,
  "failed_id_count": 1,
  "failed_id_samples": [{"id_raw": " bad_id ", "id_str": "bad_id"}],
  "successful_amount": 4,
  "failed_amount_count": 1,
  "failed_amount_samples": ["oops"]
}

" bad_id " correctly fails id conversion and is captured; "(500.00)" correctly becomes -500.00; "2,000" correctly strips the comma to 2000.00; "oops" correctly fails amount conversion; a genuinely missing id (None) is reported as <NA> rather than counted as a conversion failure, since there was nothing to convert.

A bug worth calling out explicitly, since it only shows up when you actually run the code: if parse_amount returns pd.NA (the pandas missing-value scalar) instead of float("nan") on failure, the subsequent .astype("float64") raises TypeError: float() argument must be a string or a real number, not 'NAType', because a plain NumPy float64 array cannot hold pd.NA, only pd.NA-aware nullable dtypes can. The fix is the one shown above: return a real float NaN from the parsing function when you intend to .astype("float64") afterward, and reserve pd.NA for columns you are explicitly building as nullable (Int64, boolean, string) dtypes.

Key points

• Int64 (capital I) for id preserves missing ids as <NA> rather than silently upcasting to float64.
• parse_amount handles currency symbols, thousands separators, parenthesized accounting negatives, and scientific notation, in that order, parentheses are stripped before the character-class filter so the surrounding digits survive.
• Both conversions use errors="coerce" (or an equivalent try/except) so a bad row becomes an inspectable missing value instead of crashing the whole pipeline, and the failure report is built by comparing "raw value present" against "converted value missing," which correctly distinguishes a genuine parsing failure from a genuinely missing input.

Complexity and edge cases

Complexity: O(n) time for both columns; id conversion is fully vectorized through pd.to_numeric, amount conversion runs a Python-level .apply() per row because of the custom parenthesis/currency logic, so it is the slower of the two per-element, though still linear overall. Memory: the intermediate id_raw, id_str, amount_raw columns roughly double the memory footprint of those two columns during cleaning; drop them once the report is built if memory is tight.
Edge cases: a completely empty amount string or None is treated as missing (not a parse failure) via the pd.isna(x) check at the top of parse_amount. Locale-specific formats (comma as the decimal separator instead of the thousands separator, as in many European locales) are not handled by this regex and would need locale-aware parsing instead. A value with multiple embedded currency symbols or unusual tokens ("~$50", "50 USD") is silently stripped down to its digits by the character-class filter, which happens to work for these examples but should be validated against real data rather than assumed correct for every currency format you might encounter.

Direct answer
Learning-rate schedules all answer the same question, how should the step size change over training, differently: step and exponential decay shrink it on a fixed schedule, cosine annealing shrinks it smoothly (optionally with periodic restarts), cyclical schedules deliberately move it up and down, and warmup ramps it up from near zero before any of the above kicks in.

Structured elaboration
Step decay multiplies the learning rate by a fixed factor at specific milestones (e.g. divide by 10 at epochs 30, 60, 90); simple, and gives clean, large "phase changes" useful for coarse-to-fine training. Exponential decay applies $\eta_t = \eta_0 e^{-kt}$, a smooth continuous shrink with no manual milestone tuning required. Cosine annealing follows $\eta_t = \eta_{\min} + \tfrac12(\eta_{\max}-\eta_{\min})(1+\cos(\pi t/T))$ over $T$ steps, giving a smooth cool-down that empirically often out-performs step decay's abrupt jumps; with restarts (SGDR), the schedule periodically jumps back up to $\eta_{\max}$ partway through training, deliberately re-injecting exploration to help escape a poor local region before resuming the cool-down. Cyclical learning rates instead deliberately cycle the rate between a lower and upper bound throughout training (not just at restarts), which can reduce how precisely you need to have tuned the base learning rate in the first place, since the cycle itself sweeps through a range of values. Linear warmup ramps the learning rate up from near zero to its target value over the first few hundred or thousand steps, BEFORE any decay schedule takes over.

Why warmup matters for large models: at the very start of training, weights (and for adaptive optimizers, the moment estimates) are uncalibrated, so a full-strength learning rate applied immediately can produce a large, destabilizing update before the network or optimizer state has had any chance to settle; warmup avoids this by keeping early updates small while things calibrate, which becomes especially important as model size, batch size, or the base learning rate grow.

Which schedules pair well with large-batch training: warmup is close to mandatory at large batch sizes (large batches typically use a correspondingly larger learning rate via the linear scaling rule, which makes the destabilizing-early-update risk warmup addresses even more acute); cosine annealing (with or without restarts) is the most common pairing with warmup for large-scale training, since its smooth decay complements a smooth ramp-up, whereas step decay's abrupt drops can feel like a second, smaller version of the same instability warmup was meant to avoid.

Worked example
A standard large-model recipe: linear warmup over the first 5% of total training steps (rate rising linearly from 0 to the target learning rate), followed by cosine annealing down to a small floor value for the remaining 95% of steps, with no restarts; this exact combination is the de facto default for most modern transformer training recipes precisely because both halves are smooth and compose cleanly.

Trade-offs & pitfalls
A common mistake is applying a schedule's decay starting from step 0, INCLUDING the warmup period, which causes the rate to be simultaneously rising (from warmup) and falling (from the decay schedule) and produces a confusing, unintended shape; warmup and the main decay schedule should be sequenced as two distinct phases, not blended from the start. A second common gap is choosing a schedule independent of batch size; a schedule tuned for one batch size (in particular its warmup LENGTH and the total number of decay steps) often needs to be re-tuned, not just have its peak learning rate rescaled, when batch size changes substantially.

Direct answer: Both queries are recursive common table expressions (CTEs) that walk edges(from_id, to_id) outward from a starting point, and both stop themselves the same way: by capping how many hops they'll take and by refusing to revisit a node already on the current path. Reachability additionally needs the hop limit as a business bound (how far counts as "reachable"), while cycle detection needs the visited-path check as the actual detection mechanism: a path that manages to return to its own starting node, without revisiting any node in between, is exactly what a cycle is.

Approach

Reachability: seed at the starting node, expand one edge at a time, stop at the hop limit or when a node already on the path would repeat.

WITH RECURSIVE reach(start_id, node_id, hops, visited) AS (
  SELECT from_id, to_id, 1, ARRAY[from_id, to_id]
  FROM edges WHERE from_id = :start_node

  UNION ALL

  SELECT r.start_id, e.to_id, r.hops + 1, r.visited || e.to_id
  FROM reach r
  JOIN edges e ON e.from_id = r.node_id
  WHERE r.hops < :hop_limit
    AND NOT (e.to_id = ANY (r.visited))
)
SELECT DISTINCT node_id FROM reach ORDER BY node_id;

Cycle detection: walk from every node; a path that gets back to its own starting node without revisiting an interior node along the way means that starting node sits on a cycle.

WITH RECURSIVE walk(start_id, node_id, hops, path) AS (
  SELECT from_id, to_id, 1, ARRAY[from_id, to_id]
  FROM edges

  UNION ALL

  SELECT w.start_id, e.to_id, w.hops + 1, w.path || e.to_id
  FROM walk w
  JOIN edges e ON e.from_id = w.node_id
  WHERE w.hops < 20                                     -- hard safety cap
    AND w.node_id <> w.start_id                          -- already closed the loop, stop expanding
    AND NOT (e.to_id = ANY (w.path[2:]))                  -- no interior node repeats (closing back to start is allowed)
)
SELECT DISTINCT start_id AS node_in_cycle
FROM walk
WHERE node_id = start_id
ORDER BY node_in_cycle;

Key points

• Both queries stop for two independent reasons: a hard hop/depth cap (a safety net that guarantees termination no matter what the data looks like) and a visited-path check (the actual logic that prevents wasted or incorrect re-exploration of a node already on the current path).
• In the cycle-detection query, w.node_id <> w.start_id in the WHERE clause is what stops a path from continuing to expand past the moment it closes a loop; without it, the recursion would keep circling the same cycle up to the hop cap instead of reporting the cycle once and moving on.
• w.path[2:] deliberately excludes the start node from the "no repeats" check, since returning to the start node is exactly the condition being detected, not a violation to reject.

Worked example

Edges: 1→2, 2→3, 3→4, 2→5, 5→2 (nodes 2 and 5 form a two-node cycle; 1, 3, 4 do not).

Verified in PostgreSQL. Reachability from node 1 within 3 hops returns {2, 3, 4, 5}: 1→2 (1 hop), 1→2→3 (2 hops) and 1→2→5 (2 hops), 1→2→3→4 (3 hops). Cycle detection returns {2, 5}: node 2's path 2→5→2 closes back to its own start in 2 hops without revisiting an interior node, and symmetrically for node 5; nodes 1, 3, and 4 never produce a path that returns to themselves.

graph LR
  1 --> 2
  2 --> 3
  3 --> 4
  2 --> 5
  5 --> 2

Complexity
Both queries are bounded by the hop/depth cap: a graph with average out-degree f and a cap of h hops explores at most O(f^h) paths from a given start node in the worst case (dense or highly-connected graphs), since a recursive CTE does not memoize shared sub-paths across different starting points. This is why the hop limit is not just a correctness safeguard against non-termination on a non-DAG (a graph that is not a directed acyclic graph, i.e. one that contains cycles); it is also the dominant cost control, since without it, reachability or cycle search on a real, densely-connected graph could expand far more paths than are useful before ever discovering a cycle.

Edge cases

• Isolated nodes with no outgoing edges: never appear as a node_id in either query's output; LEFT JOIN against a full node list first if downstream logic needs to see them explicitly as "reachability count 0."
• A self-loop (from_id = to_id on a single edge): immediately satisfies the cycle-detection condition at hop 1, correctly flagging that node without needing to traverse further.
• Multiple distinct cycles sharing a node: that node is correctly reported once via DISTINCT start_id, regardless of how many separate cycles it participates in.
• A very large, densely-connected graph: the exponential path-count risk above makes this recursive-CTE approach a poor fit at genuine graph-database scale; it is well suited to bounded, moderately-connected graphs like dependency graphs or organizational network data, not web-scale graphs.

Trade-offs & pitfalls

The same "bounded traversal with a visited-path guard" shape generalizes across several concrete domains beyond plain edges: transitive closure with a maximum path length cap (the reachability query above, generalized to report every reachable pair rather than just nodes reachable from one start), dependency-graph execution order (walking a build or task dependency graph to determine a valid processing sequence, where a cycle means the dependencies are unsatisfiable), a weighted-path variant where each edge carries a cost or distance and the traversal accumulates and limits by cumulative weight rather than by hop count, and a circular-payment or money-transfer framing used in fraud detection, where the identical cycle-detection query flags accounts that route funds back to themselves through a chain of transfers. The traversal and cycle-safety mechanics don't change across these; only what an edge represents does.

Direct answer

The gap that let this ship is a validation process that checked the model's outputs but never directly compared the staging and production feature pipelines against each other on the same inputs. The fix is to add an explicit parity check, a statistical test that compares the distribution of every feature as it lands in production against the distribution seen in staging (or training), gated as a hard blocker before blue traffic is ramped, not an optional dashboard someone glances at after the fact.

Structured elaboration

Where the parity check sits in the pipeline

flowchart LR
A[Training data] --> B[Preprocessing spec v1: versioned and hashed]
B --> C[Staging pipeline]
B --> D[Production pipeline]
C --> E[Feature distribution sample: staging]
D --> F[Feature distribution sample: prod]
E --> G[PSI distribution-diff test]
F --> G
G --> H{PSI within threshold}
H -->|No| I[Block blue rollout]
H -->|Yes| J[Shadow traffic on blue]
J --> K[Canary ramp with rollback gate]

1. Pipeline parity, verified, not assumed

• Preprocessing logic (scalers, encoders, tokenizers, normalization constants) has to be a single versioned artifact loaded identically by staging and production, not two independently maintained code paths that happen to be intended to match.
• Even with a shared artifact, a parity test still matters: run the same batch of real (or replayed) inputs through both environments and diff the outputs field-by-field. A silent mismatch (log1p applied in one place and log10 in another, a timezone offset in a time-based feature, a different null-fill value) shows up as a diff here even when both pipelines "look correct" individually.

2. Distribution-diff testing as an automated gate
This is the check that catches the class of bug in this scenario: nothing crashed, no schema changed, but the feature values are subtly on a different scale. Bucket each feature into bins and compare the proportion of production traffic landing in each bin against the expected (staging or training) distribution using the population stability index (PSI), a standard measure of how much a distribution has shifted:

where $a_i$ is the actual (production) proportion in bin $i$ and $e_i$ is the expected (staging) proportion. A PSI above roughly 0.2 is the common industry rule of thumb for "this is a material shift, not noise" and should block promotion.

3. Where this sits in the deployment pipeline

• Schema and contract tests (types, ranges, required fields) run first in CI, on every change, and catch structural breaks.
• The distribution-diff test runs against a production-like traffic sample before blue gets any real traffic, and again continuously once blue is in shadow mode, comparing shadow predictions and their input features against the green baseline on the same live traffic.
• Shadow mode: route a copy of real production traffic through blue without acting on its output, and compare blue's predictions and confidence distribution against green's on the same requests. A processing mismatch that changes the input distribution will usually show up as a shift in blue's output distribution too, not just its accuracy on a later-arriving label.
• Canary ramp (a few percent of real traffic) with an automatic rollback gate tied to the same distribution-diff and bias metrics, not just latency and error rate.

4. Governance around the pipeline itself

• A pre-deploy checklist with explicit sign-off from whoever owns the data/feature pipeline, separate from whoever owns the model, since this bug sits exactly at the seam between those two areas of ownership.
• An automated diff tool that flags any change to normalization constants, encoders, or tokenizer vocabulary as a reviewed, called-out change, not a side effect buried in an unrelated pull request.

Worked example

Suppose a feature (say, a scaled transaction amount) has this expected (staging/training) distribution across four bins, and this is what's actually observed in production after the scaling mismatch:

A PSI of 0.216 clears the ~0.2 "material shift" threshold, which is exactly the kind of quiet mass-shift toward the "very high" bin a scaling mismatch (for example, a log1p transform in staging versus a log10 transform in production) produces. Wired into the promotion pipeline as a hard gate, this catches the bug before blue takes real traffic, instead of after clinicians, users, or downstream consumers see biased output.

Trade-offs & pitfalls

• Schema tests alone are not enough: this bug passed every type and range check because nothing was structurally wrong, only the values were subtly rescaled. The distribution-diff test is the piece that closes that gap, and it's easy to skip because it takes real engineering effort to define good bins and thresholds per feature.
• Setting the PSI (or equivalent) threshold too loose defeats the purpose; setting it too tight creates alert fatigue and teams start ignoring it, which is its own failure mode. The threshold needs to be tuned per feature against historical natural variation, not copy-pasted as a single global number.
• Comparing distributions once at deploy time and never again misses drift that develops after a clean launch; the same test needs to run continuously as a monitoring signal, not just as a pre-deploy gate.
• Bias specifically (as opposed to a generic accuracy regression) requires checking the diff broken out by subgroup, not just in aggregate, since a shift that is invisible in the pooled distribution can be concentrated in one subgroup.
• Rollback has to be automatic and fast (traffic-weight based, not a redeploy), or the gate finding the problem doesn't actually limit the blast radius.

Direct answer

Walk the array once while maintaining a hash map from value to the index where you first saw it. For each element x at index i, check whether target - x is already a key in the map before inserting x itself; if it is, you've found the pair in that same pass. That gives $O(n)$ average time using $O(n)$ extra space for the map, which is the best achievable without assuming the array is sorted, since you need to have looked at the data at least once to guarantee you haven't missed a valid pair; what you trade for that speed is the extra memory the map uses.

Approach

• Keep a dictionary seen mapping each value to the first index it appeared at.
• For each index i and value x, compute need = target - x and check seen for need before adding x to seen; checking first is what prevents pairing an element with itself when target == 2 * x.
• Return the pair of indices the moment a match is found; a single pass suffices.

from typing import List, Optional


def two_sum(nums: List[int], target: int) -> Optional[List[int]]:
    """Returns indices [i, j] such that nums[i] + nums[j] == target.
    Average O(n) time, O(n) space."""
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        if x not in seen:
            seen[x] = i
    return None


if __name__ == "__main__":
    print(two_sum([2, 7, 11, 15], 9))   # [0, 1]
    print(two_sum([3, 3], 6))            # [0, 1]
    print(two_sum([1, 2, 3], 100))       # None

Running this prints [0, 1], [0, 1], and None. In the second case, target 6 with nums = [3, 3]: at i=0, need=3 isn't in seen yet, so 3 is stored at index 0; at i=1, need=3 is now in seen, giving [0, 1], correctly using two distinct indices for the same value rather than pairing index 0 with itself.

Key points

• Checking for the complement before inserting the current value is what stops the algorithm from matching an element with itself when target equals twice that element's value.
• "Average" $O(n)$, not worst-case, is the honest label: each hash map operation is $O(1)$ on average given a reasonably distributed hash, but an input engineered to collide against the hash function could in principle degrade individual lookups, which is a real (if unusual) concern in adversarial settings.
• The streaming variant, where you can't store the whole array up front, still needs $O(n)$ auxiliary memory for values seen so far, since you must remember what's already been scanned; there's no way around that memory cost unless an additional constraint (like a bounded value range) lets you swap the hash map for a fixed-size bitset.

Complexity

Time: $O(n)$ average (n hash map operations, each $O(1)$ average). Space: $O(n)$ for the seen map.

Edge cases

• No valid pair exists: the function should signal that clearly (returning None here, or raising, depending on the calling convention) rather than silently returning a wrong pair.
• Duplicate values that sum to the target: handled correctly by storing the first occurrence and checking the complement before inserting the current value.
• Negative numbers: work without special-casing, since dictionary keys and arithmetic on target - x don't assume non-negative values.
• An empty array or an array with fewer than two elements: no valid pair is possible.

Direct answer

Three common statistical methods for flagging outliers in a numeric column are the z-score (how many standard deviations from the mean a value is), the interquartile-range (IQR) fence (flag anything outside 1.5x the IQR beyond the 25th/75th percentile), and a robust alternative based on the median absolute deviation (MAD), which is far less sensitive to the very outliers you are trying to detect than either of the first two.

Structured elaboration

• Z-score: assumes an approximately normal distribution; both the mean and standard deviation used in its own formula are themselves distorted by the outlier being measured, which weakens its sensitivity exactly when outliers are large or numerous (a masking effect). Computational cost: cheapest of the three, the mean and standard deviation are both computed in a single pass over the data, O(n) time and O(1) extra memory, and this single pass is trivially streamable (both can be updated incrementally as new values arrive) even on a huge table.
• IQR fence: distribution-free and robust to a small number of extreme outliers since it is based on percentiles, but the fixed 1.5x multiplier is a heuristic that can flag too aggressively on a genuinely skewed (not just outlier-contaminated) distribution. Computational cost: needs the 25th and 75th percentiles, which in the exact case requires a sort or a selection algorithm, O(n log n) for a full sort or O(n) on average with a quickselect-style approach; at very large scale this is usually done with an approximate-percentile data structure (a sketch) rather than an exact sort, trading a small amount of precision for bounded memory.
• MAD-based modified z-score: uses the median and median absolute deviation instead of the mean and standard deviation, both of which are far more robust to outliers, making it the most reliable of the three for a data-quality context where you specifically expect the sample to contain what you're testing for. Computational cost: needs the median twice, once for the data itself and once for the absolute deviations from that median, so it costs roughly the same as the IQR fence (a sort or selection step, generally O(n log n) or O(n) with quickselect), done twice rather than once, and more than the single-pass z-score. MAD itself can also mislead: on a sample with many tied or duplicate values, or a very small or coarsely-discretized sample, the median absolute deviation can collapse toward zero (more than half the values sitting exactly at the median), which makes the modified z-score's denominator tiny and inflates every deviation into an apparent extreme outlier, the opposite failure mode from the mean/std masking effect above but just as capable of misleading.

Worked example

For the sample [12, 14, 13, 15, 12, 14, 13, 90, 15, 13, 12, 14] (one clear outlier, 90), computed by execution: mean = 19.75, std = 22.15, giving the outlier a z-score of only 3.17, barely over the conventional threshold of 3, because the outlier itself has inflated the mean and standard deviation used to judge it. The IQR fence (Q1=12.75, Q3=14.25, fence = [10.5, 16.5]) correctly flags 90 as outside the fence. The MAD-based modified z-score uses the formula $0.6745 \times \frac{|x - \text{median}|}{\text{MAD}}$ (the constant 0.6745 rescales MAD so it is comparable to a standard deviation under a normal distribution); plugging in median=13.5, MAD=1.0, and x=90 gives $0.6745 \times \frac{|90 - 13.5|}{1.0} = 0.6745 \times 76.5 \approx 51.6$, dramatically clearer than the z-score's 3.17, because the median and MAD are barely moved by a single extreme value. This gap between 3.17 and 51.6 for the exact same outlier is the concrete illustration of why the z-score is fragile in exactly the situation it is meant to catch.

Trade-offs and pitfalls

Z-score is misleading on a small sample or a sample with more than one or two outliers, since the mean and standard deviation degrade fastest exactly when you need them most; IQR is safer but its 1.5x multiplier is a heuristic, not a statistically-derived constant, and can over-flag a genuinely skewed (e.g. revenue, latency) distribution that is not actually anomalous, just non-normal. A practical rule: default to the MAD-based method for automated production monitoring, and reserve the z-score for exploratory, one-off analysis where a human is looking at the output.