Object Tracker with Cross-System Identity Links

Implement an Object Tracker with Cross-System Identity Links There are two independent software components: System A and System B. Each independently detects and tracks real-world objects, assigning IDs that are unique only within that system. The same real-world object may be tracked by both systems under different IDs. Design and implement an ObjectTracker with the following APIs: addLink(a_id, b_id) addObservation(observation) getHistory(system, id) Where: addLink(a_id, b_id) declares that System A ID a_id and System B ID b_id refer to the same real-world object. addObservation(observation) adds an observation containing: timestamp: a comparable timestamp; source: either "A" or "B"; source_id: the object ID in that source system; metadata: additional data that must be preserved unchanged. getHistory(system, id) receives an ID from either system and returns all observations for the corresponding real-world object. The returned history must: include observations from both System A and System B; be in ascending chronological order by timestamp; preserve every observation's original source, source_id, and metadata. Links may be added before or after observations. Multiple addLink calls may form transitive connections for the same real-world object. After links are merged, querying through any linked ID must return the complete history. Target complexity: links and inserts should be near amortized O(α(N)), excluding any necessary history merge; sorting a query result may take O(K log K), where K is the number of observations. Example Input addObservation {"timestamp":3,"source":"A","source_id":"a1","metadata":{"x":1}}\naddObservation {"timestamp":1,"source":"B","source_id":"b1","metadata":{"x":2}}\naddLink a1 b1\ngetHistory A a1 Output [{"timestamp":1,"source":"B","source_id":"b1","metadata":{"x":2}},{"timestamp":3,"source":"A","source_id":"a1","metadata":{"x":1}}]