Katkat
Back

Implement an ObjectTracker That Merges Observations From Two Perception Systems

WaymoSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

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.

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.

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?

Hints

Hint 1

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 2

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.

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?