|
69
|
1 #
|
|
|
2 # Question: Least Recently Used (LRU) Cache Implementation
|
|
|
3 #
|
|
|
4 # Design and implement a Least Recently Used (LRU) cache. The cache should be initialized with a positive integer capacity.
|
|
|
5 #
|
|
|
6 # Your implementation must support the following operations with $O(1)$ time complexity for both:
|
|
|
7 #
|
|
|
8 # get(key): Retrieve the value of the item identified by key. If the key exists, return its value. If it doesn't, return $-1$. This operation also marks the key as the most recently used.
|
|
|
9 #
|
|
|
10 # put(key, value): Insert or update an item. If the key already exists, update its value and mark it as the most recently used. If the key does not exist, insert the new item. When the cache reaches its capacity, it must evict the least recently used item before inserting the new one.
|
|
|
11 #
|
|
|
12 # You must use a Hash Map and a Doubly Linked List for the implementation.
|
|
|
13
|
|
|
14 # Cache , limit 3
|
|
|
15
|
|
|
16 from typing import Dict
|
|
|
17
|
|
|
18 # tail.prev.next = node, node.left = tails.prev, tails.prev = Node, node.next = tail
|
|
|
19
|
|
|
20 # Head <-> Tail
|
|
|
21 # Head -> Node <-> Tail ,
|
|
|
22 # Head <-> Node <-> Node1 <-> Tail,
|
|
|
23 # node.prev.next = node.next, node.next.prev = node.prev
|
|
|
24
|
|
|
25 class Node:
|
|
|
26
|
|
|
27 def __init__(self, key: str, value: str):
|
|
|
28 self.next: Node | None = None
|
|
|
29 self.prev: Node | None = None
|
|
|
30 self.key = key
|
|
|
31 self.value = value
|
|
|
32
|
|
|
33 class LRU:
|
|
|
34
|
|
|
35 def __init__(self, capacity: int = 2):
|
|
|
36 self.db: Dict[str, Node] = {}
|
|
|
37 self.capacity = capacity
|
|
|
38
|
|
|
39 self.head = Node("-1", "-1")
|
|
|
40 self.tail = Node("-1", "-1")
|
|
|
41 self.head.next, self.tail.prev = self.tail, self.head
|
|
|
42
|
|
|
43 def get(self, key: str):
|
|
|
44 node = self.db[key]
|
|
|
45 self._remove(node)
|
|
|
46 self._add_to_tail(node)
|
|
|
47 return node.value
|
|
|
48
|
|
|
49 def put(self, key: str, value: str):
|
|
|
50 if len(self.db) < self.capacity or key in self.db:
|
|
|
51 new_node = Node(key, value)
|
|
|
52 self._add_to_tail(new_node)
|
|
|
53 self.db[key] = new_node
|
|
|
54 else:
|
|
|
55 least_recently_used_node = self.head.next
|
|
|
56 self._remove(least_recently_used_node)
|
|
|
57 del self.db[least_recently_used_node.key]
|
|
|
58
|
|
|
59 new_node = Node(key, value)
|
|
|
60 self._add_to_tail(new_node)
|
|
|
61 self.db[key] = new_node
|
|
|
62
|
|
|
63 def _remove(self, node: Node):
|
|
|
64 node.prev.next, node.next.prev = node.next, node.prev
|
|
|
65
|
|
|
66 def _add_to_tail(self, node):
|
|
|
67 self.tail.prev.next, node.prev, self.tail.prev, node.next = node, self.tail.prev, node, self.tail
|
|
|
68
|
|
|
69 lru = LRU()
|
|
|
70 lru.put("june", "park")
|
|
|
71 lru.put("victor", "sun")
|
|
|
72 lru.get("june")
|
|
|
73 lru.put("bowen", "sun")
|
|
|
74
|
|
|
75
|
