Time-Based Key-Value Store

To solve this, I would first clarify that timestamps for a specific key are always inserted in increasing order. This assumption allows us to optimize our storage mechanism. I propose using a HashMap where each key points to a List or Array of objects containing the timestamp and the associated value. Because the input timestamps are sorted, we can simply append new entries to the end of the list during the set operation, ensuring an O(1) time complexity for writes. For the get operation, when a user queries a specific timestamp, we need to find the most recent value with a timestamp less than or equal to the query. Since our list is sorted by time, we can employ Binary Search to locate the correct index in O(log N) time. If the query timestamp is smaller than the earliest entry, we return an empty string or null. This approach balances memory efficiency with fast retrieval. In terms of space, we store exactly one entry per set call, resulting in O(N) space complexity where N is the total number of operations. This solution aligns well with Apple's focus on high-performance, low-latency systems where minimizing unnecessary computation during reads is critical.