Implement an ObjectTracker That Merges Observations From Two Perception Systems
Company: Waymo
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Onsite
Two separate software components perceive and track the objects around a vehicle. Call them System A and System B. Each assigns its own IDs to the objects it tracks, so one physical object has one ID in System A and a different ID in System B. Both systems emit observations: each observation carries a timestamp, the system that produced it, that system's ID for the object, and some metadata.
Design and implement an `ObjectTracker` that supports:
- `addLink(a_id, b_id)`: record that System A's object `a_id` and System B's object `b_id` are the same physical object;
- `addObservation(observation)`: store an observation from either system;
- `getHistory(system, id)`: return the full history of the physical object that `id` refers to in `system`.
The result of `getHistory` must:
- include all observations from both System A and System B for that object;
- be sorted in chronological order by timestamp;
- keep each observation's original source, source ID and metadata.
Write working code (any language) and explain the complexity of each operation.
```hint Identity is its own problem
Separate "which IDs refer to the same object" from "what was observed", and think about what happens when links chain together.
```
```hint Decide when to pay for order
Observations and links can arrive in any order. Choose whether history is kept sorted as it arrives or sorted when it is requested, and say why.
```
### Clarifying Questions
- Can one System A ID be linked to more than one System B ID (or the reverse)? If `a1` is linked to `b1` and `b1` to `a2`, are `a1` and `a2` the same object?
- Can a link arrive after observations for those IDs were stored, and should `getHistory` then include the earlier observations?
- How should observations with equal timestamps be ordered?
- What should `getHistory` return for an ID that has never been seen?
- Can links ever be removed or corrected?
- Roughly how many objects and observations per second, and how long must history be kept?
### What a Strong Answer Covers
- A data model that keeps each observation intact (source, source ID, timestamp, metadata) instead of merging records
- Correct handling of link chains, typically with a union-find (disjoint set) structure or an equivalent grouping
- Linking after observations already exist, merging the two histories correctly
- Chronological ordering with a deterministic tie rule, and where the sorting cost is paid
- Time and space complexity for each of the three operations
- Edge cases: unknown IDs, duplicate links, links between already-linked IDs, out-of-order timestamps
- Tests that exercise a chain of links and a link added after observations
### Follow-up Questions
- A link turns out to be wrong and must be removed. How does your structure change?
- History must be kept for only the last few minutes to bound memory. How do you expire old observations efficiently?
- Observations arrive concurrently from both systems on different threads. What needs synchronization?
- Callers now ask for the history within a time range. How do you answer that efficiently?
Overview: Two perception systems track the same objects under different IDs. Implement an ObjectTracker with addLink, addObservation and getHistory that returns an object's observations from both systems in timestamp order, testing identity grouping and history merging.