Time Based Key-Value Store

The problem description can be found in LeetCode.

Approach

As usual, asking clarifying questions is fundamental in a coding interview. For this problem in particular, we have the requirements stating that:

All the timestamps timestamp of set are strictly increasing.

This is so important in the design of the solution of this problem. In fact, this requirement is telling us that timestamp will be a sorted sequence in the end. Therefore, as we already read about in other problems, this is a clear indicator that Binary Search could be used to improve the overall time complexity.

Solution

from collections import defaultdict


class TimeMap:
    def __init__(self):
        self.d = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d[key].append((value, timestamp))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.d:
            return ""

        vals = self.d[key]
        left, right = 0, len(vals) - 1
        idx = -1

        while left <= right:
            mid = (left + right) // 2
            if vals[mid][1] <= timestamp:
                left = mid + 1
                idx = mid
            else:
                right = mid - 1

        return vals[idx][0] if idx != -1 else ""

Complexity

• set:
  • Time: $O(1)$
  • Space: $O(1)$
• get:
  • Time: $O(log(n))$
  • Space: $O(1)$

Where $n$ is the size of the list pointed by the key key.