Implement a Map with Time Expiration (Heap/Set)

To implement a time-expiring map, I would combine a Hash Map with a Min-Heap. The Hash Map stores the actual key-value pairs for O(1) retrieval, while the Min-Heap tracks the expiration timestamps paired with keys, allowing us to efficiently find the earliest expiring entry. When inserting a key, we calculate its absolute expiration time, update the map, and push the timestamp-key pair into the heap. For retrieval, we first check the map. Crucially, before returning any value, we run a lazy cleanup loop: we peek at the heap's root. If the root's timestamp is older than the current time, we pop it and remove the key from the map, repeating until the heap is empty or the top entry is valid. This ensures we don't scan the entire structure unnecessarily. While this approach keeps average lookup fast, I'd note that heavy cleanup spikes could occur; a production system might offload this to a background worker. This design mirrors Apple's focus on memory efficiency and responsiveness, ensuring stale data is removed without freezing the main thread during standard operations.