Design Historical Visit Tracker
Company: Uber
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: hard
Interview Round: Onsite
Design an in-memory component that stores visit events of the form `(visitor_name, timestamp)` and supports historical queries.
Requirements:
- `record_visit(name, ts)`: add one visit event.
- `get_single_visit_visitors(ts)`: return all visitor names whose number of visits with timestamp less than or equal to `ts` is exactly 1.
- Timestamps are integers and queries are inclusive.
- Multiple visits by the same visitor may exist.
- Discuss how your design changes if events arrive out of order, if queries are frequent, and if the data volume becomes large.
Explain the API, data structures, time complexity, and major trade-offs.
Quick Answer: This question evaluates design of in-memory data structures and event-processing APIs, focusing on efficient state maintenance for historical timestamped events, query semantics for cumulative counts, handling out-of-order arrivals, and scalability and time/space trade-offs.