Katkat
Back

Implement a timestamped map

GustoSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a time-indexed key-value store that supports efficient lookups of historical values using binary search.

Problem Statement

Design a TimeMap class that supports storing multiple values for the same key at different timestamps and retrieving the value for a specific key at a specific timestamp.

Implement the TimeMap class:

  • __init__(): Initializes the object.
  • set(key: str, value: str, timestamp: int) -> None: Stores the key and value with the given timestamp.
  • get(key: str, timestamp: int) -> str: Returns the value associated with the key such that timestamp_prev <= timestamp. If there are multiple such values, return the value associated with the largest timestamp_prev. If no such value exists, return an empty string "".

Constraints

  • 1 <= key.length, value.length <= 100
  • 1 <= timestamp <= 10^7
  • All timestamp values in set are strictly increasing for a single key.
  • At most 2 * 10^5 calls will be made to set and get.

Examples

tm = TimeMap()
tm.set("foo", "bar", 1)
tm.get("foo", 1) # returns "bar"
tm.get("foo", 3) # returns "bar" (since 1 <= 3)
tm.set("foo", "bar2", 4)
tm.get("foo", 4) # returns "bar2"
tm.get("foo", 5) # returns "bar2"

Edge Cases

  • Searching for a timestamp smaller than any recorded for that key.
  • Searching for a key that does not exist.
  • Multiple set operations at different timestamps for the same key.

Hints

Hint 1

Use a hash map to store keys, where each key maps to a list of (timestamp, value) pairs.

Hint 2

Since timestamps are inserted in strictly increasing order, the list for each key is naturally sorted by timestamp.

Hint 3

Perform a binary search on the list of (timestamp, value) pairs to find the largest timestamp that is less than or equal to the requested timestamp.

Follow-up questions

  • How would your implementation change if timestamps were not provided in strictly increasing order?
  • What is the time complexity of `get` and `set`? Can you optimize `get` further if the frequency of queries for a specific key is extremely high?
  • How would you modify the system to delete a specific version of a key-value pair?