Quant developer coding round.
Rolling median of a stream
The question
Maintain the median of the last k values of a stream efficiently.
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
Two heaps, a max-heap of the lower half and a min-heap of the upper half, with lazy deletion.
Keep the smaller half in a max-heap and the larger half in a min-heap, rebalancing so their sizes differ by at most one. The median is the top of the larger heap, or the average of both tops.
Insertion is O(log k). The difficulty is expiry, since heaps do not support removing an arbitrary element.
Use lazy deletion: record the expired value in a hash map of pending removals and discard entries from the heap tops when they surface. Amortised cost stays O(log k).
The alternative is an order-statistic tree or a skip list, which supports direct deletion and is cleaner if the language provides one. Say which you would choose and why.
What it is testing
Data structure selection under a constraint the obvious structure does not meet.
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.
Design a limit order book
HardWhat data structures would you use for a limit order book that must add, cancel and match quickly?
Sample from a stream of unknown length
StandardPick one element uniformly at random from a stream whose length you do not know in advance, using constant memory.
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.