About this question
Hard · Number Theory & Algorithms · Quant Trader interview question · running-median, order-book, market-impact, algorithms
You are building a high-frequency trading algorithm and need to estimate the impact of your trades on the mid-price of a stock. You observe a stream of recent order book updates (best bid and ask prices) for a particular stock. To estimate the impact of incoming orders, you decide to track the running median of the mid-price changes over the last $N$ updates, where the mid-price is the average of the best bid and ask. Suppose $N = 5$ and you have the following sequence of bid/ask prices: Update