Reservoir Sampling for Real-Time Data - Quant Trader Interview Question
Difficulty: Medium
Category: Algorithms & Data Structures
Practice quant interview questions from top firms including Jane Street, Citadel, Two Sigma, DE Shaw, and other leading quantitative finance companies.
Topics: algorithms, data-structures, probability, sampling, real-time
Problem Description
You are building a real-time trading analytics platform that needs to sample $k$ trade prices from a continuous stream of trades. The total number of trades, $n$, is unknown in advance. You need to select $k$ trades such that each trade has an equal probability of being included in the final sample. Which of the following algorithms achieves this with optimal time and space complexity?
Practice this medium trader interview question on MyntBit - the all-in-one quant learning platform with 200+ quant interview questions for Jane Street, Citadel, Two Sigma, and other top quantitative finance firms.