Time Based Key-Value Store

Time Based Key-Value Store

What is this problem about?

Imagine a database where a single key can have different values at different points in time. A "Time Based Key-Value Store" asks you to design a data structure that supports two operations: set(key, value, timestamp) and get(key, timestamp). The set operation stores a value at a specific time. The get operation retrieves the value that was most recently set at or before the given timestamp. If no such value exists, it should return an empty string.

Why is this asked in interviews?

This time based key-value store interview question is a favorite for many top tech companies, including Google, Amazon, Meta, and Bloomberg. It tests your ability to design a complex data structure that combines hash tables for quick key lookup with sorted lists for efficient time-based searches. It evaluates your proficiency with binary search and your understanding of how to manage versioned data.

Algorithmic pattern used

The problem utilizes the Hash Table, Design, Binary Search, String interview pattern.

1. Use a Hash Map to store the keys. Each key maps to a list of (timestamp, value) pairs.
2. Since timestamps in set calls are usually strictly increasing, the list of pairs for each key will be sorted by timestamp automatically.
3. For the get operation:
   • Look up the key in the Hash Map to get the list of versioned values.
   • Perform a binary search (specifically upper_bound or bisect_right) on the timestamps in the list to find the largest timestamp that is less than or equal to the target timestamp.
   • Return the corresponding value.

Example explanation

1. set("foo", "bar", 1)
2. set("foo", "bar2", 4)
3. get("foo", 1) -> Returns "bar".
4. get("foo", 3) -> The most recent value at or before time 3 is from time 1, which is "bar".
5. get("foo", 4) -> Returns "bar2".
6. get("foo", 5) -> Returns "bar2".
7. get("foo", 0) -> Returns "" (no values before time 1).

Common mistakes candidates make

In "Time Based Key-Value Store coding problem," a common mistake is using a simple linear scan for the get operation, which leads to O(N) complexity instead of the required O(log N). Another error is not correctly handling the binary search boundaries, leading to "off-by-one" errors. Finally, some might try to use a complex balanced BST instead of a simple sorted list, which adds unnecessary overhead.

Interview preparation tip

Binary search is the standard tool for finding a value in a sorted list. Practice applying it to problems where the "list" is hidden inside another data structure like a hash map. Also, be sure you understand the difference between finding an exact value and finding the "closest value less than or equal to" a target.