Mercurial

comparison grok_interview/LRU.py @ 60:d64a8c189a77

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merged
author June Park <me@mrjunejune.com>
date Sat, 20 Dec 2025 13:56:01 -0500
parents 68fa88ac73fe
children
comparison
equal deleted inserted replaced
50:983769fba767 60:d64a8c189a77
1 from typing import Optional
2
3
4 class Node:
5 def __init__(self, key, value):
6 self.key = key
7 self.value = value
8 self.next: Optional[Node] = None
9 self.prev: Optional[Node] = None
10
11 class LRUCache:
12
13 def __init__(self, capacity: int):
14 self.capacity = capacity
15 self.map = {}
16 self.head = Node(-1, -1)
17 self.tail = Node(-1, -1)
18 self.head.next, self.tail.prev = self.tail, self.head
19
20 def get(self, key: int) -> int:
21 if not key in self.map:
22 return -1
23 node = self.map[key]
24 self._deleteAndAdd(node)
25 return node.value
26
27 def put(self, key: int, value: int) -> None:
28 newNode = Node(key, value)
29 if key in self.map:
30 self._delete(self.map[key])
31 else:
32 if len(self.map.keys())+1 > self.capacity:
33 del self.map[self.head.next.key]
34 self._delete(self.head.next)
35 self._add(newNode)
36 self.map[key] = newNode
37
38 def _deleteAndAdd(self, node):
39 self._delete(node)
40 self._add(node)
41
42 def _delete(self, node):
43 node.prev.next, node.next.prev = node.next, node.prev
44
45 def _add(self, node):
46 node.prev, node.next, self.tail.prev.next, self.tail.prev = self.tail.prev, self.tail, node, node