We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Time Based Key-Value Store

Difficulty: Medium

Problem Description

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

  • TimeMap() Initializes the object of the data structure.
  • void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
  • String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

Key Insights

  • The set method allows storing values with associated timestamps, which must be unique for each key.
  • The get method requires efficient retrieval of the most recent value before or at a given timestamp.
  • A combination of a hash table and a sorted list (or binary search) can optimize both set and get operations.

Space and Time Complexity

Time Complexity:

  • set: O(1)
  • get: O(log n) (due to binary search)

Space Complexity: O(n) for storing the values and timestamps.

Solution

The solution utilizes a hash table (dictionary) to map each key to a list of tuples, where each tuple contains a timestamp and its corresponding value. This allows for efficient storage and retrieval. The set method appends the value and timestamp to the list for the given key. The get method performs a binary search on the list of timestamps to find the largest timestamp less than or equal to the requested timestamp, returning the associated value.

Code Solutions

class TimeMap:

    def __init__(self):
        # Initialize a dictionary to store key-value pairs with timestamps
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        # If the key doesn't exist, initialize it with an empty list
        if key not in self.store:
            self.store[key] = []
        # Append the (timestamp, value) pair to the list for the key
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        # If the key doesn't exist, return an empty string
        if key not in self.store:
            return ""
        # Retrieve the list of (timestamp, value) pairs for the key
        timestamps_values = self.store[key]
        # Implement binary search to find the correct value
        left, right = 0, len(timestamps_values) - 1
        while left <= right:
            mid = (left + right) // 2
            if timestamps_values[mid][0] <= timestamp:
                left = mid + 1
            else:
                right = mid - 1
        # If right is negative, no valid timestamp was found
        if right == -1:
            return ""
        # Return the value associated with the largest timestamp less than or equal to the given timestamp
        return timestamps_values[right][1]
← Back to All Questions