Highest Price Query - Sliding Window Coding Interview

Question

## Problem

Given a stream of price updates `(symbol, price, timestamp)` in strictly increasing timestamp order, implement a `PriceTracker` that answers: "What is the highest price seen for `symbol` in the last `T` seconds?"

```python
class PriceTracker:
    def update(self, symbol: str, price: float, ts: int) -> None: ...
    def highest_in_window(self, symbol: str, ts_now: int, window: int) -> float:
        # Return max price seen in (ts_now - window, ts_now], or -1 if no data
        ...
```

**Example:**
```
pt = PriceTracker()
pt.update("AAPL", 150.0, 100)
pt.update("AAPL", 155.0, 200)
pt.update("AAPL", 148.0, 300)
pt.highest_in_window("AAPL", 300, 150)  -> 155.0  # window: (150,300]
pt.highest_in_window("AAPL", 300, 50)   -> 148.0  # window: (250,300]
```

## Follow-ups
- What data structure gives O(log n) `update` and O(log n) `highest_in_window`? (sorted list + segment tree)
- How would you extend this to return the top-k prices in a window?
- What if updates can arrive slightly out of order (within 5 seconds)? How do you handle late arrivals?

Highest Price Query - Sliding Window Coding Interview

Question Details

Full Details

Topics

More from Atlassian