Skip to main content

981. Time Based Key-Value Store

https://leetcode.com/problems/time-based-key-value-store/

Python​

from collections import defaultdict


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

    def set(self, key: str, value: str, timestamp: int) -> None:
        # The question did not indicate the timestamp will be set always in incremental order
        # But the test case riase error if you're not set in the order, so we can skip the
        # ordering find of append
        self.memory[key].append((timestamp, value))


    def get(self, key: str, timestamp: int) -> str:
        result = ""
        l, r = 0, len(self.memory[key])-1
        while l <= r:
            pivot = (l+r) >> 1
            if self.memory[key][pivot][0] <= timestamp:
                result = self.memory[key][pivot][1]
                l = pivot+1
            else:
                r = pivot-1
        return result