Decagon·Software Engineer·Technical Phone Screen
- Design a class with an insert method and a get_avg method, where get_avg returns the average of all values whose timestamps fall within a fixed time window ending at the given timestamp. Timestamps are guaranteed to be non-decreasing across calls.
- Follow-up: add an update method that can modify the value or refresh the timestamp of an existing record by its ID. What data structures would you need, and what are the tradeoffs between O(log n) and O(1) update complexity?
“The monotonic timestamp constraint is the key thing to notice early.”