lru_cache

View Source

 1# @leet start
 2from collections import OrderedDict
 3
 4
 5class LRUCache:
 6    """
 7    LRU Cache involves evicting the last item that was used (get/put) if
 8    the capacity of the dict becomes too big.
 9    We'll use an ordereddict, although a regular dict works as well.
10    When we get from the dict, we'll move it to the end of the dictionary.
11    When we put, we'll move our current key to the end and then if the capacity
12    is greater, then we'll pop the item from the start.
13    """
14
15    def __init__(self, capacity: int):
16        self.dict = OrderedDict()
17        self.capacity = capacity
18
19    def get(self, key: int) -> int:
20        if key not in self.dict:
21            return -1
22        self.dict.move_to_end(key)
23        return self.dict[key]
24
25    def put(self, key: int, value: int) -> None:
26        if key in self.dict:
27            self.dict.move_to_end(key)
28
29        self.dict[key] = value
30        if len(self.dict) > self.capacity:
31            self.dict.popitem(False)
32
33
34def test():
35    assert 2 + 2 == 4

class LRUCache: View Source

 6class LRUCache:
 7    """
 8    LRU Cache involves evicting the last item that was used (get/put) if
 9    the capacity of the dict becomes too big.
10    We'll use an ordereddict, although a regular dict works as well.
11    When we get from the dict, we'll move it to the end of the dictionary.
12    When we put, we'll move our current key to the end and then if the capacity
13    is greater, then we'll pop the item from the start.
14    """
15
16    def __init__(self, capacity: int):
17        self.dict = OrderedDict()
18        self.capacity = capacity
19
20    def get(self, key: int) -> int:
21        if key not in self.dict:
22            return -1
23        self.dict.move_to_end(key)
24        return self.dict[key]
25
26    def put(self, key: int, value: int) -> None:
27        if key in self.dict:
28            self.dict.move_to_end(key)
29
30        self.dict[key] = value
31        if len(self.dict) > self.capacity:
32            self.dict.popitem(False)

LRU Cache involves evicting the last item that was used (get/put) if the capacity of the dict becomes too big. We'll use an ordereddict, although a regular dict works as well. When we get from the dict, we'll move it to the end of the dictionary. When we put, we'll move our current key to the end and then if the capacity is greater, then we'll pop the item from the start.

LRUCache(capacity: int) View Source

16    def __init__(self, capacity: int):
17        self.dict = OrderedDict()
18        self.capacity = capacity

dict

capacity

def get(self, key: int) -> int: View Source

20    def get(self, key: int) -> int:
21        if key not in self.dict:
22            return -1
23        self.dict.move_to_end(key)
24        return self.dict[key]

def put(self, key: int, value: int) -> None: View Source

26    def put(self, key: int, value: int) -> None:
27        if key in self.dict:
28            self.dict.move_to_end(key)
29
30        self.dict[key] = value
31        if len(self.dict) > self.capacity:
32            self.dict.popitem(False)

def test(): View Source

35def test():
36    assert 2 + 2 == 4