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 constructor(key, value) {
3 this.key = key;
4 this.value = value;
5 this.freq = 1;
6 this.prev = null;
7 this.next = null;
8 }
9}
10
11class DoubleLinkedList {
12 constructor() {
13 this.head = new Node(null, null);
14 this.tail = new Node(null, null);
15 this.head.next = this.tail;
16 this.tail.prev = this.head;
17 }
18
19 add(node) {
20 const nextNode = this.head.next;
21 this.head.next = node;
22 node.prev = this.head;
23 node.next = nextNode;
24 nextNode.prev = node;
25 }
26
27 remove(node) {
28 const prevNode = node.prev;
29 const nextNode = node.next;
30 prevNode.next = nextNode;
31 nextNode.prev = prevNode;
32 }
33
34 popTail() {
35 if (this.tail.prev === this.head) return null;
36 const nodeToRemove = this.tail.prev;
37 this.remove(nodeToRemove);
38 return nodeToRemove;
39 }
40}
41
42class LFUCache {
43 constructor(capacity) {
44 this.capacity = capacity;
45 this.size = 0;
46 this.nodeMap = new Map();
47 this.freqMap = new Map();
48 this.minFreq = 0;
49 }
50
51 updateFreq(node) {
52 const freq = node.freq;
53 const list = this.freqMap.get(freq);
54 list.remove(node);
55 if (!list.head.next !== list.tail) {
56 this.freqMap.delete(freq);
57 if (freq === this.minFreq) {
58 this.minFreq++;
59 }
60 }
61
62 node.freq++;
63 const newFreq = node.freq;
64 if (!this.freqMap.has(newFreq)) {
65 this.freqMap.set(newFreq, new DoubleLinkedList());
66 }
67 this.freqMap.get(newFreq).add(node);
68 }
69
70 get(key) {
71 if (!this.nodeMap.has(key)) return -1;
72 const node = this.nodeMap.get(key);
73 this.updateFreq(node);
74 return node.value;
75 }
76
77 put(key, value) {
78 if (this.capacity === 0) return;
79 if (this.nodeMap.has(key)) {
80 const node = this.nodeMap.get(key);
81 node.value = value;
82 this.updateFreq(node);
83 } else {
84 if (this.size === this.capacity) {
85 const list = this.freqMap.get(this.minFreq);
86 const toRemove = list.popTail();
87 this.nodeMap.delete(toRemove.key);
88 this.size--;
89 }
90
91 const newNode = new Node(key, value);
92 this.nodeMap.set(key, newNode);
93 if (!this.freqMap.has(1)) {
94 this.freqMap.set(1, new DoubleLinkedList());
95 }
96 this.freqMap.get(1).add(newNode);
97 this.minFreq = 1;
98 this.size++;
99 }
100 }
101}The JavaScript solution closely mirrors the Python one, making use of ES6 class syntax. Two classes, Node and DoubleLinkedList, are utilized to manage nodes and frequency lists. The methods exhibit similar logic to their Python counterparts: Nodes are added to and removed from the double linked list, and frequencies are updated in constant time.
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.