unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 981: Time Based Key-Value Store

link

Note, if get() is called for a timestamp that was not set, we need to find the latest value until that timestamp. In other words, say for a key, we have (1, val1), (2, val2, 2), (5, val3) where 1, 2, and 5 are timestamps. For that key, if get() is now called with timestamp = 3, we need to return val2. Since, timestamps in set() are strictly increasing, if we keep a list of (val, timestamp) against a key, it will be sorted by timesteamp. So, using binary-search we can find the latest value up to a timestamp.

Say the maximum number of times set() was called against a key is n and the longest key or value has length m.

OperationTimeSpace
__init__\mathcal{O}(1)\mathcal{O}(1)
set\mathcal{O}(m)\mathcal{O}(m)
get\mathcal{O}(m \cdot \lg{n})\mathcal{O}(1)
class TimeMap:

    def __init__(self):
        self.kvs = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.kvs:
            self.kvs[key] = []
        self.kvs[key].append( (timestamp, value) )

    def __find_latest_until(self, t, values):
        lo, hi = 0, len(values)-1
        while lo <= hi:
            mid = (lo + hi) // 2
            if values[mid][0] <= t:
                lo = mid+1
            else:
                hi = mid-1
        
        return lo-1


    def get(self, key: str, timestamp: int) -> str:
        if key not in self.kvs:
            return ""
        
        pos = self.__find_latest_until( timestamp, self.kvs[key] )
        if pos < 0:
            return ""
        
        return self.kvs[key][pos][1]


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

tanvirdotzaman

,

Leave a comment