Design and Implement a Cross-System Object Tracker

Problem Description

In a distributed sensor network, different systems (e.g., Radar, LiDAR, Camera) generate their own unique IDs for the same physical object. You are tasked with designing an ObjectTracker class that maintains the observation history for these objects and links multiple system IDs to a single "Global Object."

Implement the following interface:

class ObjectTracker:
    def add_observation(self, system_id, object_id, timestamp, metadata):
        # Records an observation for a given object_id from a specific system.

    def link_systems(self, id1, id2):
        # Declares that id1 and id2 represent the same physical entity.

    def get_history(self, any_id):
        # Returns a sorted list of all observations for the global object associated with any_id.

Requirements

1. Merging: If link_systems(A, B) is called, all observations previously associated with A and B must now be linked to the same entity.
2. Consistency: Observations should be returned in chronological order. If timestamps are identical, maintain determinism (e.g., sort by system_id).
3. Idempotency: Calling link_systems(A, B) multiple times should have no side effects.
4. Scale: Assume a high volume of observations. Optimize for retrieving the history of an object.

Example

tracker = ObjectTracker()
tracker.add_observation("LIDAR", "L-1", 100, "loc:0,0")
tracker.add_observation("RADAR", "R-5", 105, "loc:1,1")
tracker.link_systems("L-1", "R-5")
# get_history("L-1") returns [(100, "L-1", "loc:0,0"), (105, "R-5", "loc:1,1")]

Edge Cases

• Linking IDs that have already been linked to different objects.
• Receiving observations for an ID that was linked after the observation was recorded.
• Handling empty history requests.