981. Time Based Key-Value Store - Detailed Explanation

Free Coding Questions Catalog
Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

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

  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

Python3
Python3

. . . .

Explanation of Python Code:

  • We use the bisect module to perform binary search. The call to bisect_right(pairs, (timestamp, chr(127))) finds the insertion point for a tuple where the timestamp is the given value. We subtract 1 to get the index of the largest timestamp that is ≤ the query.

  • chr(127) (or any high character) is used as a placeholder to ensure that the binary search compares only the timestamp if needed.

Java Code

Java
Java

. . . .

Explanation of Java Code:

  • We use a HashMap to map each key to a list of Pair objects (each Pair contains a timestamp and a value).

  • The set method appends a new Pair to the list.

  • The get method performs a binary search over the list to find the pair with the largest timestamp that is less than or equal to the given timestamp. The binary search is implemented manually here.

  • The main method demonstrates usage and prints expected outputs.

Complexity Analysis

  • Time Complexity:
    • The set operation runs in O(1) time per call (amortized), since it appends to a list.
    • The get operation uses binary search over the list of pairs for a given key, running in O(log n) time per call, where n is the number of entries for that key.
  • Space Complexity:
    • The space complexity is O(N) overall, where N is the total number of calls to set, as each call stores one pair in the dictionary.

Common Pitfalls and Edge Cases

  • Key Not Present:
    Ensure that if a key does not exist in the map, get returns an empty string.

  • No Valid Timestamp:
    When the binary search does not find any pair with a timestamp ≤ the queried timestamp, the function should return an empty string.

  • Timestamps in Order:
    The solution assumes that the timestamps for each key are non-decreasing, so appending to the list keeps it sorted. If the input can be arbitrary, you would need to sort the list, which can increase complexity.

  • Empty Input:
    Consider edge cases such as calling get before any set operations or with very early timestamps.

  • Design Log Storage System:
    A problem where you design a system to store logs with timestamps and perform range queries.

  • Find Latest Element:
    Problems that involve binary search on a sorted list to find the latest element that meets a condition.

  • Snapshot Array:
    A problem where you take snapshots of an array and later retrieve values from a specific snapshot, also leveraging time/versioning.

TAGS
leetcode
CONTRIBUTOR
Design Gurus Team
-

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
Practical resume editing services for senior-level engineers
Which is the best font for a resume?
Which database to use in system design interview?
Related Courses
Image
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.
Image
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Image
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
Image
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.