Design a Stock Price Fluctuation Tracker
Design a data structure that allows you to record a new stock price and immediately retrieve the maximum, minimum, and current price in $O(1)$ time. Use two heaps and a single variable.
Why Interviewers Ask This
Interviewers at Spotify ask this to evaluate your ability to optimize for real-time data consistency under strict latency constraints. They specifically test if you can balance memory efficiency with speed, ensuring you understand that standard sorting is too slow for live financial feeds. This question probes your mastery of heap properties and lazy deletion techniques to solve the 'stale node' problem in dynamic datasets.
How to Answer This Question
1. Clarify Requirements: Confirm that updates are immediate and that retrieving max/min must be O(1). Ask if duplicate prices or invalid timestamps need handling.
2. Propose Core Structure: Suggest using a hash map to store current valid prices for O(1) lookups and two heaps (min-heap and max-heap) to track extremes.
3. Address Staleness: Explain the critical challenge where old values remain in heaps after an update. Detail how to use the hash map as the source of truth to lazily remove stale entries during retrieval.
4. Define Operations: Walk through inserting a price (update map, push to both heaps) and retrieving max/min (pop from heap until top matches current map value).
5. Analyze Complexity: Conclude by stating time complexity is amortized O(log N) for insertions but O(1) for retrieval, and space complexity is O(N) due to storing all historical updates in heaps.
Key Points to Cover
- Identifying the 'stale node' problem inherent in using static heaps for dynamic data
- Proposing a hybrid structure combining a Hash Map for truth and Heaps for ordering
- Explaining the Lazy Deletion strategy to avoid expensive cleanup operations
- Distinguishing between worst-case O(log N) insertion and amortized O(1) retrieval
- Demonstrating awareness of memory overhead trade-offs in real-time systems
Sample Answer
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 ent…
Common Mistakes to Avoid
- Attempting to rebuild the entire sorted list on every update, resulting in O(N) retrieval time
- Forgetting to handle stale entries, leading to incorrect max/min values being returned
- Using a single heap for both min and max, which forces inefficient conversions or full scans
- Ignoring the memory cost of storing historical data in heaps when only current values matter
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.