30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System 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

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", "bar1", 1], ["set", "foo", "bar2", 4], ["get", "foo", 3], ["get", "foo", 5]]

Output:


[null, null, "bar1", "bar2"]

Explanation: set('foo', 'bar1', 1) stores bar1 at time 1. set('foo', 'bar2', 4) stores bar2 at time 4. get('foo', 3) returns bar1 (largest timestamp <= 3 is 1). get('foo', 5) returns bar2 (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 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', 'bar1', timestamp=1) and later set('foo', 'bar2', timestamp=4), the key 'foo' now has two values associated with different times.

When we call get('foo', timestamp=3), we need to return the value whose timestamp is the largest timestamp less than or equal to 3. In this case, that's 'bar1' (timestamp 1), not 'bar2' (timestamp 4).

Important constraint: Timestamps for a given key are strictly increasing - we'll never set the same key with a timestamp less than or equal to a previous timestamp for that key.

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 there are up to 2 * 10^5 operations?

Building Intuition

Since timestamps for each key are strictly increasing, the values for each key form a sorted list by timestamp.

When we need to find the value with the largest timestamp <= queried_timestamp, we're essentially searching for a floor value in sorted data.

Searching in sorted data can be done very efficiently using binary search, achieving O(log n) time instead of O(n) linear scan.

With up to 2 * 10^5 operations, this efficiency difference becomes critical - the difference between 200,000 comparisons and just 18 comparisons per lookup!

Think of organizing historical stock prices. For each stock symbol (key), you maintain a chronological list of (timestamp, price) pairs.

When someone asks 'What was the price at 3:45 PM?', you need to find the most recent price at or before 3:45 PM. Since prices are recorded in chronological order, you can use binary search to quickly locate the right entry instead of scanning through all historical records.

Common Mistakes

Using linear search instead of binary search for get() operations, resulting in O(n) time instead of O(log n)

Not handling the edge case where the queried timestamp is smaller than all stored timestamps for a key (should return empty string)

Attempting to sort timestamps on every get() call instead of leveraging the strictly increasing property

Using a single global sorted list instead of per-key lists, making it impossible to efficiently query by both key and timestamp

Incorrect binary search implementation for finding floor value - forgetting to track the last valid timestamp seen that's <= target

Optimal Solution

Use a hashmap where each key maps to a list of (timestamp, value) pairs. Since timestamps are strictly increasing per key, each list remains sorted by timestamp. For set() operations, append the new (timestamp, value) pair to the key's list in O(1) time. For get() operations, perform binary search on the key's sorted timestamp list to find the largest timestamp <= queried_timestamp in O(log n) time, where n is the number of values stored for that key.

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

from collections import defaultdict
import bisect

def time_map_demo(operations):
    """
    Simulate time-based key-value store operations.
    operations: list of tuples like ('set', key, value, timestamp) or ('get', key, timestamp)
    Returns list of get operation results.
    """
    # Initialize store: key -> list of (timestamp, value) pairs
    store = defaultdict(list)
    results = []
    
    # Process each operation
    for op in operations:
        if op[0] == 'set':
            # Extract set operation parameters
            _, key, value, timestamp = op
            # Append (timestamp, value) to key's list - O(1)
            store[key].append((timestamp, value))
        
        elif op[0] == 'get':
            # Extract get operation parameters
            _, key, query_timestamp = op
            
            # Check if key exists in store
            if key not in store:
                results.append("")
                continue
            
            # Get sorted list of (timestamp, value) pairs for this key
            pairs = store[key]
            
            # Binary search for largest timestamp <= query_timestamp
            # Extract just timestamps for binary search
            timestamps = [t for t, v in pairs]
            
            # Use bisect_right to find insertion point
            # bisect_right returns index where query_timestamp would go
            idx = bisect.bisect_right(timestamps, query_timestamp)
            
            # If idx is 0, no timestamp <= query_timestamp exists
            if idx == 0:
                results.append("")
            else:
                # idx-1 gives us the largest timestamp <= query_timestamp
                results.append(pairs[idx - 1][1])
    
    return results

Initialize time-based key-value store

0 / 74

Test Your Knowledge

Complexity Analysis

Time Complexity: O(1) for set, O(log n) for get set() appends to a list in constant time. get() performs binary search on a sorted list of timestamps, which takes logarithmic time relative to the number of entries for that key

Space Complexity: O(n) We store all key-value-timestamp tuples in the hashmap, where n is the total number of set operations performed

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 for floor value retrieval: Use binary search (bisect_right - 1 in Python, upper_bound - 1 in C++) to find the largest timestamp ≤ query time in O(log n) - this "floor search" pattern is critical for range queries where you need the most recent valid entry.
Monotonic timestamp guarantee optimization: When timestamps are strictly increasing per key, you can append to lists in O(1) without sorting - recognize this constraint in problem statements as it eliminates the need for insertion sort or post-insertion reordering.
Empty result edge case: Always check if binary search returns a valid index before accessing - if the query timestamp is smaller than all stored timestamps, your search will return -1 or an invalid position, requiring an empty string return rather than array access.
Time-series data pattern: This HashMap + Binary Search combination applies broadly to versioned data systems, stock price lookups, configuration history, and event logs - any scenario where you query "what was the state at time T?" benefits from this structure.
Space-time tradeoff insight: Storing all historical values trades O(n) space for O(log n) query time - compared to keeping only latest values, this temporal indexing enables point-in-time queries essential for audit trails, debugging, and time-travel features in real systems.

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

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