FilesExpand file tree

master

/

time-based-key-value-store.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

43 lines (34 loc) · 941 Bytes

master

/

time-based-key-value-store.py

Copy path

Top

File metadata and controls

• Code
• Blame

43 lines (34 loc) · 941 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

# Time: set: O(1)

# get: O(logn)

# Space: O(n)

import collections

import bisect

class TimeMap(object):

def __init__(self):

"""

Initialize your data structure here.

"""

self.lookup = collections.defaultdict(list)

def set(self, key, value, timestamp):

"""

:type key: str

:type value: str

:type timestamp: int

:rtype: None

"""

self.lookup[key].append((timestamp, value))

def get(self, key, timestamp):

"""

:type key: str

:type timestamp: int

:rtype: str

"""

A = self.lookup.get(key, None)

if A is None:

return ""

i = bisect.bisect_right(A, (timestamp+1, 0))

return A[i-1][1] if i else ""

# Your TimeMap object will be instantiated and called as such:

# obj = TimeMap()

# obj.set(key,value,timestamp)

# param_2 = obj.get(key,timestamp)