981. Time Based Key-Value Store - Detailed Explanation
Problem Statement
You are required to design a time-based key-value store that supports two operations:
-
set(String key, String value, int timestamp):
Stores the key and value, along with the given timestamp. -
get(String key, int timestamp):
Returns a value such thatset
was called previously withkey
and a timestamp less than or equal to the giventimestamp
. If there are multiple such values, it returns the one with the largest timestamp. If there is no such value, it returns an empty string (""
).
Example
Input:
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);
timeMap.get("foo", 1); // returns "bar"
timeMap.get("foo", 3); // returns "bar" since there is no value corresponding to key "foo" at timestamp 3, but timestamp 1 is the closest one less than or equal to 3.
timeMap.set("foo", "bar2", 4);
timeMap.get("foo", 4); // returns "bar2"
timeMap.get("foo", 5); // returns "bar2"
Explanation:
- The first
set
call stores the pair ("foo", "bar") at timestamp 1. - The first
get("foo", 1)
returns "bar" because that was set at timestamp 1. - The call
get("foo", 3)
returns "bar" because although there is no entry for timestamp 3, the latest timestamp less than or equal to 3 is 1. - After updating with
set("foo", "bar2", 4)
, the value at timestamp 4 becomes "bar2", and subsequent queries for timestamps ≥ 4 return "bar2".
Hints
-
Maintaining Sorted Order:
Since timestamps for each key are given in non-decreasing order (or you can assume they are stored in sorted order by definition of the problem), you can keep a list (or array) of (timestamp, value) pairs for each key. This makes it efficient to look up values later. -
Binary Search:
For theget
operation, you can use binary search to quickly find the largest timestamp that is less than or equal to the given timestamp. This allows theget
method to run in O(log n) time for a key with n entries. -
Dictionary / Hash Map:
Use a hash map (or dictionary) to map each key to its list of (timestamp, value) pairs.
Approaches to Solve the Problem
Approach: Dictionary with Sorted Lists and Binary Search
-
Data Structure:
Use a dictionary (orHashMap
in Java) where each key maps to a list of pairs (timestamp, value). Because theset
operations occur in order (or can be appended in order), the list for each key remains sorted by timestamp. -
set(key, value, timestamp):
- Append the pair
(timestamp, value)
to the list corresponding tokey
.
- Append the pair
-
get(key, timestamp):
- If the key is not in the dictionary, return
""
. - Otherwise, perform a binary search on the list of pairs to find the largest timestamp that is less than or equal to the given
timestamp
. - Return the corresponding value if found; otherwise, return
""
.
- If the key is not in the dictionary, return
Step-by-Step Walkthrough
-
Initialization:
Create an empty dictionary (orHashMap
). -
set Operation:
- When
set("foo", "bar", 1)
is called, check if "foo" exists in the dictionary. - Since it doesn't, create a new list and add the pair
(1, "bar")
.
- When
-
get Operation (Example 1):
- When
get("foo", 1)
is called, look up the list for "foo". - Perform a binary search on the list
[(1, "bar")]
to find the largest timestamp ≤ 1. - The binary search returns the pair
(1, "bar")
, so "bar" is returned.
- When
-
get Operation (Example 2):
- When
get("foo", 3)
is called, look up the list for "foo". - Even though there is no pair with timestamp 3, binary search finds the greatest timestamp that is ≤ 3 (which is 1).
- Return the value "bar".
- When
-
Subsequent set and get:
- When
set("foo", "bar2", 4)
is called, append(4, "bar2")
to the list for "foo". - Now,
get("foo", 4)
andget("foo", 5)
will use binary search on[(1, "bar"), (4, "bar2")]
to return "bar2" (the pair with timestamp 4).
- When
Code Implementations
Python Code
Explanation of Python Code:
-
We use the
bisect
module to perform binary search. The call tobisect_right(pairs, (timestamp, chr(127)))
finds the insertion point for a tuple where the timestamp is the given value. We subtract 1 to get the index of the largest timestamp that is ≤ the query. -
chr(127)
(or any high character) is used as a placeholder to ensure that the binary search compares only the timestamp if needed.
Java Code
Explanation of Java Code:
-
We use a
HashMap
to map each key to a list ofPair
objects (eachPair
contains atimestamp
and avalue
). -
The
set
method appends a newPair
to the list. -
The
get
method performs a binary search over the list to find the pair with the largest timestamp that is less than or equal to the given timestamp. The binary search is implemented manually here. -
The
main
method demonstrates usage and prints expected outputs.
Complexity Analysis
- Time Complexity:
- The
set
operation runs in O(1) time per call (amortized), since it appends to a list. - The
get
operation uses binary search over the list of pairs for a given key, running in O(log n) time per call, where n is the number of entries for that key.
- The
- Space Complexity:
- The space complexity is O(N) overall, where N is the total number of calls to
set
, as each call stores one pair in the dictionary.
- The space complexity is O(N) overall, where N is the total number of calls to
Common Pitfalls and Edge Cases
-
Key Not Present:
Ensure that if a key does not exist in the map,get
returns an empty string. -
No Valid Timestamp:
When the binary search does not find any pair with a timestamp ≤ the queried timestamp, the function should return an empty string. -
Timestamps in Order:
The solution assumes that the timestamps for each key are non-decreasing, so appending to the list keeps it sorted. If the input can be arbitrary, you would need to sort the list, which can increase complexity. -
Empty Input:
Consider edge cases such as callingget
before anyset
operations or with very early timestamps.
Related Problems for Further Practice
-
Design Log Storage System:
A problem where you design a system to store logs with timestamps and perform range queries. -
Find Latest Element:
Problems that involve binary search on a sorted list to find the latest element that meets a condition. -
Snapshot Array:
A problem where you take snapshots of an array and later retrieve values from a specific snapshot, also leveraging time/versioning.
GET YOUR FREE
Coding Questions Catalog
