Implement a Timestamped Counter
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a data structure that records calls to an `increment` method.
Requirements:
- Each call to `increment(timestamp)` receives an integer `timestamp`.
- Timestamps are strictly increasing across calls.
- Implement `query(t)` to return how many times `increment` was called with a timestamp greater than `t`.
Example:
- Calls: `increment(1)`, `increment(3)`, `increment(3)`, `increment(10)`
- `query(3)` should return `1` if `query` means strictly after `3`, or `1` plus any later duplicates depending on the exact interpretation. Make your API behavior explicit.
Follow-up discussion:
1. How would you support a very high call rate, where `increment` may be invoked many times per second?
2. How would you optimize query performance further?
3. If the requirements were extended to support counting calls in any time interval `[start, end]`, what data structures would you consider?
Quick Answer: This question evaluates the ability to design and implement time-indexed counting data structures, reason about strictly increasing timestamps and query semantics, and consider performance and scalability trade-offs.