Sponsored
Sponsored
In this approach, we use a combination of a HashMap (or Dictionary) and a double linked list to ensure O(1) operations for both get and put. The HashMap stores keys and values as well as a reference to the corresponding node in the double linked list, effectively allowing for quick updates and removals. The double linked list maintains the order of keys based on use frequency and recency to guarantee the correct eviction policy.
Time Complexity: O(1) for get and put operations due to the use of HashMap and Doubly Linked List.
Space Complexity: O(capacity) due to storage of nodes and frequency mappings.
1class Node:
2 def __init__(self, key, value):
3 self.key = key
4 self.value = value
5 self.freq = 1
6 self.prev = None
7 self.next = None
8
9class DoubleLinkedList:
10 def __init__(self):
11 self.head = Node(None, None)
12 self.tail = Node(None, None)
13 self.head.next = self.tail
14 self.tail.prev = self.head
15
16 def add(self, node):
17 p = self.head.next
18 self.head.next = node
19 node.prev = self.head
20 node.next = p
21 p.prev = node
22
23 def remove(self, node):
24 p, n = node.prev, node.next
25 p.next = n
26 n.prev = p
27
28 def pop_tail(self):
29 if self.tail.prev is self.head:
30 return None
31 tail = self.tail.prev
32 self.remove(tail)
33 return tail
34
35class LFUCache:
36 def __init__(self, capacity: int):
37 self.capacity = capacity
38 self.size = 0
39 self.node_map = {}
40 self.freq_map = {}
41 self.min_freq = 0
42
43 def update_freq(self, node):
44 freq = node.freq
45 self.freq_map[freq].remove(node)
46 if not self.freq_map[freq].head.next != self.freq_map[freq].tail:
47 del self.freq_map[freq]
48 if freq == self.min_freq:
49 self.min_freq += 1
50
51 node.freq += 1
52 freq = node.freq
53 if freq not in self.freq_map:
54 self.freq_map[freq] = DoubleLinkedList()
55 self.freq_map[freq].add(node)
56
57 def get(self, key: int) -> int:
58 if key not in self.node_map:
59 return -1
60 node = self.node_map[key]
61 self.update_freq(node)
62 return node.value
63
64 def put(self, key: int, value: int) -> None:
65 if self.capacity == 0:
66 return
67 if key in self.node_map:
68 node = self.node_map[key]
69 node.value = value
70 self.update_freq(node)
71 else:
72 if self.size == self.capacity:
73 list_to_remove = self.freq_map[self.min_freq]
74 tail = list_to_remove.pop_tail()
75 del self.node_map[tail.key]
76 self.size -= 1
77 new_node = Node(key, value)
78 self.node_map[key] = new_node
79 if 1 not in self.freq_map:
80 self.freq_map[1] = DoubleLinkedList()
81 self.freq_map[1].add(new_node)
82 self.min_freq = 1
83 self.size += 1The Python solution involves two custom classes: Node and DoubleLinkedList. The Node class holds key-value pairs, frequency counts, and pointers to previous and next nodes. The DoubleLinkedList class is used to maintain the order based on frequency and recency of use.
The LFUCache class maintains two dictionaries: node_map which maps keys to nodes, and freq_map which maps frequencies to linked lists. The cache operations (get/put) are implemented to update the frequency of nodes appropriately and handle cache capacity by removing the least frequently and recently used nodes when needed.
The OrderedDict based approach uses Python's built-in OrderedDict to efficiently track keys while maintaining the insertion order. By managing the dictionary's order, we can track the frequency of access and modify it when performing get or put operations. This may not offer the theoretical O(1) complexity for all operations but is a practical solution with simplicity in Python.
Time Complexity: Average O(1) for both get and put, due to the effectiveness of OrderedDict for these operations.
Space Complexity: O(capacity) for storing nodes and their frequency mappings.
1from collections import defaultdict, OrderedDict
2
3class LFUCache:
4
The OrderedDict solution keeps track of keys and their frequencies in separate dictionaries. key_freq_map maps the key to its frequency, while freq_map has OrderedDicts keyed by frequency with keys as their values. This way, we can update both frequency and recency of accesses.
With the built-in nature of Python's OrderedDict, the implementation remains concise and takes advantage of existing functionality to manage ordering effectively, even if all operations might not run in strict O(1) time.