Stock Price Fluctuation

Stock Price Fluctuation

What is this problem about?

The Stock Price Fluctuation coding problem asks you to design a system that tracks the price of a stock over time. The system receives updates in the form of (timestamp, price). However, updates can arrive out of order, and a price for a previously recorded timestamp can be corrected. You need to provide the current price (at the latest timestamp), as well as the maximum, minimum, and latest prices recorded in the system at any given time.

Why is this asked in interviews?

This problem is a favorite at Microsoft, Meta, and Google because it tests your ability to choose and combine data structures for efficient updates and queries. It's a classic "system design in a single class" problem. You must handle high-frequency updates while maintaining sorted information (for min/max) and historical accuracy. It evaluates your understanding of the Data Stream and Ordered Set interview pattern.

Algorithmic pattern used

To solve this efficiently, you need a combination of data structures.

• Latest Price: A simple Hash Table (Map) to store timestamp -> price and a variable to track the maxTimestamp.
• Min/Max Prices: A Heap (Priority Queue) or an Ordered Set (TreeMap/TreeSet). Since prices can be updated, a simple heap might contain "stale" prices. You can handle this by either removing the old price from an ordered set or by lazily removing invalid entries from the top of the heap (checking if the price at the top matches the current price for that timestamp in your map).

Example explanation (use your own example)

1. Update(10, 100): Map={10:100}, Latest=100, Min=100, Max=100.
2. Update(5, 50): Map={10:100, 5:50}, Latest=100 (time 10), Min=50, Max=100.
3. Update(10, 110): Map={10:110, 5:50}, Latest=110, Min=50, Max=110. Note how the update for time 10 changed both the latest price and the maximum price. If we query current(), we return 110 because 10 is the largest timestamp.

Common mistakes candidates make

• Inefficient Min/Max: Using a simple list and calling min() and max() on every query, which is $O(N)$.
• Stale Data: Forgetting that an update to an existing timestamp makes the previous price for that timestamp invalid.
• Out-of-order timestamps: Assuming that the most recent update() call always contains the current() price.
• Choosing the wrong Heap: Using a heap without a mechanism to handle invalid/updated entries.

Interview preparation tip

When designing a class with multiple requirements (like latest, min, and max), don't try to find one data structure that does everything. Usually, the solution involves using a Hash Table for $O(1)$ lookups and an Ordered Set or Heap for $O(\log N)$ range queries.