Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 981. Time Based Key-Value Store

Design a time-based key-value store that records multiple values per key with timestamps and returns the value whose timestamp is the largest <= the queried timestamp. With timestamps per key strictly increasing and up to 2e5 operations, the typical solution uses per-key ordered timestamp/value lists and binary search to find the floor timestamp efficiently.

Asked at:

OpenAI

Apple

Amazon

DESCRIPTION

Input:

operations = [["set", "foo", "bar", 1], ["get", "foo", 1], ["get", "foo", 3], ["set", "foo", "baz", 4], ["get", "foo", 4], ["get", "foo", 5]]

Output:

[null, "bar", "bar", null, "baz", "baz"]

Explanation: set('foo','bar',1) stores bar at timestamp 1. get('foo',1) returns 'bar' (exact match). get('foo',3) returns 'bar' (largest timestamp ≤ 3 is 1). set('foo','baz',4) stores baz at timestamp 4. get('foo',4) returns 'baz' (exact match). get('foo',5) returns 'baz' (largest timestamp ≤ 5 is 4).

Constraints:

1 <= key.length, value.length <= 100
key and value consist of lowercase English letters and digits
1 <= timestamp <= 10^7
All timestamps for set operations are strictly increasing per key
At most 2 * 10^5 calls total to set and get

Understanding the Problem

Let's understand what we're being asked to design. We need a time-based key-value store that can store multiple values for the same key, each with a different timestamp.

For example, if we do set('foo', 'bar', 1) and later set('foo', 'baz', 3), the key 'foo' now has two values: 'bar' at timestamp 1 and 'baz' at timestamp 3.

When we call get('foo', 2), we need to return the value whose timestamp is the largest timestamp less than or equal to 2. In this case, that's 'bar' (timestamp 1), because timestamp 3 is too large.

Important constraint: Timestamps for each key are strictly increasing - we never set the same key with an earlier timestamp than a previous set. This means for each key, the timestamps are naturally sorted!

Edge cases to consider: What if we get() a key that doesn't exist? What if we get() with a timestamp smaller than all stored timestamps for that key? What if we have up to 2e5 operations - how do we keep get() efficient?

Brute Force Approach

Store a hash map where each key maps to a list of (timestamp, value) pairs. For set(), append the new pair to the key's list. For get(), iterate through the entire list for that key, checking each timestamp to find the largest one that is ≤ the query timestamp. This approach is simple to implement but requires scanning all timestamps for each get() operation, making it inefficient when a key has many historical values.

Building Intuition

For each key, we're storing a list of (timestamp, value) pairs that grows over time. Because timestamps are strictly increasing, this list is automatically sorted by timestamp.

When we get(key, timestamp), we need to find the largest timestamp in the list that is ≤ our query timestamp. This is a classic 'floor' search problem.

Searching for a floor value in a sorted list can be done in O(log n) time using binary search, rather than O(n) time with linear search.

With up to 2e5 operations and potentially many get() calls, this logarithmic speedup is crucial for performance.

Think of organizing historical stock prices by timestamp. If someone asks 'What was the price at 2:30 PM?', you look through your sorted list of timestamps and find the most recent price before or at 2:30 PM.

You don't need to check every single timestamp - you can use the sorted property to quickly narrow down to the right time range. The sorted timestamps are what make this efficient lookup possible.

Common Mistakes

Forgetting to handle the case where the key doesn't exist in the hash map - should return empty string, not throw an error

Not handling the case where all timestamps for a key are greater than the query timestamp - should return empty string since no valid floor exists

Using linear search instead of binary search for get() - this makes the solution too slow for large inputs with many timestamps per key

Implementing binary search incorrectly for floor queries - need to track the last valid timestamp seen that is ≤ target, not just check for exact match

Not initializing the hash map value as an empty list when encountering a new key - this causes errors when trying to append

Optimal Solution

Use a hash map where each key maps to a list of (timestamp, value) pairs. Since timestamps are strictly increasing per key, each list is automatically sorted by timestamp. For set(), append the new pair to the key's list in O(1) time. For get(), perform binary search on the key's timestamp list to find the largest timestamp ≤ the query timestamp in O(log n) time. This takes advantage of the sorted property to achieve logarithmic lookup time.

Format: [['put', key, value], ['get', key]]

Visualization

from collections import defaultdict
import bisect
def time_map_demo(operations):
    """
    Simulate TimeMap operations: set(key, value, timestamp) and get(key, timestamp).
    Returns list of get() results.
    """
    # Initialize hash map: key -> list of (timestamp, value) pairs
    store = defaultdict(list)
    results = []
    
    # Process each operation
    for op in operations:
        operation_type = op[0]
        
        if operation_type == "set":
            key = op[1]
            value = op[2]
            timestamp = op[3]
            
            # Append (timestamp, value) to key's list (auto-sorted since timestamps increase)
            store[key].append((timestamp, value))
            
        elif operation_type == "get":
            key = op[1]
            query_timestamp = op[2]
            
            # Get the list of (timestamp, value) pairs for this key
            if key not in store:
                results.append("")
                continue
            
            pairs = store[key]
            
            # Binary search: find largest timestamp <= query_timestamp
            left = 0
            right = len(pairs) - 1
            result_value = ""
            
            while left <= right:
                mid = (left + right) // 2
                
                if pairs[mid][0] <= query_timestamp:
                    # This timestamp is valid, store value and search right half
                    result_value = pairs[mid][1]
                    left = mid + 1
                else:
                    # This timestamp is too large, search left half
                    right = mid - 1
            
            results.append(result_value)
    
    return results

Start TimeMap simulation

0 / 95

Test Your Knowledge

Complexity Analysis

Time Complexity: O(1) for set, O(log n) for get where n is the number of timestamps for that key set() appends to a list in O(1). get() uses binary search on a sorted list of timestamps, which takes O(log n) time where n is the number of values stored for that key.

Space Complexity: O(m) where m is the total number of set operations across all keys We store every (timestamp, value) pair that was ever set, so space grows linearly with the number of set operations.

What We've Learned

HashMap + Sorted List hybrid structure: When you need to store multiple time-series values per key, combine a HashMap for O(1) key lookup with per-key sorted lists for temporal ordering - this dual-layer structure enables efficient access by both key and time dimension.
Binary search on timestamps: Since timestamps are strictly increasing per key, use binary search (bisect_right/upper_bound - 1) to find the largest timestamp ≤ query in O(log n) time - this is the floor-finding pattern essential for time-based lookups.
Monotonic property exploitation: When a problem guarantees strictly increasing timestamps, you can skip insertion sorting and simply append to the list - recognizing monotonic guarantees saves O(n) per insertion and simplifies implementation significantly.
Off-by-one in binary search: The critical mistake is using bisect_left instead of bisect_right - you need bisect_right then subtract 1 to find the floor timestamp, or check if bisect_left's result has an exact match before using it as the answer.
Time-series data pattern: This HashMap-of-sorted-arrays pattern applies broadly to versioned data, event logs, stock prices, sensor readings - whenever you need point-in-time queries on historical data with temporal ordering per entity.
Space-time tradeoff awareness: Storing all historical values costs O(n) space but enables O(log n) queries - understand that precomputing and storing sorted data trades memory for query speed, which is optimal when reads vastly outnumber writes.

Test Your Understanding

Why is hashmap the right data structure for this problem?

hashmap provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late November, 2025

Apple

Mid-level

Mid October, 2025

OpenAI

Senior

Early August, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More