Solution
Approach 1: HashMap + Binary Search
Intuition and Algorithm
For each key
we get or set, we only care about the timestamps and values for that key. We can store this information in a HashMap
.
Now, for each key
, we can binary search the sorted list of timestamps to find the relevant value
for that key
.
Complexity Analysis

Time Complexity: for each
set
operation, and for eachget
operation, where is the number of entries in theTimeMap
. 
Space Complexity: .
Approach 2: TreeMap
Intuition and Algorithm
In Java
, we can use TreeMap.floorKey(timestamp)
to find the largest timestamp smaller than the given timestamp
.
We build our solution in the same way as Approach 1, swapping in this functionality.
Complexity Analysis

Time Complexity: for each
set
operation, and for eachget
operation, where is the number of entries in theTimeMap
. 
Space Complexity: .
Analysis written by: @awice.