About this question
Medium · Algorithms & Data Structures · Quant Trader interview question · algorithms, data-structures, probability, sampling, real-time
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?