# Design and Implement a Cross-System Object Tracker ### Prompt Two independent systems, `A` and `B`, observe real-world objects. Each system assigns its own unique string ID, so the same object can have an `A` ID and a different `B` ID. Design an in-memory `ObjectTracker` with these operations: ```text add_link(a_id, b_id) add_observation(observation) get_history(system, object_id) ``` An observation contains a source system, that system's object ID, a timestamp, and arbitrary metadata. `add_link` states that an `A` ID and a `B` ID refer to the same real object. `get_history` must accept either system's ID and return all observations known for that real object, ordered chronologically while retaining each observation's original source, source ID, timestamp, and metadata. Discuss the data structures, method behavior, complexity, and handling of observations that arrive before a link. **Candidate hint:** Model identity resolution separately from observation storage, and define what must happen when two previously independent records are linked. ### Constraints & Assumptions - Calls may be repeated, and observations may arrive out of timestamp order. - Links are valid; contradictory identity claims do not need automatic resolution, but they should be detectable. - Equal timestamps need a deterministic tie-breaker. - The metadata object must be preserved rather than rewritten into a system-neutral shape. ### Clarifying Questions to Ask - Can one real object ever have multiple IDs from the same source system? - Does `get_history` need a snapshot under concurrent writes? - Is low write latency or low read latency more important? - Is observation deduplication based on an event ID, or are identical-looking events distinct? ### What a Strong Answer Covers - A precise representation for source-qualified IDs and resolved object identity - Correct merging when a late link joins two histories - A deliberate strategy for chronological ordering and deterministic ties - Idempotency, duplicate handling, invalid links, and thread-safety boundaries - Complexity and trade-offs between sorting on write, sorting on read, and indexed storage ### Follow-up Questions 1. How would the design change if more than two tracking systems were added? 2. How would you support pagination over a very large history? 3. How would you undo a bad link after histories have been merged? 4. What would you persist so the tracker can recover after a process restart?