AI Engineer Interview Daily — 2026-10-23: Coding

🌏 中文版

Today's Focus

Friday is still Coding day, but today's a different flavor from last week. Last Friday's k-means was a "batch data, everything fits in memory at once" problem. Today's is a "streaming data, you don't know the length ahead of time" problem — reservoir sampling. This type of question shows up in MLE onsite coding rounds right alongside "compute precision/recall/F1" and "compute each user's seven-day rolling activity count." What's being tested isn't how well you've memorized a data structure — it's whether you can derive a probabilistically sound algorithm under the constraint that memory is limited and data can only be read once, and then explain why it works instead of just typing out code.

Core Concepts

1. The "ML flavor" in ML coding questions hides in probability and streaming assumptions

A typical LeetCode question assumes all the data is already in hand — sort it, scan it multiple times, whatever you want. MLE interviews deliberately add a "streaming" or "probabilistic sampling" constraint instead — the data source might be a user-event log, a live feature stream, or a dataset too large to fit in memory, which immediately rules out "just sort it first." The interviewer wants to see whether you notice this constraint changes the whole direction of the solution, instead of forcing the question into a template you memorized.

2. Reservoir sampling's core invariant: every element has to end up with probability k/n

The algorithm itself isn't hard: stuff the first k items into a "reservoir," then from item k+1 onward, use randomness to decide whether to swap each new item in and which one to kick out. The hard part is explaining why this is correct — proving by induction that after processing item i, every element currently in the reservoir has exactly a k/i chance of being there. That invariant is what guarantees that by the time the stream ends, every one of the n items has exactly a k/n chance of being selected — true uniform sampling, not something that merely looks random but is secretly biased.

3. Streaming constraints change your entire toolbox

Batch problems let you sort, scan multiple times, or lay out the whole dataset to compute a distance matrix at once. Streaming problems only let you look once, never backtrack, and only hold O(k) memory instead of O(n). That rules out some of your usual tricks (sort-for-median, multi-pass convergence) outright, and forces a single-pass, update-state-as-you-go approach instead. When an interviewer deliberately says "data stream" and "unknown length," they're testing whether you check the constraints first and pick the algorithm second, instead of hearing "sampling" and reflexively reaching for random.sample.

4. Not every ML coding question deserves vectorization

Last Friday's k-means practice stressed "use broadcasting instead of nested loops." Reservoir sampling is the counterexample — whether each item gets swapped into the reservoir, and the outcome, depend on the state from the previous step; it's fundamentally a sequentially dependent chain of random decisions, and it can't be vectorized all at once. Forcing vectorization onto it tends to plant subtle bugs around "sharing a random seed" or "pretending steps are independent when they aren't." What the interviewer wants to hear is that you can tell the difference between "this problem should be vectorized" and "this problem is structurally sequential, and forcing vectorization just creates new bugs."

5. Precision/recall/F1's zero-division edge case is a recurring trap in the same question bank

The same article lists another question from this set — "write a function that computes precision, recall, and F1, and handles the case where the model predicts no positives at all." It's testing the same mindset: edge cases decide whether you pass. When the denominator is zero, you need to explicitly define the return value (usually 0, documented as a deliberate choice), not let the function throw a ZeroDivisionError or silently return nan.

Today's Practice Question

The Question

You have a data source whose length you don't know in advance — it could be a live event stream, or a file too large to even count the total number of rows beforehand. Implement a function that uniformly samples k items from this stream, scanning it exactly once, using extra memory proportional only to k (not to the total length n). Explain why your method produces a uniform sample.

Source: Adapted from the MLE coding-round examples listed in CoPilot Interview's "Machine Learning Engineer Onsite Interview: Round by Round" (published 2026-10-22) Difficulty: Intermediate Round: Onsite coding round

Breaking It Down

1. Clarify the problem first: is the length genuinely unknown, or just known-but-large with an upper bound? Does the sample need to preserve original order? If the stream might repeat the same item, does that need deduplication? These decide whether you need anything beyond the basic version.
2. Build the framework: split the problem into two phases — the first k items go straight into the reservoir, no probability check needed; from item k+1 onward, every item requires a decision about "should this swap out something already in the reservoir," and the probability formula behind that decision is the whole core of the question.
3. Go deep on the core trade-offs: item i (1-indexed, i > k) must stay in the reservoir with probability k/i, so you generate a uniform random draw over [0, i) (or [1, i], depending on your indexing convention), and if that draw lands inside the reservoir's size range, you swap the new item into that slot; otherwise you discard it. The key is being able to prove this out loud: assuming every item has probability k/(i-1) of being in the reservoir after processing i-1 items, once you add item i, the old items' probability of staying needs a conditional correction for "wasn't swapped out," and the new item's probability of staying needs to come out to k/i — both have to check out algebraically for the induction chain to hold.
4. Close it out: state the complexity — O(n) time, O(k) extra space — and proactively name the practical caveat: if n is actually known and small, plain uniform sampling without replacement (e.g. np.random.choice) is more intuitive and easier to test. Reservoir sampling earns its keep specifically when n is genuinely unknown or too large to compute up front.

Sample Answer (How You'd Actually Say This in an Interview)

Confirm the constraints first. I'd ask whether the source is really unknown-length or just "large," because if n actually has a known bound, plain uniform sampling without replacement is simpler and easier to test. Assuming it's confirmed to be a genuinely unknown-length stream, I'd go with reservoir sampling.

Write the core logic. I'd put the first k items straight into a fixed-size array as the reservoir, no probability check at all. From item k+1 onward, for each new item, I'd generate a uniform random integer between 0 and the count of items seen so far minus one; if that number is less than k, I swap the new item into the reservoir slot at that index, otherwise I discard the item and move on. The whole pass scans the stream exactly once, and the only extra memory is the reservoir itself at O(k) — completely independent of n.

Prove why it's correct. This is the part the interviewer actually wants to hear — by induction: assume that after processing item i-1, every item in the reservoir has probability k/(i-1) of being there. When you process item i, the new item's probability of staying is exactly the random range I chose, which works out to k/i; an old item staying requires it "wasn't swapped out this round" times "was already in the reservoir," and multiplying those out and simplifying also gives k/i. The induction holds, which means by the time you reach the last item, every one of the n items ends up in the reservoir with exactly k/n probability — that's the actual definition of "uniform sampling," not just "feels random enough."

Self-Check

Use this table to check whether your answer hit the key points:

Further Reading

• Machine Learning Engineer Onsite Interview: Round by Round — CoPilot Interview — source for today's practice question; the same question bank also lists precision/recall/F1 and rolling-window activity-count as ML-flavored coding examples
• LinkedIn Interview Questions (Updated 2026) — PracHub — a 217-question real LinkedIn interview bank; its MLE category explicitly names "probabilistic sampling" and "weighted-index sampling" as recurring themes, good for cross-practice
• Machine Learning Interview Questions and Answers (2026) — goodspace.ai — a complete vectorized NumPy implementation of mini-batch SGD, useful as a contrast for today's discussion of "which problems deserve vectorization"

References

• Machine Learning Engineer Onsite Interview: Round by Round — CoPilot Interview — source for today's practice question (reservoir sampling) and the precision/recall/F1 zero-division trap
• LinkedIn Interview Questions (Updated 2026) — PracHub — supporting source for "probabilistic sampling" and "weighted-index sampling" as recurring MLE interview themes
• Machine Learning Interview Questions and Answers (2026) — goodspace.ai — vectorized NumPy implementation example, used as the contrast case for "which problems should be vectorized"