Problem
Design a data structure that stores multiple values for the same key at different timestamps, and can retrieve the most recent value as of a given timestamp.
Implement a class TimeMap with the following operations:
-
set(key, value, timestamp)
-
Stores the string
value
for string
key
at integer
timestamp
.
-
get(key, timestamp) -> string
-
Returns the value associated with
key
at the
largest timestamp t such that t <= timestamp
.
-
If there is no such timestamp for the key, return an empty string
""
.
Notes / Constraints (typical)
-
key
and
value
are strings.
-
timestamp
is a positive integer.
-
set
calls for the same key may be given in increasing timestamp order (state your assumption; if not guaranteed, handle it).
-
Target complexity: about
O(log m)
per
get
, where
m
is the number of stored timestamps for that key.