Stock Price Fluctuation
Asked at Atlassian
Problem
Design a data structure that tracks stock prices over time, supporting three operations: update(timestamp, price) to record a new price, current() to return the latest price, and maximum() / minimum() to return the highest and lowest prices recorded. Prices can be updated at the same timestamp, overwriting the previous value.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
Naive approach: store all (timestamp, price) pairs in a list. current() is O(1) (last element). maximum() and minimum() scan the entire list each time: O(n). This is too slow if maximum()/minimum() are called frequently.
Better: use a hash map (dictionary) mapping timestamp to price for O(1) updates and lookups. For max/min, maintain two heaps: a max-heap for maximum and a min-heap for minimum. This gives O(1) current, O(log n) update, O(1) amortized max/min.
The problem: heaps do not support efficient deletion of arbitrary elements. When you update a price at an existing timestamp, the old price is still in the heap. Solution: lazy deletion. Mark the old entry as stale in the hash map. When popping from the heap, skip entries where the hash map value does not match the heap top.
Data structures:
price_map:dict[timestamp] -> pricefor O(1) lookups.max_heap: stores(-price, timestamp)for max price (negate for max-heap in Python).min_heap: stores(price, timestamp)for min price.latest_timestamp: tracks the most recent timestamp forcurrent().
Lazy deletion example: timestamp 3 initially has price 100. Heap has (100, 3). Update timestamp 3 to price 50. Now price_map[3] = 50, but heap still has (100, 3). When you pop (100, 3) from min-heap, check price_map[3] == 100? No (it's 50). Discard and pop again.
Complexity: update() is O(log n) (two heap pushes). current() is O(1). maximum() and minimum() are O(log n) amortized (popping stale entries). Total space: O(n).
Optimal Approach
Maintain a hash map (price_map) mapping timestamp to price, a max-heap (max_heap) storing (-price, timestamp), and a min-heap (min_heap) storing (price, timestamp). Also track latest_timestamp.
update(timestamp, price):
- Store
price_map[timestamp] = price. - Push
(-price, timestamp)ontomax_heap. - Push
(price, timestamp)ontomin_heap. - Update
latest_timestampiftimestampis newer.
current():
- Return
price_map[latest_timestamp].
maximum():
- Peek at
max_heap[0]. Whileprice_map[heap_top.timestamp] != -heap_top.price, pop (stale entry). Return-max_heap[0][0].
minimum():
- Same lazy deletion logic on
min_heap. Returnmin_heap[0][0].
Walkthrough: update(1, 10), update(2, 5), update(1, 20).
price_map = {1: 20, 2: 5}. Heaps have stale (10, 1).maximum(): heap top is (-10, 1).price_map[1]is 20, not 10. Pop. Next is (-20, 1).price_map[1]is 20 = -(-20). Return 20.minimum(): heap top is (5, 2).price_map[2]is 5. Return 5.
Time: O(log n) update, O(1) current, O(log n) amortized max/min. Space: O(n).
What Trips People Up in Real Interviews
Forgetting that updating the same timestamp overwrites the old price. The heap still contains the old (price, timestamp) pair. Without lazy deletion, you would return stale max/min values.
Using a TreeMap / SortedDict for max/min. While this works (O(log n) for max/min), heaps are more commonly expected in interviews and the lazy deletion pattern is a valuable signal.
Not tracking the latest timestamp for current(). If you only use heaps, you cannot efficiently get the latest price. You need either a hash map or a separate variable.
Pushing duplicate entries into the heap without lazy deletion. Do NOT try to remove old entries from the heap — it is O(n). Instead, push new entries and skip stale ones when popping.
Forgetting that Python's heapq is a min-heap. For a max-heap, negate the price: push (-price, timestamp) and negate again when reading back.
Solution Code
import heapq
class StockPrice:
def __init__(self):
self.price_map = {}
self.max_heap = []
self.min_heap = []
self.latest_timestamp = 0
def update(self, timestamp: int, price: int) -> None:
self.price_map[timestamp] = price
heapq.heappush(self.max_heap, (-price, timestamp))
heapq.heappush(self.min_heap, (price, timestamp))
self.latest_timestamp = max(self.latest_timestamp, timestamp)
def current(self) -> int:
return self.price_map[self.latest_timestamp]
def maximum(self) -> int:
while self.max_heap:
price, ts = self.max_heap[0]
if self.price_map.get(ts) == -price:
return -price
heapq.heappop(self.max_heap)
return -1
def minimum(self) -> int:
while self.min_heap:
price, ts = self.min_heap[0]
if self.price_map.get(ts) == price:
return price
heapq.heappop(self.min_heap)
return -1Frequently Asked Questions
What is the Stock Price Fluctuation problem?
Design a data structure that tracks stock prices over time, supporting three operations: `update(timestamp, price)` to record a new price, `current()` to return the latest price, and `maximum()` / `minimum()` to return the highest and lowest prices recorded. Prices can be updated at the same timestamp, overwriting the previous value.
How do you solve Stock Price Fluctuation?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Stock Price Fluctuation?
Stock Price Fluctuation is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on Stock Price Fluctuation?
- Forgetting that updating the same timestamp overwrites the old price. The heap still contains the old (price, timestamp) pair. Without lazy deletion, you would return stale max/min values.
- Using a `TreeMap` / `SortedDict` for max/min. While this works (`O(log n)` for max/min), heaps are more commonly expected in interviews and the lazy deletion pattern is a valuable signal.
- Not tracking the latest timestamp for `current()`. If you only use heaps, you cannot efficiently get the latest price. You need either a `hash map` or a separate variable.
- Pushing duplicate entries into the heap without lazy deletion. Do NOT try to remove old entries from the heap — it is `O(n)`. Instead, push new entries and skip stale ones when popping.
- Forgetting that Python's `heapq` is a min-heap. For a max-heap, negate the price: push `(-price, timestamp)` and negate again when reading back.