How to Solve Time Based Key-Value Store

This problem requires designing a data structure to store multiple values per key along with timestamps and retrieve the most recent value efficiently. Use a hash table to map keys to timestamped value lists and binary search to quickly locate the latest valid value for a query timestamp. Understanding the strictly increasing timestamp constraint is crucial for correctness and performance.

Problem Statement

Design a data structure called TimeMap that supports storing multiple values for the same key at different timestamps and retrieving the key's value at a given timestamp. Each key can have several values, but queries should return the most recent value no later than the requested timestamp.

Implement the following operations: set(key, value, timestamp) which stores the value along with its timestamp, and get(key, timestamp) which returns the value set at or before the timestamp. If no such value exists, return an empty string. All timestamps are strictly increasing for each key.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["TimeMap", "set", "get", "get", "set", "get", "get"] [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]] Output [null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation TimeMap timeMap = new TimeMap(); timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1. timeMap.get("foo", 1); // return "bar" timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar". timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4. timeMap.get("foo", 4); // return "bar2" timeMap.get("foo", 5); // return "bar2"

Constraints

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits.
• 1 <= timestamp <= 107
• All the timestamps timestamp of set are strictly increasing.
• At most 2 * 105 calls will be made to set and get.

Solution Approach

Use a Hash Map to Store Timestamped Values

Maintain a hash map where each key maps to a list of (timestamp, value) pairs. This allows O(1) access to the key's history and ensures that all timestamped values are stored in strictly increasing order, which is essential for applying binary search during retrieval.

Binary Search Over the Timestamp List

When retrieving a value for a given timestamp, perform binary search on the list of stored timestamps for that key. This efficiently finds the largest timestamp less than or equal to the query, avoiding linear scans and ensuring O(log n) query time per key.

Handle Edge Cases and Nonexistent Keys

If a key does not exist or the query timestamp is earlier than any stored timestamp, return an empty string. Ensure that the search correctly handles the boundary conditions, as failing to do so is a common source of errors in this problem.

Complexity Analysis

Setting a value is O(1) because it appends to a list. Getting a value requires O(log n) binary search where n is the number of timestamps for that key. Space complexity is O(m) where m is the total number of set operations stored across all keys.

What Interviewers Usually Probe

• Ask if you can assume timestamps are strictly increasing per key.
• Check if the candidate uses binary search instead of linear scan for retrieval.
• Confirm handling of keys with no stored value at the queried timestamp.

Common Pitfalls or Variants

Common pitfalls

• Performing linear search instead of binary search for get operations, leading to timeouts.
• Not handling empty lists or keys with no stored timestamps properly.
• Incorrectly implementing binary search boundaries, returning the wrong value for edge timestamps.

Follow-up variants

• Support deletion of key-value pairs at specific timestamps.
• Allow multiple keys with overlapping timestamp ranges and query across them.
• Retrieve all values within a given timestamp range instead of just the latest one.

How GhostInterview Helps

• Provides step-by-step guidance to implement the TimeMap with hash map and binary search correctly.
• Highlights edge cases where retrieval could fail due to timestamp boundaries or missing keys.
• Explains performance trade-offs and ensures your solution meets O(log n) query efficiency requirements.

Topic Pages

• Hash Table
• String
• Binary Search
• Design

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

Why do we need binary search in Time Based Key-Value Store?

Binary search efficiently finds the most recent value at or before the given timestamp, avoiding a slow linear scan over all stored values for a key.

Can timestamps be repeated for the same key?

No, timestamps are strictly increasing for each key, which ensures that each binary search retrieves a unique latest value.

What should get return if no value exists at the query timestamp?

It should return an empty string if the key doesn't exist or the query timestamp is earlier than any stored timestamp.

How does GhostInterview help with edge cases?

It points out boundary conditions, such as querying before the first timestamp or at exact timestamp matches, ensuring correct implementation.

What is the space complexity for storing Time Based Key-Value data?

Space complexity is O(m), where m is the total number of set operations across all keys, because each (timestamp, value) pair is stored.