Design a Stock Price Fluctuation Tracker

To design this tracker efficiently, I would first clarify that we need to handle rapid updates where a stock price changes frequently. The core challenge is maintaining the maximum and minimum without re-scanning the entire dataset every time. My solution uses a combination of a hash map and two priority queues. I will maintain a hash map where the key is the timestamp or unique ID and the value is the current price. This acts as our single source of truth. For the heaps, I'll use a min-heap to track the lowest price and a max-heap for the highest. When a new price arrives, I update the hash map and push the new entry into both heaps. However, simply pushing isn't enough because old entries linger in the heaps. To handle this, I implement lazy deletion. When retrieving the maximum price, I check the top of the max-heap against the hash map. If the price in the heap doesn't match the current price in the map, it's stale, so I pop it and repeat. Once the tops match, I have the true maximum. The same logic applies to the minimum. While insertion takes O(log N), the retrieval is effectively O(1) on average because most checks pass immediately. This approach balances the need for instant access with the reality of changing data, which fits well with high-frequency trading environments.