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 that set was called previously with key and a timestamp less than or equal to the given timestamp. 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 the get operation, you can use binary search to quickly find the largest timestamp that is less than or equal to the given timestamp. This allows the get 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

1. Data Structure:
   Use a dictionary (or HashMap in Java) where each key maps to a list of pairs (timestamp, value). Because the set operations occur in order (or can be appended in order), the list for each key remains sorted by timestamp.

2. set(key, value, timestamp):

   • Append the pair (timestamp, value) to the list corresponding to key.

3. 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 "".

Step-by-Step Walkthrough

1. Initialization:
   Create an empty dictionary (or HashMap).

2. 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").

3. 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.

4. 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".

5. Subsequent set and get:

   • When set("foo", "bar2", 4) is called, append (4, "bar2") to the list for "foo".
   • Now, get("foo", 4) and get("foo", 5) will use binary search on [(1, "bar"), (4, "bar2")] to return "bar2" (the pair with timestamp 4).

Code Implementations

Python Code