My friend got asked this for a Bloomberg Systems Design interview recently. The start of the interview however mainly focused on the algorithmic approach to the system, which is what this post is focusing on.

The question was to build a stock notification system. The system monitors the stock price of various companies in real time, and a user can subscribe to any of these companies to recieve alerts. Specfically, a user would want to receive an alert when the price of a company falls above/below X% within Y minutes. X and Y are variables that the user can set, where X is the % change and Y is the window in which that change can occur.

In terms of the data, you have a constant stream of stock tick data (stockID, price, timestamp). The price of a stock is changing at every millisecond or so. The interviewer was asking questions about algorithmiacally how you would calculate this change, and wanted to see how you could do it in both a time and space efficient way. A lot of the discussion was focussed on how much data would you actually want to log/save. It seems like there should be a way to do this without storing a huge stream of data.

What makes this question a bit more tricky is that you are not just looking at changes between fixed intervals. i.e. Lets say you set an alert for a X% change within a 10 minute window. You are not looking whether there is a 10% change at any point between t = 0 to t = 9, then t = 10 to t = 19, etc. Rather you are looking at t = 0 to t = 9, then t = 1 to t = 10, t = 2 to t = 11, etc.

A naieve approach to solve this would be to log the data at every millsecond and at every point, iterate backwards for 10 mins to find the minimum and maximum value. Then calculate the % change and see if this change is equal to or bigger than the threshold. This solution would be O(n * k) though where k is your window size.

I think this can be done better using a min heap and a max heap. At every new datapoint we can do the following:

Add KV pair (price, time) to the min heap
Add KV pair (price, time) to the max heap

while the timestamp of the KV pair at the top of our minheap is outside our window 
	poll the minheap 
//(i.e. if our interval is 10, the current time is t = 11 and minHeap.peek has a time of t = 0, then we would poll this)

//same concept for the maxheap
while the timestamp of the KV pair at the top of our maxheap is outside our window 
	poll the maxheap
	
now peek the minHeap and maxHeap and calculate the % change between them. If its equal to or above threshold, alert the user. 

Space complexity of this however would be O(N) worst case (imagine an always increasing stock, the max heap would just keep growing). And I think the time complexity of this would be O(N log K), but I'm not too sure!

If someone could comment on the time/space complexity of my algorithm, or suggest some alternative better ones, that would be great!

There is an interesting discussion on stackoverflow on something like this, couldn't make sense of some of the solutions though: https://stackoverflow.com/questions/23281172/efficiently-accumulate-sliding-window-percentage-changes-of-large-dataset