I applied for this position online on a whim and didn't expect to actually land an interview. The company works in public safety.
The question was to design a system for looking up an officer's status record near a given point in time.
The system continuously receives data from police officers' devices. For each officer, while they're active, their device generates a record every 5 seconds. Each record contains at minimum an officer_id, a timestamp, and the corresponding status data.
One thing to note: because of network latency and other factors, this data can arrive at the system out of order. For example, a record with timestamp 10:00:10 might arrive before a record with timestamp 10:00:05. So the system can't assume the data arrives in timestamp order.
The system needs to support this kind of query: given an officer_id and a target timestamp, find that officer's record whose timestamp is closest to the target.
For example, say an officer has two records:
t1 = 10:00:05
t2 = 10:00:10
If the query timestamp is 10:00:07, it's 2 seconds from t1 and 3 seconds from t2, so it should return the record for t1.
In other words, if the query timestamp falls between two records t1 and t2, you compute the time difference to each and return whichever one is closer. If the query time falls exactly halfway between the two records, you need to define a fixed rule — for example, always prefer the earlier record.
Also, the system only needs to keep the most recent 12 hours of data. This is a rolling 12-hour window — as time moves forward, data older than 12 hours needs to be automatically deleted and excluded from queries, to keep storage under control.
So the system basically needs to solve three problems:
- How to handle data that arrives out of order.
- How to efficiently find, given an officer_id and a timestamp, the record closest in time.
- How to maintain a rolling 12-hour window and efficiently evict expired data.
Discussion
Loading comments…