Coding round for data and platform roles.
Sample from a stream of unknown length
The question
Pick one element uniformly at random from a stream whose length you do not know in advance, using constant memory.
Have a go before you open the solution. If you are stuck after a few minutes, the first paragraph below is usually enough of a nudge.
Show the worked solution
The answer
Reservoir sampling: keep the nth element with probability 1/n.
Hold the current candidate. When the nth element arrives, replace the candidate with probability 1/n.
By induction each element ends up selected with probability exactly 1/N after N items: the nth survives with probability (1/n) times the product of (1 - 1/k) for k above n, which telescopes to 1/N.
For a sample of size k, keep the first k, then accept the nth with probability k/n and evict a uniformly chosen incumbent.
It comes up genuinely in trading systems whenever you need a representative sample of messages without buffering the feed.
What it is testing
A short inductive proof alongside the code.
Try these next
Maximum drawdown in one pass
Warm-upGiven an array of prices in time order, compute the maximum drawdown in a single pass.
Rolling median of a stream
HardMaintain the median of the last k values of a stream efficiently.
Design a limit order book
HardWhat data structures would you use for a limit order book that must add, cancel and match quickly?
Why the loop order matters
StandardTwo implementations of matrix multiplication have identical complexity but one runs several times faster. Why?
Preparing properly
Live opportunities
Interviewing soon? See who is hiring
Open vacancies we track at quant firms, grouped by role and city. Adverts are anonymised.
Hiring for these roles? Brief the desk on a hire or check your fit for a role.
Research desk
Speak to a quant market specialist
Ask what a firm really pays, how a desk hires, or where your profile sits. One reply from the research desk, in confidence, no obligation.