981. Time Based Key-Value Store

 1# "All the timestamps timestamp of set are strictly increasing."
 2# is vital to enable binary search
 3
 4
 5class TimeMap:
 6
 7    def __init__(self):
 8        self.storage = defaultdict(list)
 9
10    def set(self, key: str, value: str, timestamp: int) -> None:
11        self.storage[key].append((timestamp, value))
12
13    def get(self, key: str, timestamp: int) -> str:
14        n = len(self.storage[key])
15        if not n:
16            return ""
17
18        l = 0
19        r = n - 1
20
21        # [0,0,1,1,1,7,8] we want latest <= 4
22        #  l     m     r; m < target therefore l = m
23        #        l   m r; m > target therefore r = m - 1
24        #          l
25        #  l/r is correct index
26
27        # [0,0,1,1,4,4,8] we want latest <= 4
28        #  l     m     r; m < target therefore l = m
29        #        l   m r; m = target therefore l = m
30        #            l r; m > target therefore r = m - 1
31        #            l
32        #  l/r is correct index
33
34        # [5,5,5] we want latest <= 4
35        #  l m r; m > target therefore r = m - 1
36        #  l    ; m > target therefore r = m - 1
37        #  l == 0, r < l, we should catch this
38        while l < r:
39
40            m = (l + r + 1) // 2
41
42            if self.storage[key][m][0] <= timestamp:
43                l = m
44            else:
45                r = m - 1
46
47        # print(l, r, self.storage[key], timestamp)
48        return "" if self.storage[key][l][0] > timestamp else self.storage[key][l][1]
49
50
51# Your TimeMap object will be instantiated and called as such:
52# obj = TimeMap()
53# obj.set(key,value,timestamp)
54# param_2 = obj.get(key,timestamp)

 1class TimeMap:
 2
 3    def __init__(self):
 4        self.tmap = defaultdict(list)
 5
 6    def set(self, key: str, value: str, timestamp: int) -> None:
 7        self.tmap[key].append((timestamp, value))
 8
 9    def get(self, key: str, timestamp: int) -> str:
10        if not self.tmap[key] or self.tmap[key][0][0] > timestamp:
11            return ""
12
13        n = len(self.tmap[key])
14        l = 0
15        r = n - 1
16
17        # [1,1,4,4,7,7] find latest <= 4
18        #  l     m   r; m <= target, l = m
19        #      l   m r; m > target, r = m - 1
20        #        l
21        # l is correct
22
23        # [1,4] find latest <= 1
24        #  l r; m > target, r = m - 1
25
26        while l < r:
27            m = (l + r + 1) // 2
28
29            if self.tmap[key][m][0] <= timestamp:
30                l = m
31            else:
32                r = m - 1
33
34        return self.tmap[key][l][1]
35
36
37# Your TimeMap object will be instantiated and called as such:
38# obj = TimeMap()
39# obj.set(key,value,timestamp)
40# param_2 = obj.get(key,timestamp)

 1class TimeMap:
 2
 3    def __init__(self):
 4        self.tmap = defaultdict(list)
 5
 6    def set(self, key: str, value: str, timestamp: int) -> None:
 7        self.tmap[key].append((timestamp, value))
 8
 9    def get(self, key: str, timestamp: int) -> str:
10        if not self.tmap[key] or self.tmap[key][0][0] > timestamp:
11            return ""
12
13        n = len(self.tmap[key])
14        l = 0
15        r = n - 1
16
17        # [1,1,4,4,7,7] find latest <= 4
18        #  l   m     r; m <=, l = m + 1
19        #        l m r; m > , r = m - 1
20        #        3    ; , <=, l = m + 1
21        # r is correct
22
23        # [1,4] find latest <= 1
24        #  l r; m <=, l = m + 1
25        #    3; m > , r = m - 1
26        # r is correct
27
28        while l <= r:
29            m = (l + r) // 2
30
31            if self.tmap[key][m][0] <= timestamp:
32                l = m + 1
33            else:
34                r = m - 1
35
36        return self.tmap[key][r][1]
37
38
39# Your TimeMap object will be instantiated and called as such:
40# obj = TimeMap()
41# obj.set(key,value,timestamp)
42# param_2 = obj.get(key,timestamp)