Link Object Tracks Across Two Perception Systems and Merge Their Histories

Two perception systems, A and B, track objects in the same scene independently. Each system 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, and each system records observations of its tracks over time. Design and implement a class with these operations: - `link(id_a, id_b)`: record that track `id_a` of system A and track `id_b` of system B are the same object. - `add_observation(system, track_id, timestamp, data)`: record that `system` (`"A"` or `"B"`) observed its track `track_id` at `timestamp`, with an opaque payload `data`. - `get_history(system, track_id)`: given an id from either system, return every observation of that object from both systems, merged into one list ordered by timestamp. The problem is given verbally, and the rules for `link` are not specified up front. Settling them with the interviewer is part of the task, and several of the clarifying questions below change the data structure you need. Write working code, and leave time to test it on the tricky cases. ```hint Group ids, not pairs Picture several links arriving over time that chain ids on both sides together. What structure lets you answer "which ids belong to the same object as this one" quickly while links keep arriving? ``` ```hint Merge on write or on read Decide whether the combined, time-ordered history is built when observations and links arrive or when a history is requested, and what each choice costs when a link arrives after many observations were already recorded. ``` ### Clarifying Questions - Is linking strictly one-to-one, or can one track in A be linked to several tracks in B, and the reverse? - Are links transitive? If `a1` is linked to `b1` and `a2` is also linked to `b1`, are `a1` and `a2` the same object? - Can a link arrive after observations were already recorded for either id, and must the history then include those earlier observations? - Can a link be removed or replaced later? - Do a track's observations arrive in timestamp order? How should observations with equal timestamps be ordered? - What should `get_history` return for an id that was never seen, or for an id with no links? - Can system A and system B use the same id value for different objects? ### What a Strong Answer Covers - Linking semantics agreed before coding: cardinality, transitivity, late links and removal - A grouping structure that keeps all ids of one object together as links merge groups - A correctly merged history with a stated tie-break and the source system of each observation - The cost of `link`, `add_observation` and `get_history`, and which operation the design optimizes - Tests for chains of links, late links, unknown ids and equal timestamps - Clarification kept bounded, so that there is time to run the tests ### Follow-up Questions - Add `unlink` for a link that turns out to be wrong. What does your structure need in order to support it? - `get_history` is called far more often than `link`, and histories are long. How do you make reads cheap? - How does the design change with three or more perception systems? - How would you return only the part of a history that falls inside a time range?