Spotify Machine Learning Engineer Interview Preparation Guide - Junior Level

Situation: When preparing to deploy a new ML model, I run it in shadow (dark launch) mode: receiving a copy of live requests but not affecting production decisions: to validate behavior before switching traffic.

How shadow testing helps:

• Safe realism: the candidate sees real inputs (including rare edge cases) and exposes mismatches that synthetic tests miss.
• Performance profiling: measures inference latency, CPU/GPU/memory use, and throughput under production load, identifying resource bottlenecks.
• Behavioral comparison and root-cause detection: by logging paired outputs (baseline vs candidate) for each request, you can compute per-request deltas, slice analysis (user segments, feature ranges), and trace back to features or input patterns causing regressions. Storing contextual logs and sample inputs enables replay for debugging and model explainability tools to inspect why predictions diverged.

How to run it (concise steps):

• Mirror production requests to candidate model synchronously or asynchronously.
• Never let candidate responses affect user-facing systems.
• Persist timestamps, inputs, baseline and candidate outputs, prediction confidences, and resource metrics.
• Run automated checks and alerts on divergence thresholds; sample and replay failures to dev pipelines.

Practical concerns: PII and sample rate

• Handling PII: shadow mode mirrors real production requests, so whatever PII lives in the user-facing request (names, emails, account IDs, free-text fields) is present in the shadow logs too, even though the shadow output never reaches the user. Strip or hash identifying fields (or replace them with a stable hashed key that still lets you reproduce and join the delta record without the raw PII) before persisting shadow logs, and give the shadow log store the same access-control, retention-window, and encryption-at-rest treatment as the production logs it copies from: it is a diagnostic system, not a lower-security one.
• Choosing a sample rate: because shadow predictions never affect the user, mirror 100% of production traffic when compute cost allows. The risk side of the cost/power trade-off that a live A/B test worries about (real users seeing a worse experience) does not apply to shadow mode, so the constraint is money and infra headroom, not user risk. When cost forces sampling, size the fraction the same way you would size a statistical test: pick the comparison metric you care about most (e.g., the delta in false-positive rate between baseline and candidate), estimate its expected effect size and variance from historical data, and compute the minimum number of paired requests needed for around 80% power at your chosen significance level. For example, if you expect roughly a 2-percentage-point difference in false-positive rate against a baseline rate near 10%, a standard two-proportion power calculation needs on the order of 3,500 to 4,000 paired requests per arm to detect that reliably at 80% power (alpha=0.05, two-sided). A service handling 500,000 requests/day clears that with well under a 1% sample rate within a single day; a lower-traffic service might need to mirror 100% for a week or more to accumulate enough paired comparisons.

Key metrics to compare (baseline vs shadow):

• Prediction-level:
  • Prediction distribution shifts (class probabilities, score histograms)
  • Top-k accuracy / precision / recall / F1 (if labels available eventually)
  • Confusion matrix / per-class error rates, false positives/negatives
  • Calibration (reliability diagrams, Brier score)
  • Confidence / entropy changes and % low-confidence predictions
• Latency & reliability:
  • P50/P95/P99 inference latency, tail latency, error rates, timeouts
  • Throughput and request drop/failure counts
• Resource & cost:
  • CPU/GPU utilization, memory, I/O, cost per request
• Data/robustness:
  • Feature importance shifts, input covariate drift, distributional distance (KL, JS, population stability index: all three measure how much a distribution, such as a feature's values or the candidate's score histogram, has shifted between two samples. KL, Kullback-Leibler, divergence measures how much information is lost approximating one distribution with the other and is asymmetric; JS, Jensen-Shannon, divergence is a symmetric, bounded version of the same idea; PSI, population stability index, buckets the distribution and sums a simple weighted log-ratio per bucket, and is the one most commonly used in production because it comes with widely-adopted rule-of-thumb alert thresholds: PSI below 0.1 is stable, 0.1 to 0.25 is a moderate shift worth investigating, and above 0.25 is a significant shift)
• Business and downstream:
  • Proxy business metrics (e.g., click-through, conversion uplift, fraud alerts) from a delayed ground-truth pipeline or shadow-analysis heuristics

What I watch for and actions:

• Small global metric differences warrant deeper slice analysis. Large regressions or tail latency increases trigger rollback of candidate rollout.
• Use alerts for delta thresholds (e.g., >2% increase in false positives, >50ms P95 latency). Reproduce failures by replaying logged requests, inspect features, model explainability outputs, and iterate on model or preprocessing.

Result: Shadow testing provides realistic, low-risk validation: catching correctness, performance, and operational issues early: so when the model goes live you’ve minimized surprises and regression risk.

Direct answer. A silent process exit or an ECC-error-and-kernel-retry pattern in a long-running job needs to be triaged in a specific order, cheapest and most-common causes first, because chasing a hardware explanation before ruling out software config wastes the most time when the cause turns out to be mundane.

The vocabulary this triage runs on. A bit flip is a single stored bit spontaneously changing from 0 to 1 or back, from electrical noise, a stray particle, or a degrading memory cell. ECC (error-correcting code memory) stores extra check bits alongside every word so the hardware can DETECT that corruption and, for a single flipped bit, REPAIR it in place before anything reads it; it also keeps a running per-device count, which is the only reason any of this is visible from software. A correctable error is one ECC repaired: your numbers were fine. An uncorrectable error is multi-bit corruption ECC could detect but not repair: the data was wrong, or the process was killed to stop it being used. NCCL is NVIDIA's library for GPU-to-GPU collective communication, and its logs show which rank a collective stalled on. dmesg is the OS kernel's log, where an out-of-memory kill is recorded even when the application itself logs nothing. A SIGKILL is the termination signal a process cannot catch or handle, so it gets no chance to run cleanup or print a stack trace, which is exactly why an OOM kill presents as a silent exit.

Order of investigation.

1. Resource limits and OOM kills first. Check whether the process was actually OOM-killed by the OS/container orchestrator (a silent SIGKILL with no application-level stack trace looks identical to a mysterious crash unless you specifically check dmesg or the container runtime's exit-reason field). This is the single most common cause of a "silent" exit and the cheapest to rule in or out.
2. NCCL and network errors next, since a hung or failed collective communication in distributed training frequently manifests as one node appearing to silently exit while the real cause is a network partition or a peer timing out.
3. Driver/CUDA compatibility. Check whether all nodes in the cluster are running identical driver and CUDA versions; a mismatched driver on one freshly-provisioned node is a common, boring cause of node-specific instability that looks alarming until you check the versions.
4. Only then, treat ECC error counters as meaningful signal, since the driver typically exposes a persistent per-GPU ECC count (nvidia-smi -q -d ECC gives both the volatile and the aggregate counters); a rising, non-zero count strongly implicates the device's MEMORY. Be precise about what the other direction buys you, because this is where the triage most often goes wrong: ECC covers memory cells and nothing else, so a flat zero count rules out a memory fault, not hardware in general. Thermal or power throttling, a degrading NVLink or PCIe path, and a failing compute unit all produce exactly this symptom (throughput degradation with kernel retries) while leaving every ECC counter at zero. So when ECC is clean, read the counters that cover those paths instead: nvidia-smi -q -d TEMPERATURE,POWER,PERFORMANCE for clock throttling and its stated reason, the NVLink CRC and replay counters, and the PCIe replay count. Only when THOSE are also clean have you ruled hardware out.

Where kernel retries fit. A kernel retry in the logs means a GPU kernel launch or memory operation failed and the driver re-issued it. It is a symptom, not a cause, and its diagnostic value is in what it excludes: retries do not accompany an OOM kill or an ordinary application bug, so seeing them lets you move past step 1 quickly. They DO accompany both a degrading device and a driver-level fault, so they cannot separate those two on their own, which is what steps 3 and 4 are for. They also explain the throughput half of the symptom: every retry costs wall-clock time, so a rising retry rate reads as a gradual mid-run slowdown on one node with no error surfacing anywhere.

Deciding evacuate versus continue with reduced capacity. Four cases, each with its own action and its own reason:

counter state                          action                    why THIS row
any uncorrectable error, even one      evacuate immediately,     the device has already produced
                                       do not wait for a         data that was wrong and could
                                       second one                not be repaired; correctness of
                                                                 the run is already in question
uncorrectable zero, correctable        drain at the next         a rising correctable rate is the
RISING on one device                   checkpoint boundary;      leading indicator of a degrading
                                       stop scheduling new       cell; the driver will retire the
                                       work there                row eventually, and you would
                                                                 rather that happen between runs
uncorrectable zero, correctable        continue with reduced     ECC repaired every error, so the
non-zero but FLAT                      expectations; keep the    numbers are correct; the cost is
                                       counters on a dashboard   throughput, not correctness
ECC flat at zero across the             memory fault is ruled     ECC counts every flip it sees in
incident window                         out; check throttling,    memory, so silence is real evidence
                                        NVLink/PCIe replay and    about memory and no evidence at all
                                        clock counters, then      about clocks, links or compute
                                        go back to steps 1-3

The threshold for "rising" is a policy choice you calibrate per fleet rather than a universal constant, and the robust form is comparative rather than absolute: on the same job, on the same hardware generation, one device's correctable count climbing while its peers stay flat is the signal, regardless of the raw number. If you want a starting default, treat a non-zero pending row-remap count, or correctable errors accumulating faster than a handful per hour on one device while its peers sit at zero, as "rising" and drain it. Whichever rule you pick, write it down before the incident, because during one everything looks like it might be rising.

And in every continue case, the precondition is checkpointing frequent enough that losing that node's progress would not be catastrophic. Without that, "continue" is not a lower-risk option, it is just a deferred one.

Preserving scientific validity of a long experiment. Whichever path you choose, log the incident (which node, when, what the counters showed) alongside the experiment's own metadata. A result produced on a cluster with an active, unresolved hardware issue on one node should be flagged as such when reported, not presented with the same confidence as a clean run. The reason is specific: a bit flip that ECC did not catch, or one that landed during a window the counters do not cover, changes a single number in a weight or an activation without crashing anything and without appearing in any log, so it can nudge a result in a direction nobody can reconstruct after the fact. That is the failure mode the flag is protecting against, not the visible crash.

The idea in plain words

A pairwise ranker is a model that learns a score $f(q, d)$ for a query $q$ and a candidate $d$ (here, a listing) so that, for a training pair $(a, b)$ where the user preferred $a$ over $b$ for the same query, $f(q, a) > f(q, b)$. A common loss is the logistic loss on the score gap:

where $\sigma$ is the sigmoid function. The model never sees an absolute label, only "a beat b". So the whole job is to turn a log of (query, shown ranking, clicks, bookings) into pairs that are (1) comparisons the user actually made, (2) taken within one query and one shown list, and (3) not just a copy of what the old ranker already did.

Step 1: order the signals, then form pairs only where the order is informative

Bookings are rarer and more costly than clicks, so they are stronger evidence. Rank the funnel stages: booked > clicked but not booked > examined and skipped > never examined. Pairs are formed only between items of different stages, and only for items that were plausibly examined (that the user had a real chance to look at).

Pairs are only ever formed inside one search (same query, same filters, same date range), because relevance is relative to the query and scores from different queries are not comparable.

Step 2: sampling negatives

• Skipped-above negatives come first: the user passed them, so they are the best-evidenced negatives.
• Next-below-the-click items (the one or two positions right after the last click) are a reasonable extension, because users often glance a little past what they click.
• Hard negatives are negatives that look like good answers: items the current ranker scored highly that the user did not choose. (A negative is the less-preferred item in a pair, and an easy negative is one the model already ranks far below.) Hard negatives teach the most, but they also contain the most false negatives (listings the user would have liked but did not get to, which the pair wrongly labels as worse), so cap how many you use and weight them below the evidenced ones.
• Random negatives from other queries are cheap, but they teach only coarse relevance (wrong city, wrong dates), because the model already separates those. Keep a small share for stability.
• Cap pairs per query (for example sample at most a fixed number of pairs from each search), or weight each pair by one over the number of pairs its search produced. Otherwise a popular query with a long list of clicks supplies most of the gradient (the update signal that trains the model).

Step 3: the biases to correct

1. Position bias. Users examine top positions more, so a click is partly "it was on top". Correct with inverse propensity weighting (IPW): weight a pair by $1 / p_{\text{exam}}(\text{position of the clicked item})$, where $p_{\text{exam}}$ is the probability the position is examined, estimated from a small slice of traffic with randomly ordered results. A click at a position that is examined half the time counts double (weight 2); a click at a position examined one time in ten would count ten times and is clipped (for example at 5) so one deep click does not dominate. The by-hand example below works these weights. Skip-above pairs also remove much of this bias by construction, because they compare against items the user passed.
2. Selection (exposure) bias. Only items the old ranker showed can be clicked, so the pairs inherit the old ranker's blind spots. A small randomized slice, or exploration slots (positions reserved for items chosen at random or by an exploration policy), is the only way to see items the old ranker never surfaced.
3. Presentation bias and trust bias. A photo, a price badge or a "popular" label draws clicks independent of fit: include presentation features in the model, or evaluate with them held fixed. Trust bias is separate: users tend to believe that what the ranker put on top is better, so they click high results even after looking at them and finding them no better than the ones below, and position-based weights alone do not remove that. Comparing against the randomized slice is the check.
4. Label delay. Bookings arrive days later. Wait out a fixed attribution window (the period after a search during which a booking is credited to it) before building labels for a day, or recent days will look click-heavy and booking-poor.
5. Leakage in the split. Split train and validation by time and by user or query group. Pairs from the same search in both sets inflate the validation score.

Worked example: what each pairing rule actually produces

One search by hand. A search shows 8 listings top to bottom. The user clicks positions 2 and 4 and books position 2. Click over all unclicked pairs each of the 2 clicks with each of the 6 unclicked listings, 12 pairs. Click over skipped-above keeps only unclicked listings that sit above the click: position 2 beats 1, and position 4 beats 1 and 3, which is 3 pairs. Booked over clicked-only pairs the booking with the click that did not convert: position 2 beats 4, one pair. The weights below use illustrative examination probabilities (the chance a user looks at each position; in practice estimated from randomized-order traffic). A pair is weighted by 1 over the examination probability of the clicked item's position, then clipped at 5.

# One search, 8 listings shown top to bottom (positions 1 to 8). The user clicked positions 2 and 4 and booked position 2.
clicked, booked = {2, 4}, {2}
positions = range(1, 9)
p_exam = {1: 1.0, 2: 0.8, 3: 0.6, 4: 0.5, 5: 0.4, 6: 0.3, 7: 0.2, 8: 0.1}   # illustrative examination probabilities

all_unclicked = [(c, o) for c in sorted(clicked) for o in positions if o not in clicked]
skipped_above = [(c, o) for c, o in all_unclicked if o < c]
booked_over_clicked = [(b, c) for b in sorted(booked) for c in sorted(clicked - booked)]
print("click over all unclicked:", len(all_unclicked), "pairs")
print("click over skipped-above:", skipped_above)
print("booked over clicked-only:", booked_over_clicked)

print("clicked position, p_exam, weight 1/p_exam, clipped at 5")
for pos in [2, 4, 7, 8]:
    w = 1 / p_exam[pos]
    print(f"{pos}, {p_exam[pos]}, {w:.2f}, {min(w, 5):.2f}")

Output:

click over all unclicked: 12 pairs
click over skipped-above: [(2, 1), (4, 1), (4, 3)]
booked over clicked-only: [(2, 4)]
clicked position, p_exam, weight 1/p_exam, clipped at 5
2, 0.8, 1.25, 1.25
4, 0.5, 2.00, 2.00
7, 0.2, 5.00, 5.00
8, 0.1, 10.00, 5.00

The click at position 4 gets weight 2.00 because users look at that position half the time, so each such click stands in for two. A click at position 8 would get 10.00 and is clipped to 5.00.

At scale, in a simulation. A simulated log: 4,000 searches of 8 listings each. True relevance is known only because this is a simulation. The shown order comes from a noisy old ranker, and the user scans top-down, clicks with probability equal to the listing's relevance, usually stops after a click, and sometimes gives up after a skip. Examination therefore falls with depth only through that stopping rule; there is no separate per-position examination probability, so the weights from the by-hand example are not tested here. This is a stand-in for a real log, where true relevance is not observable. In the table, agrees with true rel is the share of a rule's pairs in which the preferred item really has the higher relevance, and preferred shown higher is the share in which the preferred item sat above the other one in the displayed list. The code loops over each clicked or booked position j and each other position i, forms a pair under each rule that applies, and tallies those two shares.

import numpy as np

rng = np.random.default_rng(0)
N_SESSIONS, LIST_LEN = 4000, 8

def simulate_session():
    rel = rng.uniform(0, 1, LIST_LEN)                      # true relevance of 8 candidate items
    order = np.argsort(-(rel + rng.normal(0, 0.35, LIST_LEN)))  # shown ranking: a noisy old ranker
    rel = rel[order]                                        # rel[j] = true relevance at shown position j
    clicked = np.zeros(LIST_LEN, bool)
    booked = np.zeros(LIST_LEN, bool)
    for j in range(LIST_LEN):                               # top-down scan; the user examines until they stop
        if rng.random() < rel[j]:
            clicked[j] = True
            booked[j] = rng.random() < rel[j]
            if rng.random() < 0.6:                          # usually stops after a click
                break
        elif rng.random() > 0.85:                           # sometimes gives up after a skip
            break
    return rel, clicked, booked

pos_ok = {k: 0 for k in ["click > all unclicked","click > skipped above","booked > clicked-only"]}
stats = {"click > all unclicked": [0, 0],
         "click > skipped above": [0, 0],
         "booked > clicked-only": [0, 0]}
sessions_with_pair = {k: 0 for k in stats}
for _ in range(N_SESSIONS):
    rel, c, b = simulate_session()
    found = {k: False for k in stats}
    for j in range(LIST_LEN):
        if c[j]:
            for i in range(LIST_LEN):
                if not c[i]:
                    stats["click > all unclicked"][0] += 1
                    stats["click > all unclicked"][1] += rel[j] > rel[i]
                    pos_ok["click > all unclicked"] += j < i
                    found["click > all unclicked"] = True
                    if i < j:
                        stats["click > skipped above"][0] += 1
                        stats["click > skipped above"][1] += rel[j] > rel[i]
                        pos_ok["click > skipped above"] += j < i
                        found["click > skipped above"] = True
        if b[j]:
            for i in range(LIST_LEN):
                if c[i] and not b[i]:
                    stats["booked > clicked-only"][0] += 1
                    stats["booked > clicked-only"][1] += rel[j] > rel[i]
                    pos_ok["booked > clicked-only"] += j < i
                    found["booked > clicked-only"] = True
    for k in found:
        sessions_with_pair[k] += found[k]

print(f"{'rule':24s} {'pairs':>6s} {'sessions':>8s} {'agrees with true rel':>21s} {'preferred shown higher':>23s}")
for k, (n, ok) in stats.items():
    print(f"{k:24s} {n:6d} {sessions_with_pair[k]:8d} {ok / n:21.3f} {pos_ok[k] / n:23.3f}")

Output:

rule                      pairs sessions  agrees with true rel  preferred shown higher
click > all unclicked     34925     3771                 0.833                   0.920
click > skipped above      2784     1154                 0.653                   0.000
booked > clicked-only      1154      663                 0.802                   0.633

Reading the table:

• The "click over all unclicked" rule gives 34,925 pairs, about 12.5 times as many as the 2,784 from "click over skipped-above". Its agreement with true relevance is higher (0.833 against 0.653), but 92.0% of its pairs have the preferred item already sitting higher in the list. A model can score well on these pairs by learning to reproduce the old ranker (position, old score, anything correlated with them).
• Every skip-above pair contradicts the display order (the preferred item is shown LOWER, so the last column is 0.000). These pairs carry information the old ranker did not have. Their lower raw agreement is expected: they compare an item the user clicked with items the user probably looked at, so the relevance gaps are smaller than against an item that was never seen. A rule's agreement with truth is therefore not the yardstick; the value of its pairs shows up in the model trained on them, which the next program measures.
• Booked-over-clicked-only gives 1,154 pairs from 663 searches, 0.802 agreement and 63.3% of pairs consistent with display order: a cleaner signal, available in fewer searches.

Training on the pairs. A second program trains a pairwise logistic model on each set of pairs and scores the result against true relevance on fresh lists. Each listing has two features: a noisy readout of its relevance, and the old ranker's own score (the number that decided the display order). The model learns one weight per feature from the feature differences of the pairs. Agreement is the share of fresh within-list item pairs that the model orders as true relevance does. Using the old score as a feature is the setting where pair bias hurts most; the same effect appears whenever position or old-score signals reach the model.

import numpy as np
from sklearn.linear_model import LogisticRegression

L = 8
def session(rng):
    rel = rng.uniform(0, 1, L)                              # true relevance (known only in a simulation)
    eps = rng.normal(0, 0.35, L)
    order = np.argsort(-(rel + eps))                        # old ranker shows items by its score rel + eps
    rel, old_score = rel[order], (rel + eps)[order]
    readout = rel + rng.normal(0, 0.3, L)                   # feature 1: a noisy readout of relevance
    X = np.stack([readout, old_score], 1)                   # feature 2: the old ranker's own score
    clicked = np.zeros(L, bool); booked = np.zeros(L, bool)
    for j in range(L):                                      # same top-down user as the first program
        if rng.random() < rel[j]:
            clicked[j] = True; booked[j] = rng.random() < rel[j]
            if rng.random() < 0.6: break
        elif rng.random() > 0.85: break
    return rel, X, clicked, booked

rng = np.random.default_rng(0)
P = {"click > all unclicked": [], "click > skipped above": [], "booked > clicked-only": []}
for _ in range(4000):
    rel, X, c, b = session(rng)
    for j in range(L):
        if c[j]:
            for i in range(L):
                if not c[i]:
                    P["click > all unclicked"].append(X[j] - X[i])
                    if i < j: P["click > skipped above"].append(X[j] - X[i])
        if b[j]:
            for i in range(L):
                if c[i] and not b[i]: P["booked > clicked-only"].append(X[j] - X[i])
P = {k: np.array(v) for k, v in P.items()}
sub = np.random.default_rng(1)
tenth = P["click > all unclicked"][sub.random(len(P["click > all unclicked"])) < 0.1]
sets = {"click > all unclicked": P["click > all unclicked"],
        "click > skipped above": P["click > skipped above"],
        "booked > clicked-only": P["booked > clicked-only"],
        "skipped-above + booked": np.vstack([P["click > skipped above"], P["booked > clicked-only"]]),
        "skipped-above + booked + 10% of all": np.vstack([P["click > skipped above"], P["booked > clicked-only"], tenth])}

def fit(D):                                                 # pairwise logistic model: w . (x_a - x_b)
    X = np.vstack([D, -D]); y = np.r_[np.ones(len(D)), np.zeros(len(D))]
    return LogisticRegression(fit_intercept=False, C=100).fit(X, y).coef_[0]

def agreement(w, n=3000):                                   # share of fresh within-list item pairs ordered as true relevance orders them
    g = np.random.default_rng(5); ok = tot = 0
    for _ in range(n):
        rel, X, _, _ = session(g); s = X @ w
        for i in range(L):
            for j in range(i + 1, L):
                tot += 1; ok += (s[i] > s[j]) == (rel[i] > rel[j])
    return ok / tot

print(f"{'training pairs':38s} {'n pairs':>8s} {'weight readout':>15s} {'weight old score':>17s} {'agreement':>10s}")
for k, D in sets.items():
    w = fit(D)
    print(f"{k:38s} {len(D):8d} {w[0]:15.2f} {w[1]:17.2f} {agreement(w):10.4f}")
print(f"{'reference: readout only':38s} {'':8s} {1.0:15.2f} {0.0:17.2f} {agreement(np.array([1.0, 0.0])):10.4f}")
print(f"{'reference: equal weights':38s} {'':8s} {1.0:15.2f} {1.0:17.2f} {agreement(np.array([1.0, 1.0])):10.4f}")

Output:

training pairs                          n pairs  weight readout  weight old score  agreement
click > all unclicked                     34341            1.25              4.95     0.7576
click > skipped above                      2707            1.10           -103.02     0.2755
booked > clicked-only                      1043            1.50              0.99     0.7932
skipped-above + booked                     3750            1.60             -2.78     0.3987
skipped-above + booked + 10% of all        7193            1.47              0.77     0.7913
reference: readout only                                    1.00              0.00     0.7498
reference: equal weights                                   1.00              1.00     0.7927

Reading it: the readout alone gives 0.7498 and the equal-weight reference 0.7927. Training on every click-over-unclicked pair gives 0.7576 because 92% of those pairs are already ordered by the old score, so the model leans on the old score (weight 4.95) instead of the readout. Training on skip-above pairs alone is far worse than chance (0.2755): every one of those pairs has the preferred item displayed lower, so the old score looks like a perfect reverse predictor (the very large negative weight is that perfect separation) and the model learns to rank by it backwards. Booked-over-clicked alone reaches 0.7932, but from only 1,043 pairs. Skip-above plus booked together is still dominated by the skip-above pairs (0.3987). Adding a 10% slice of click-over-unclicked pairs, so that display order is no longer a perfect predictor of the label, brings it to 0.7913, near the equal-weight reference. In this run the rows order as follows: skip-above alone is lowest, skip-above plus booked is next, all-clicks sits just above the readout-only reference, and booked-only and the mixture sit near the equal-weight reference.

How to judge the pairs on a real log, where true relevance is not observable: (1) the share of pairs the old order already gets right, because a high share means the pairs mostly teach the old ranker; (2) agreement of the trained model with clicks and bookings on a slice of traffic whose order was randomized, where position cannot explain them; (3) an online test on bookings per search. An agreement of 0.653 for a rule is a statement about its labels, where a coin flip scores 0.5; what matters is whether the trained model beats the readout alone, as it does here only when the pair set points both ways relative to the display order.

A reasonable recipe is therefore: skip-above and booked-over-clicked pairs as the evidenced core, plus a down-weighted slice of click-over-unclicked pairs (or the old score and position kept out of the model's inputs), IPW-clipped weights, a limited share of hard negatives at a lower weight, and a per-search cap.

Common mistakes

• Pairing a click with every unclicked item and treating the result as clean labels.
• Forming pairs across different queries.
• Reporting offline pair accuracy on a validation set built with the same rule as training, which only measures agreement with the old ranker.
• Using unclipped IPW weights, which makes a few deep clicks dominate training.
• Training on skip-above pairs alone while the old ranker's score or position is an input: every pair is ordered against the display, and the model learns the display order backwards.

Running the code

python one_search.py
python pair_rules.py
python train_on_pairs.py

Python 3.12, numpy 2.1.3, scikit-learn 1.5.2. The three listings above are the three scripts in order; seeds are fixed inside each.

Direct answer: A supervised entity-embedding approach for a very high-cardinality categorical feature (up to tens of millions of unique IDs) needs a neural architecture that maps each ID to a learned dense vector via an embedding lookup table, trained jointly with the downstream task, with the practical engineering challenge being memory budgeting and sharding that embedding table, and defining sensible behavior for cold-start and rare IDs.

Structured elaboration:
The architecture: an embedding layer maps each category's integer index to a dense vector, which is then concatenated with the model's other inputs and trained end-to-end against the actual supervised objective, so the embedding learns to place IDs with similar downstream behavior close together in the vector space, entirely as a byproduct of the training objective, not a separately-specified similarity criterion.

Choosing the embedding dimensionality: a common starting rule of thumb sizes the dimension as roughly the fourth root of the cardinality (dimension is approximately cardinality^0.25), often capped at some practical maximum (for example 256 or a few hundred) so the table stays within a fixed memory budget regardless of how the cardinality grows; for 50 million unique IDs this rule suggests roughly 80-90 dimensions as a reasonable starting point, not the many hundreds of dimensions a smaller-cardinality categorical might not even need. In practice this starting value is then tuned against validation performance: too small a dimension underfits (can't represent enough distinct behavior patterns), too large wastes memory and can overfit rare IDs, so the rule of thumb gives a sane initial value to sweep around rather than a value to accept blindly.

Memory budgeting: at tens of millions of unique IDs, even a modest embedding dimension multiplies into a very large total table size (dimension times cardinality times bytes-per-value), which typically necessitates SHARDING the embedding table across multiple machines (each shard owning a range or hash-partition of the ID space), with the model's forward pass needing to route each ID's lookup to the correct shard.

Handling cold-start and rare IDs: an ID with very few training examples gets an unreliable, poorly-estimated embedding if trained the same as a common ID; standard mitigations include a shared "unknown/rare" embedding for IDs below a frequency threshold, or explicit regularization pulling rare IDs' embeddings toward a population average rather than letting them drift based on too little data. Online updates (adding a genuinely brand-new ID after initial training) need a defined policy, typically initializing new IDs at the shared "unknown" embedding until enough interaction data accumulates to justify a dedicated one.

Worked example: For 50 million unique user IDs feeding a recommendation model, the fourth-root rule of thumb (50,000,000^0.25 is approximately 84) suggests starting around 80-90 dimensions, which is then validated (and adjusted up or down) against held-out recommendation quality rather than used blindly; a memory-budget check confirms this is workable (roughly 84 floats x 4 bytes x 50 million IDs is on the order of 17 GB for the full table, which is exactly why sharding across several machines by a hash of the user ID is necessary at this scale). Reserving a shared fallback embedding for any user ID with fewer than a small threshold of historical interactions lets the system scale to that cardinality without either an infeasible single-machine memory footprint or unreliable per-user vectors for the long tail of rarely-seen users.

Trade-offs and pitfalls: Exporting the trained embeddings for use in a downstream tree-based or linear model (rather than only within the original neural architecture) requires freezing them at a specific training checkpoint; if the neural model is later retrained and its embeddings shift, any downstream model still using the OLD exported embeddings will silently be working with a stale representation, which is the same training-serving-consistency discipline that applies throughout this topic, here specific to a learned representation rather than a raw feature.

Direct answer

The core move isn't picking a clever analogy, it's figuring out what decision or worry the stakeholder actually has before you start explaining, then building the explanation to answer that, and checking as you go whether it landed. Below is a caching example: what I chose to include, the analogy I used, how I confirmed it landed, and what happened.

Adapting depth without condescension

• Find out what they need to DECIDE, not just what they need to KNOW. A stakeholder rarely needs to understand caching itself, they need to decide whether to approve a change, a budget, or a timeline; build the explanation around that decision.
• Pick one analogy tied to something they already manage, inventory, a filing system, a pantry, and use it consistently rather than switching metaphors mid-conversation, which confuses even when each individual metaphor is fine on its own.
• Check understanding by asking them to restate the trade-off in their own words or apply it to a hypothetical ("if we changed X, what do you think happens to Y"), never by asking "does that make sense," which invites a polite yes regardless of whether it landed.
• Build the explanation step by step from what they already know rather than reaching for a named technique or framework to describe what you're doing; naming the technique adds nothing for the listener and mostly serves the explainer.

Worked example

Situation: our product team wanted faster page loads, and I needed the VP of Product and a finance manager, neither with an engineering background, to approve adding a caching layer.

Task: get them to understand the trade-off, faster pages, at the cost of occasionally showing slightly outdated data, well enough to make an informed approval decision, not just rubber-stamp it.

Action: I opened with the decision they needed to make, not the technology: "we can make pages load faster by keeping a copy of frequently requested information close by; the trade-off is that copy can be a few seconds out of date." I used a pantry analogy, keeping snacks nearby instead of driving to the store every time, and periodically checking the pantry is still fresh, consistently through the conversation. I sketched a two-box diagram on the whiteboard: browser, then a fast local cache, then the slower database behind it, and pointed at where the freshness delay would show up. For the finance manager, I connected the trade-off to their actual concern: fewer requests hitting the expensive database tier means lower infrastructure spend, which is why this was worth their budget attention. I checked understanding by asking each of them to describe, in their own words, what a customer might see if we set the freshness window too long; both correctly identified stale data as the risk, which told me the analogy had landed.

Result: they approved a staged rollout, and the finance manager specifically asked for the freshness window to start conservative and widen over time, which showed they'd internalized the actual trade-off rather than just agreeing. I learned to lead with the decision, not the mechanism, and that asking someone to apply the idea to a hypothetical is a much better comprehension check than asking if it makes sense.

Trade-offs and pitfalls

The pantry analogy is easy to over-extend; someone will eventually ask "what if two people put different snacks in at the same time," and a caching layer's real answer (a specific write and invalidation rule) doesn't have a clean pantry equivalent, so know where you'll stop extending it before someone finds the gap for you. The other common failure mode is treating a nod as confirmation, a stakeholder will often not admit they're lost mid-meeting, which is why an explicit restate-it-back check matters more than reading the room.

Direct answer

Walk through one concrete system end to end (here, a transaction fraud-risk scoring model), covering ingestion, training and validation, serving, and the specific signal that confirms health a month later, then name the two or three decisions that were genuinely hard and why they were made that way, rather than reciting a generic architecture template.

Structured elaboration

• Ingestion: raw transaction events land in an append-only store. True fraud labels are delayed (chargebacks land 30 to 90 days after the transaction), so the training set at any point in time is necessarily built on a mix of confirmed and provisional labels.
• Feature computation: features are computed by one shared library invoked by both the offline training job and the online serving path, specifically to avoid training-serving skew (the mismatch between the feature values a model sees during training and the values it actually receives at inference time, usually caused by two independent code paths quietly computing "the same" feature differently).
• Training and validation: the model retrains on a rolling window and is validated on a strict time-based holdout, never a random split, because fraud patterns drift over time; validation also checks performance by slice (transaction size, region), since an aggregate metric can look fine while the model quietly underperforms on a smaller, costlier slice.
• Serving: a synchronous, low-latency scoring service sits directly in the payment-authorization path, so it has a hard latency ceiling rather than a soft one.
• Health a month later, three separate signals, not one: proxy signals that don't need ground truth (the model's score distribution and calibration, tracked for drift), a delayed-label backtest (once real labels arrive, retroactively recompute precision and recall over the scored population and compare to what was expected offline), and a downstream business metric (chargeback rate, false-decline rate).

Two of the harder architectural calls, and the reasoning:

1. Synchronous scoring inside the authorization path. A fraud score that arrives after the transaction has already settled cannot block anything, so scoring had to be synchronous. That forced a lighter model (gradient-boosted trees rather than a heavier deep model) to fit inside the latency budget, trading some raw accuracy for the ability to act on the score at all.
2. One shared feature-computation path for training and serving. This couples the serving path to whatever the offline feature logic can compute quickly online, which is a real constraint. It was chosen anyway because, in an earlier version of the system, two independent feature implementations silently diverged and caused an accuracy drop that went undetected for weeks; paying the coupling cost up front was cheaper than repeating that failure.
3. Training on provisional labels. Since confirmed fraud labels lag by up to 90 days, waiting for fully confirmed labels before every retrain would mean training on data that is already stale relative to current fraud patterns. The system trains on provisional labels (unflagged transactions treated as legitimate) with periodic relabeling once confirmed labels arrive, accepting some label noise as the lesser failure mode compared to a model that's chronically out of date.

Worked example

Consider the latency budget behind decision 1. Suppose the payment authorization path has an end-to-end service-level objective (SLO, an internal target for how fast a request must complete) of 250 ms at the 99th percentile (p99, the latency below which 99% of requests complete). An identity check reserves 40 ms p99, a ledger lookup reserves 30 ms p99, and the round trip to the card issuer reserves 120 ms p99. That leaves the fraud check:

$250 - 40 - 30 - 120 = 60 \text{ ms p99 for feature retrieval and model inference combined}$

If retrieving features from the online store costs 25 ms p99, only 35 ms remains for inference. That budget rules out a large deep model (batched inference for large transformer-style models typically needs far more than 35 ms at p99 on standard hardware) and points toward a gradient-boosted tree ensemble or a small feedforward network instead. This is the concrete arithmetic behind decision 1: the model architecture wasn't chosen by preference, it was constrained by what fits inside a budget derived from the other components already sitting in the same request path.

flowchart LR
  A[Raw transactions] --> B[Shared feature library]
  B --> C[Offline feature store]
  B --> D[Online feature store]
  C --> E[Training pipeline]
  E --> F[Model registry]
  F --> G[Serving path]
  D --> G
  G --> H[Auth decision]
  H --> I[Delayed fraud labels]
  I --> J[Backtest job]
  J --> K[Retrain trigger]
  K --> E

Trade-offs & pitfalls

• Answering with a generic reference architecture instead of a specific system with specific numbers misses the point of the question: it's testing whether the candidate actually owned trade-offs, not whether they can recite a template.
• Concluding a model is "still healthy" purely because nobody complained is a trap; without a label-based backtest, degradation in a low-complaint system can run silently for a long time.
• A model's offline metrics can stay flat while its real-world input distribution drifts underneath it; the two need separate monitoring, since one does not imply the other.
• Two feature-computation code paths will eventually diverge even if they start out identical, which is exactly why the shared-library decision above was worth its coupling cost.

Direct answer

Token-level augmentation (synonym swaps, random deletion) is cheap and fast but risks small, local meaning changes; span-level augmentation (masking or swapping whole phrases or entities) preserves more surrounding context but can still corrupt named-entity-sensitive tasks; back-translation produces the most fluent, natural-sounding variety but is the most expensive and hardest to control precisely.

Structured elaboration

Detecting semantic drift from the original: compute a similarity score (cosine similarity between sentence embeddings of the original and augmented text) and flag pairs below a threshold for manual review or automatic discarding; for back-translation specifically, comparing the round-tripped sentence's embedding against the original catches cases where the translation pass introduced a genuine meaning change rather than just a paraphrase.

For fine-tuning production large language models specifically, the cost-versus-fidelity trade-off shifts toward preferring higher-fidelity techniques (span masking, back-translation) over crude token-level swaps, since a production LLM's fine-tuning data quality has outsized influence on output quality, and cheap, low-fidelity augmentation risks teaching subtly wrong patterns at scale.

Worked example

Back-translating "The customer was frustrated by the delayed shipment" through French and back might produce "The customer was upset about the shipping delay," a genuine paraphrase preserving meaning; a careless synonym-replacement pass on the same sentence swapping "frustrated" for a poorly-chosen synonym like "confused" would introduce a real, undetected meaning change that a naive word-level substitution list wouldn't catch on its own.

Trade-offs and pitfalls

The common mistake is treating all three techniques as interchangeable "make more data" options rather than recognizing that each introduces a DIFFERENT kind and rate of potential semantic drift, meaning the amount of quality-control effort (similarity checks, manual spot review) should scale with how much drift a given technique typically introduces, not be applied uniformly regardless of method.

Direct answer

Quickselect finds the kth largest element in average O(n) time by reusing quicksort's partitioning step, but only ever recursing into the ONE side of the partition that contains the answer, instead of both sides like quicksort does. Its PARTITIONING is O(1) extra space (a handful of index variables, all swaps done within the array), which is the property the question is asking about; whether the function as a whole is O(1) space then depends on one API decision, whether it sorts the caller's list in place or works on a copy, and that decision is made explicit below rather than left implied.

Structured elaboration

The core idea: pick a pivot, partition the array around it (everything less than the pivot ends up to its left, everything greater or equal ends up to its right, matching quicksort's Lomuto or Hoare partition scheme), and check where the pivot landed relative to the index you're looking for. If the pivot landed exactly at the target index, you're done. If the target index is to the left of the pivot's final position, recurse only into the left partition; if it's to the right, recurse only into the right partition. Because you discard the other half of the array entirely at each step instead of processing both halves, the expected total work follows the same geometric-series shrinking as quicksort's average case, giving expected time $T(n) = T(n/2) + O(n) = O(n)$ rather than quicksort's $O(n \log n)$, because there's no second recursive branch to sum in. The in-place partitioning (swapping elements within the same array, using only a few index variables) is what keeps the SEARCH's extra space at O(1): no auxiliary array is needed to partition, and writing the loop iteratively rather than recursively keeps the call stack at O(1) too, where a recursive quickselect would add O(log n) expected stack frames. Be precise about what that does and does not cover, because it is the easiest claim in this problem to overstate: the implementation below deliberately begins with arr = nums[:], a full O(n) copy, so that it does not scramble the caller's list. That copy makes the FUNCTION O(n) extra space even though the ALGORITHM is O(1). Truly O(1) total extra space requires permuting the caller's array in place and documenting that side effect, which is a one-line change (drop the copy and use nums directly) and is the right call when the caller owns a throwaway buffer; the copy is the right call when the caller's ordering is load-bearing. State which one you chose, do not claim both.

Worst case is still $O(n^2)$, exactly like quicksort, if the pivot choice is consistently bad (e.g., always picking the smallest or largest remaining element on an already-sorted or adversarially-ordered input with a naive pivot rule); choosing the pivot uniformly at random, as below, makes that worst case exponentially unlikely rather than eliminating it, which is the standard practical mitigation (a deterministic median-of-medians pivot selection guarantees worst-case O(n) instead, at a larger constant factor, and is rarely needed in interview-level implementations).

Behavior for invalid k and duplicates, stated explicitly: k is defined as 1-indexed from the largest (k=1 means the single largest element), and any k outside [1, len(nums)] is a usage error that should raise rather than silently return a wrong answer. Duplicate values are handled correctly by the partition scheme without special-casing: if the target value appears multiple times, the algorithm still converges on a single correct index in the sorted-order sense (the kth position when ties are broken arbitrarily among equal values), because partitioning only compares against the pivot's value, never against object identity.

Worked example

import random

def quickselect_kth_largest(nums, k):
    """Return the kth largest element (k=1 -> largest).

    Time: O(n) average, O(n^2) worst case.
    Space: O(1) for the selection itself; O(n) overall because of the defensive
    ``arr = nums[:]`` copy below, which leaves the caller's list unmodified.
    Drop the copy and partition ``nums`` directly for true O(1) extra space,
    at the cost of permuting the caller's list.
    """
    if not nums:
        raise ValueError("nums must be non-empty")
    if k < 1 or k > len(nums):
        raise ValueError(f"k={k} out of range for array of length {len(nums)}")

    target_index = len(nums) - k  # index of the kth largest in ascending sorted order
    arr = nums[:]  # O(n) copy: preserves the caller's list. Use `arr = nums` for O(1) space.
    lo, hi = 0, len(arr) - 1

    while lo < hi:
        pivot_index = random.randint(lo, hi)
        arr[pivot_index], arr[hi] = arr[hi], arr[pivot_index]
        pivot = arr[hi]
        store = lo
        for i in range(lo, hi):
            if arr[i] < pivot:
                arr[i], arr[store] = arr[store], arr[i]
                store += 1
        arr[store], arr[hi] = arr[hi], arr[store]

        if store == target_index:
            return arr[store]
        elif store < target_index:
            lo = store + 1
        else:
            hi = store - 1

    return arr[lo]


random.seed(42)
print(quickselect_kth_largest([3, 2, 1, 5, 6, 4], 2))              # 5
print(quickselect_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))     # 4
print(quickselect_kth_largest([5, 5, 5, 5], 3))                    # 5, duplicates handled
try:
    quickselect_kth_largest([1, 2, 3], 5)
except ValueError as e:
    print("invalid k:", e)

Running this prints:

5
4
5
invalid k: k=5 out of range for array of length 3

each matched against sorted(nums, reverse=True)[k-1] as an independent check during development, confirming correctness on both distinct and duplicate-heavy inputs.

Trade-offs and pitfalls

Using a fixed pivot choice (always the first or last element) instead of a random one turns an already-sorted or reverse-sorted input into the O(n^2) worst case deterministically, which is exactly the input shape an adversary or a careless test generator is most likely to produce, so randomizing pivot selection is not a cosmetic detail. A second pitfall is the space claim itself: it is very easy to say "quickselect is O(1) extra space" and then ship a function that opens with a full copy of the input, which is O(n). Those are two different claims about two different things (the algorithm versus this function), and an interviewer will ask which one you meant. Mutating the caller's original list in place without documenting it is the mirror-image mistake, since quickselect's partitioning permanently reorders the array as a side effect; the version above copies first and says so, trading the O(1) space guarantee for a non-surprising API, and either choice is defensible as long as it is stated. Finally, quickselect only finds the kth element, it does not leave the array fully sorted, so if a caller actually needs a sorted prefix or suffix (not just one position), a full sort is the right tool despite quickselect's better asymptotic complexity for the single-element query.

Direct answer

I start by figuring out the smallest slice of the tool a specific task actually needs, not its whole surface area, and I get there by doing rather than reading in isolation. I weight learning toward the parts most likely to break or surprise me, state handling, concurrency, failure behavior, whatever the tool's real sharp edges are, deliberately defer advanced or rarely used features until they are needed, and I consider myself ready for real work once I can predict what the tool will do on a case I have not tried before, not just reproduce a tutorial.

Structured elaboration

Prioritizing what to learn first

• Start from the task, not the manual: what does this specific piece of work require the tool to do, and work outward from there.
• Weight toward the tool's failure modes and non-obvious behavior first, since those cause real damage, not the well-documented happy path.
• Explicitly defer advanced surface area, configuration knobs, performance tuning, edge-case interfaces, anything the current task does not touch, and say so out loud rather than trying to learn everything before starting.

Confirming comprehension rather than mimicry

• Change one assumption on purpose and predict what should happen before checking; if the prediction is wrong, that gap is exactly what to close next.
• Explain the tool's behavior to someone else, or write it down, without looking at the reference; being unable to explain it plainly is a sign the understanding is still surface-level.
• Deliberately reproduce a small known issue or edge case rather than only ever running the happy path.

Knowing when it is safe to be trusted with real work

• Confidence comes from correctly predicting behavior on a case not seen before, not from something merely having run once.
• If the team's existing practice with the tool is inconsistent or weak, learn and apply at the same time rather than waiting for a clean reference implementation to copy.

Worked example

Say I am handed a task that requires a caching layer I have never operated. I do not start with the full documentation; I start with what the task needs, reads and writes for one specific data pattern. I read just enough to understand the eviction policy and what happens during a cache-miss storm, since that is the sharp edge most likely to matter, and I defer things like clustering configuration or advanced eviction tuning entirely, since this task does not touch them. Before writing real code, I predict what happens if two writes race on the same key, then write a small local test to check, and I am wrong the first time, which tells me exactly where my mental model was off. Once I can correctly predict behavior on a case I invent myself, not just repeat the documentation's own example, I consider myself ready to touch the real task.

Trade-offs and pitfalls

• Deferring advanced surface area is efficient but risky if the thing deferred turns out to be quietly load-bearing for the actual task; the judgment call is knowing which "advanced" features are genuinely optional.
• Confidence built on a narrow set of predictions can still be wrong outside that narrow set; treat "I can predict this" as evidence for the cases actually tested, not a blanket guarantee.
• Learning purely by doing, with no reference material at all, tends to reinforce whatever mental model you started with, right or wrong; a quick check against documentation or a knowledgeable person catches that.

The idea in plain words

"Probability proportional to weight" means that if the weights are 3, 1, 4, 1, 5 (total 14), item e is picked with probability 5/14. A direct way to pick: draw a random whole number r from 0 to total - 1, lay the items out on a number line with item i owning a stretch of weight[i] consecutive positions, and return the item whose stretch contains r. The whole problem is finding that item fast while weights keep changing.

A binary sum tree does both parts in O(log n). Put the weights in the leaves of a binary tree (leaves are nodes with no children), and let every internal node store the sum of its two children. The root then holds the total. To find the owner of position r, start at the root and ask "is r inside the left child's stretch?": if r < left sum, go left; otherwise subtract the left sum from r and go right. One decision per level, so the walk takes as many steps as the tree has levels. To change a weight, add the difference to the leaf and to each of its ancestors, again one step per level. Heights and depths here count edges (empty tree -1, single node 0), so a tree with 8 leaves has height 3.

Weights here are non-negative integers, which makes the arithmetic exact; for decimal weights, scale them to integers first. Each update adds a difference to the ancestors, and with floating-point numbers the rounding can leave a tiny nonzero residue in a node whose true weight is 0, so a descent can then return a zero-weight item.

Brute force and the alternatives

• Linear scan: add weights until the running total passes r. Sampling is O(n), updates are O(1).
• Prefix-sum array (cumulative totals [3, 4, 8, 9, 14]): sampling is O(log n) with a binary search, but changing one weight changes every cumulative value after it, so an update is O(n).
• Heap: a heap keeps the largest (or smallest) item at the top and says nothing about sums of subtrees. It is the wrong tool for "pick in proportion to weight". (Heaps do appear in weighted sampling without replacement from a stream, where each item gets a random key built from its weight and a heap keeps the best k keys. That is a rarely asked extension and a different task from sampling from a changing table.)
• Sum tree or Fenwick tree: O(log n) for both operations.

The layout

The tree lives in a flat list. With size leaves (a power of two), leaf i is at index size + i, and the children of node j are 2j and 2j + 1. The five weights above, padded to 8 leaves, look like this (node numbers are the list indexes):

              1:14
          /          \
       2:9            3:5
      /    \         /    \
    4:4    5:5     6:5    7:0
    / \    / \     / \    / \
   3   1  4   1   5   0  0   0
   a   b  c   d   e

The root holds 14. The list is printed by the program below as [0, 14, 9, 5, 4, 5, 5, 0, 3, 1, 4, 1, 5, 0, 0, 0]; index 0 is unused.

Code

import random


class WeightedSampler:
    """Binary sum tree in an array. Leaf i is at size + i; each internal node holds the sum of
    its two children, so tree[1] is the total weight. Weights are non-negative integers."""

    def __init__(self, capacity=4):
        self.size = 1
        while self.size < capacity:
            self.size *= 2
        self.tree = [0] * (2 * self.size)
        self.items = []

    def add(self, item, weight):
        if len(self.items) == self.size:
            self._grow()
        self.items.append(item)
        self.update(len(self.items) - 1, weight)

    def update(self, index, new_weight):
        if not 0 <= index < len(self.items):
            raise IndexError(index)
        if new_weight < 0:
            raise ValueError("weight must be >= 0")
        node = self.size + index
        delta = new_weight - self.tree[node]
        while node >= 1:                          # add the change to every ancestor
            self.tree[node] += delta
            node //= 2

    def _grow(self):                              # doubles the leaf level and rebuilds sums
        leaves = self.tree[self.size:self.size + len(self.items)]
        self.size *= 2
        self.tree = [0] * (2 * self.size)
        self.tree[self.size:self.size + len(leaves)] = leaves
        for node in range(self.size - 1, 0, -1):
            self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def total(self):
        return self.tree[1]

    def find(self, r, log=None):
        """Index of the leaf that owns position r, for 0 <= r < total."""
        node = 1
        while node < self.size:
            left = self.tree[2 * node]
            if r < left:
                node = 2 * node
                where = "left"
            else:
                r -= left
                node = 2 * node + 1
                where = "right"
            if log is not None:
                log.append(f"  at node {node // 2} (left sum {left}): go {where}, r is now {r}")
        return node - self.size

    def sample(self, n, rng):
        if self.total() == 0:
            raise ValueError("no weight to sample from")
        return [self.items[self.find(rng.randrange(self.total()))] for _ in range(n)]


class Fenwick:
    """Fenwick (binary indexed) tree over the same weights: n + 1 slots instead of 2 * size."""

    def __init__(self, weights):
        self.n = len(weights)
        self.t = [0] * (self.n + 1)
        for i, w in enumerate(weights):
            self.add(i, w)

    def add(self, i, delta):
        i += 1
        while i <= self.n:
            self.t[i] += delta
            i += i & -i

    def find(self, r):
        """Smallest index whose running total exceeds r."""
        pos, step = 0, 1 << self.n.bit_length()
        while step:
            nxt = pos + step
            if nxt <= self.n and self.t[nxt] <= r:
                pos = nxt
                r -= self.t[nxt]
            step >>= 1
        return pos


if __name__ == "__main__":
    s = WeightedSampler()
    for name, w in [("a", 3), ("b", 1), ("c", 4), ("d", 1), ("e", 5)]:
        s.add(name, w)
    print("capacity", s.size, "| tree array:", s.tree)
    print("node 1 = total", s.total(), "| node 2 =", s.tree[2], "(leaves a..d) | node 3 =", s.tree[3], "(leaves e..h)")

    log = []
    idx = s.find(9, log)
    print("find(9):")
    print("\n".join(log))
    print("-> index", idx, "item", s.items[idx])

    # Exact check: over r = 0..total-1 every leaf must own exactly `weight` positions
    def check(sampler):
        owned = [0] * len(sampler.items)
        for r in range(sampler.total()):
            owned[sampler.find(r)] += 1
        assert owned == sampler.tree[sampler.size:sampler.size + len(sampler.items)], owned
        return owned
    print("positions owned per item:", check(s))

    s.update(1, 6)                    # b goes from 1 to 6
    s.update(2, 0)                    # c goes from 4 to 0, so it must never be returned
    s.add("f", 2)
    s.add("g", 0)
    s.add("h", 7)
    s.add("i", 3)                     # the ninth item forces the tree to double
    print("after updates, capacity", s.size, "| owned per item:", check(s))

    fen = Fenwick(s.tree[s.size:s.size + len(s.items)])
    assert all(fen.find(r) == s.find(r) for r in range(s.total()))
    print("Fenwick find agrees with the sum tree on all", s.total(), "positions")

    rng = random.Random(42)
    draws = s.sample(20000, rng)
    counts = {k: draws.count(k) for k in s.items}
    print("20000 draws:", counts)
    print("expected   :", {k: round(20000 * w / s.total()) for k, w in zip(s.items, s.tree[s.size:])})

    # Randomised check against a plain list of weights
    rng = random.Random(9)
    ref, t = [], WeightedSampler(1)
    for step in range(400):
        if not ref or rng.random() < 0.3:
            ref.append(rng.randint(0, 5)); t.add(len(ref) - 1, ref[-1])
        else:
            i = rng.randrange(len(ref)); ref[i] = rng.randint(0, 5); t.update(i, ref[i])
        if sum(ref):
            assert check(t) == ref
    print("random add/update sequence checked against a plain list: 400 steps, final size", len(ref))

    # The two guards: nothing to sample, and a negative weight
    for label, action in [("empty sampler, sample(1)", lambda: WeightedSampler().sample(1, rng)),
                          ("update(0, -1) on the sampler above", lambda: s.update(0, -1))]:
        try:
            action()
        except ValueError as err:
            print(f"{label}: ValueError: {err}")

Output:

capacity 8 | tree array: [0, 14, 9, 5, 4, 5, 5, 0, 3, 1, 4, 1, 5, 0, 0, 0]
node 1 = total 14 | node 2 = 9 (leaves a..d) | node 3 = 5 (leaves e..h)
find(9):
  at node 1 (left sum 9): go right, r is now 0
  at node 3 (left sum 5): go left, r is now 0
  at node 6 (left sum 5): go left, r is now 0
-> index 4 item e
positions owned per item: [3, 1, 4, 1, 5]
after updates, capacity 16 | owned per item: [3, 6, 0, 1, 5, 2, 0, 7, 3]
Fenwick find agrees with the sum tree on all 27 positions
20000 draws: {'a': 2144, 'b': 4418, 'c': 0, 'd': 760, 'e': 3728, 'f': 1477, 'g': 0, 'h': 5284, 'i': 2189}
expected   : {'a': 2222, 'b': 4444, 'c': 0, 'd': 741, 'e': 3704, 'f': 1481, 'g': 0, 'h': 5185, 'i': 2222}
random add/update sequence checked against a plain list: 400 steps, final size 139
empty sampler, sample(1): ValueError: no weight to sample from
update(0, -1) on the sampler above: ValueError: weight must be >= 0

How a sample descends: the trace

find(9) on the tree above (the cumulative totals are 3, 4, 8, 9, 14, so position 9 is the first position owned by e):

1. At node 1 the left child (node 2) holds 9. r = 9 is not below 9, so go right and set r = 9 - 9 = 0.
2. At node 3 the left child (node 6) holds 5. r = 0 < 5, so go left.
3. At node 6 the left child (leaf 12) holds 5. r = 0 < 5, so go left. Node 12 is a leaf: index 12 - 8 = 4, which is e.

That is exactly the three lines the program prints, and the result e matches the layout.

Why it is correct, and checked exhaustively. At each node the left child owns the first left sum positions of that node's stretch and the right child owns the rest, so the decision never loses a position. The check function in the program tries every r from 0 to total - 1 and confirms that item i is returned for exactly weight[i] of them. That exact count (not a random test) is shown after the updates too, where a weight of 0 is owned by zero positions and so can never be sampled. The 20,000-draw run is a fixed-seed illustration: its counts land near the expected counts but are not exact, which is normal for random draws.

Add, update, and sample(n)

• update(index, new_weight): compute the difference, then add it to the leaf and to every ancestor up to the root: one step per level.
• add(item, weight): put the item in the next free leaf and call update. When the leaves are all used, the tree doubles its leaf count and rebuilds every internal sum in O(size). Amortized means the cost averaged over a whole run of operations. A rebuild at capacity 8 costs about 16 steps, but it can only happen again after 8 more adds have filled the new space, so the rebuild work per add stays constant on average even though one unlucky add costs O(n). In the program, the ninth add doubles the capacity from 8 to 16.
• sample(n): n independent draws of r, each followed by a descent: O(n log N) for N items. That is sampling with replacement (the same item can appear twice). Sampling without replacement can be done by setting a drawn item's weight to 0 with update, and restoring it afterwards, O(log N) each.

Fenwick tree comparison

A Fenwick tree (binary indexed tree) stores partial sums in one list of N + 1 slots, using the lowest set bit of the index to decide which range each slot covers (worked in the walk-through below). Updates add the difference to O(log N) slots; the sample step finds the smallest index whose running total exceeds r by testing powers of two from large to small. The program builds one from the same weights and shows that its find returns the same index as the sum tree for all 27 positions. Choose the Fenwick tree when memory matters or you only need prefix sums plus sampling: it uses N + 1 slots instead of 2 * size (roughly 2N to 4N). Choose the explicit sum tree when you want to read a node's subtree total directly, such as to descend to a subtree, to split sampling by region, or to teach and debug.

Fenwick walk-through on the five weights

Three ideas make the Fenwick tree work. The lowest set bit of a number is its rightmost 1 in binary, and i & -i isolates it (for 12 = 1100 it is 4). Slot i (counting from 1) stores the sum of the i & -i weights that end at index i, so slot 4 covers four weights, slot 6 covers two, and every odd slot covers just itself. Adding i & -i to i jumps to the next slot whose range contains i, which is how an update reaches every slot that must change. And 1 << n.bit_length() is the smallest power of two above n (8 for n = 5), the largest jump the descent can try.

weights = [3, 1, 4, 1, 5]
n = len(weights)
t = [0] * (n + 1)          # slot i (1-based) holds the sum of the last (i & -i) weights ending at i


def add(i, delta):
    i += 1                 # convert to 1-based
    while i <= n:
        t[i] += delta
        print(f"    slot {i} ({i:03b}) += {delta}  -> {t[i]}")
        i += i & -i        # i & -i is the lowest set bit of i; adding it jumps to the next slot that covers i


for idx, w in enumerate(weights):
    print(f"add weight {w} at index {idx}:")
    add(idx, w)
print("slots 1..5:", t[1:])
for i in range(1, n + 1):
    low = i & -i
    print(f"slot {i} ({i:03b}): lowest set bit {low}, covers weights at indexes {i - low}..{i - 1} = {sum(weights[i - low:i])}")


def find(r):
    pos, step = 0, 1 << n.bit_length()
    print(f"find({r}): start pos=0, step={step}")
    while step:
        nxt = pos + step
        if nxt <= n and t[nxt] <= r:
            print(f"    step {step}: slot {nxt} holds {t[nxt]} <= r={r}, take it, r becomes {r - t[nxt]}")
            pos, r = nxt, r - t[nxt]
        else:
            print(f"    step {step}: slot {nxt} " + ("is past the end" if nxt > n else f"holds {t[nxt]} > r={r}, skip"))
        step >>= 1
    return pos


print("owner of position 9 is index", find(9))

# growing a sum tree from 2 leaves to 4 when a third weight arrives
size, tree = 2, [0, 4, 3, 1]          # leaves are tree[2:4] = [3, 1]; tree[1] = 4 is the total
print("\nbefore grow:", tree)
leaves = tree[size:]
size *= 2
tree = [0] * (2 * size)
tree[size:size + len(leaves)] = leaves  # copy the leaves into the new, wider leaf level
for node in range(size - 1, 0, -1):     # recompute every internal sum bottom-up
    tree[node] = tree[2 * node] + tree[2 * node + 1]
print("after grow: ", tree)
tree[size + 2] = 4                      # now the third weight fits; add it to the leaf (node 6) and its ancestors (nodes 3 and 1)
tree[3] += 4
tree[1] += 4
print("after adding weight 4 at index 2:", tree)

Output:

add weight 3 at index 0:
    slot 1 (001) += 3  -> 3
    slot 2 (010) += 3  -> 3
    slot 4 (100) += 3  -> 3
add weight 1 at index 1:
    slot 2 (010) += 1  -> 4
    slot 4 (100) += 1  -> 4
add weight 4 at index 2:
    slot 3 (011) += 4  -> 4
    slot 4 (100) += 4  -> 8
add weight 1 at index 3:
    slot 4 (100) += 1  -> 9
add weight 5 at index 4:
    slot 5 (101) += 5  -> 5
slots 1..5: [3, 4, 4, 9, 5]
slot 1 (001): lowest set bit 1, covers weights at indexes 0..0 = 3
slot 2 (010): lowest set bit 2, covers weights at indexes 0..1 = 4
slot 3 (011): lowest set bit 1, covers weights at indexes 2..2 = 4
slot 4 (100): lowest set bit 4, covers weights at indexes 0..3 = 9
slot 5 (101): lowest set bit 1, covers weights at indexes 4..4 = 5
find(9): start pos=0, step=8
    step 8: slot 8 is past the end
    step 4: slot 4 holds 9 <= r=9, take it, r becomes 0
    step 2: slot 6 is past the end
    step 1: slot 5 holds 5 > r=0, skip
owner of position 9 is index 4

before grow: [0, 4, 3, 1]
after grow:  [0, 4, 4, 0, 3, 1, 0, 0]
after adding weight 4 at index 2: [0, 8, 4, 4, 3, 1, 4, 0]

Read the trace like this. Adding weight 3 at index 0 touches slots 1, 2 and 4: the three slots whose ranges include index 0. The table shows slot 4 holds 9 = 3 + 1 + 4 + 1, the first four weights. In find(9) the descent tries the largest jump first: slot 8 does not exist, slot 4 holds 9 which is not above r = 9, so the whole block belongs before the answer and r drops to 0. The next jump lands on slot 6, past the end, and slot 5 holds 5, which is above 0, so the walk stops with pos = 4: index 4, item e, the same owner the sum tree found. The last three lines show the sum tree's growth step on a 2-leaf tree: the leaves are copied into a wider leaf level and every internal sum is recomputed bottom-up.

A typical interview needs one of the two trees (the sum tree or the Fenwick tree), the update rule and the descent rule. The alias method and sampling with random keys and a heap are deeper material that a coding round rarely asks for.

Complexity

• update, find: O(log size) each, where the tree has about log2(size) levels (3 for 8 leaves, 4 for 16).
• add: O(log size) plus an O(size) rebuild each time the capacity doubles: amortized O(log size).
• sample(n): O(n log size).
• Space: a list of 2 * size entries, where size is at most about 2N for N items, so about 4N entries at most.

Edge cases and common mistakes

• Total weight 0: there is nothing to sample; the code raises ValueError instead of returning an item (the last lines of the first program's output show it).
• Zero-weight items must never be returned: use r < left (strict) when choosing the left child, which the exhaustive check confirms.
• Updating a leaf without updating its ancestors leaves every sum above it stale, so the descent is steered by old totals.
• Using floating-point weights and random.random() * total: rounding can send the descent into a zero-weight leaf. Scale to integers or add a guard.
• Off-by-one on the position: randrange(total) yields 0 to total - 1; using randint(0, total) can pick a position past the end.
• Negative weights make the stretches meaningless; reject them as update does (also shown in the last output line of the first program).

Follow-ups and how the answer changes

• Weights never change and the number of draws is huge: the alias method (a precomputed table of two-way coin flips; rarely asked in interviews) gives O(1) per draw after an O(n) setup, but any update means rebuilding.
• Sampling without replacement while weights change: the zero-and-restore trick above, in O(log N) per draw.
• Different sample sizes per call and a stream of items: keep the same tree and only grow the leaf level when needed.

Running the code

# Python 3.12, standard library only
python weighted_sampler.py     # the sampler (first program)
python fenwick_walk.py         # the Fenwick walk-through (second program)