Design timestamped key-value map

Question

Design a class that supports insert(key, value, timestamp) and get(key, timestamp) where get returns the value whose timestamp is the smallest timestamp ≥ the given timestamp, assuming inserts arrive in increasing timestamp order. Follow-up: How would you change the design if inserts arrive out of order (timestamps not strictly increasing)?

Timestamped Map with Ceiling Lookup

Implement a function to process operations on a timestamped key-value map. It supports two operations: (1) insert(key, value, timestamp): store the value for key at the given timestamp; (2) get(key, timestamp): return the value for key whose timestamp is the smallest timestamp greater than or equal to the given timestamp. If no such timestamp exists for the key, return null. Assume that all insert operations arrive in nondecreasing timestamp order across all keys. The function should return a list of results for all get operations in the order they appear.

Constraints

• 1 <= len(operations) <= 200000
• Each operation is either ["insert", key:str, value:str, timestamp:int] or ["get", key:str, timestamp:int]
• All insert operations appear in nondecreasing timestamp order (timestamps may be equal)
• 0 <= timestamp <= 1e9
• 1 <= len(key), len(value) <= 50
• The function returns results for get operations only; insert operations produce no direct output

Examples

Example 1

Input: operations = [["insert","a","x",1],["insert","b","y",3],["insert","a","z",4],["get","a",0],["get","a",1],["get","a",2],["get","b",2],["get","b",3],["get","c",5],["get","a",5]]
Output: ["x","x","z","y","y",null,null]

Explanation: For key a: timestamps [1->x, 4->z]. Ceil(0)=1->x, Ceil(1)=1->x, Ceil(2)=4->z, Ceil(5) doesn't exist -> null. For key b: timestamps [3->y]. Ceil(2)=3->y, Ceil(3)=3->y. Key c not present -> null.

Example 2

Input: operations = [["insert","k","v1",5],["insert","k","v2",5],["insert","k","v3",7],["get","k",5],["get","k",6],["get","k",8]]
Output: ["v1","v3",null]

Explanation: Timestamps for k: [5->v1, 5->v2, 7->v3]. Using ceiling: t=5 returns first at 5 -> v1; t=6 returns 7->v3; t=8 has no ceiling -> null.

Hints

1. Map each key to a sorted list of timestamps and a parallel list of values.
2. Because inserts are in nondecreasing timestamp order, you can append to each key's lists to keep them sorted.
3. Use binary search (bisect_left) on the timestamps list to find the first index with timestamp >= query.
4. If inserts were out of order, maintain each key's timestamps in sorted order via bisect.insort or use a balanced BST.

Approach

Maintain, for each key, a pair of parallel arrays: timestamps (sorted) and values. Because all inserts arrive in nondecreasing timestamp order, appending keeps the timestamps sorted. For a get(key, t) query, perform a binary search with bisect_left to find the smallest index i such that timestamps[i] >= t; if it exists, return values[i]; otherwise return None. If inserts arrive out of order, you would insert timestamps and values at the appropriate positions using bisect.insort (O(log m) per insert plus O(m) shifts in arrays) or use a balanced tree/skip list to keep inserts and queries both O(log m), where m is the number of entries for that key.

• Time complexity: Insert: O(1) amortized per operation (append); Get: O(log m) per query where m is the number of entries for the key
• Space complexity: O(N) where N is the total number of inserted entries