Search for a command to run...
Evict the least frequently used, breaking ties by recency
Initialization
Empty cache with capacity 2. Eviction takes the tail of the lowest non-empty frequency bucket, so minFreq must be tracked as buckets empty out.
Frequency Buckets
1class Node {2 constructor(key, value) {3 this.key = key; this.value = value;4 this.cnt = 1; this.next = null; this.prev = null;5 }6}//capacity: 2size: 0minFreq: 07 8class List {9 constructor() {10 this.size = 0;11 this.head = new Node(0, 0);12 this.tail = new Node(0, 0);13 this.head.next = this.tail;14 this.tail.prev = this.head;15 }16 addFront(node) {17 const temp = this.head.next;18 node.next = temp; node.prev = this.head;19 this.head.next = node; temp.prev = node;20 this.size++;21 }22 removeNode(delnode) {23 delnode.prev.next = delnode.next;24 delnode.next.prev = delnode.prev;25 this.size--;26 }27}28 29class LFUCache {30 constructor(capacity) {31 this.maxSizeCache = capacity;32 this.minFreq = 0;33 this.curSize = 0;34 this.keyNode = new Map();35 this.freqListMap = new Map();36 }37 38 updateFreqListMap(node) {39 this.keyNode.delete(node.key);40 this.freqListMap.get(node.cnt).removeNode(node);41 if (node.cnt === this.minFreq &&42 this.freqListMap.get(node.cnt).size === 0) {43 this.minFreq++;44 }45 let nextHigherFreqList = new List();46 if (this.freqListMap.has(node.cnt + 1)) {47 nextHigherFreqList = this.freqListMap.get(node.cnt + 1);48 }49 node.cnt += 1;50 nextHigherFreqList.addFront(node);51 this.freqListMap.set(node.cnt, nextHigherFreqList);52 this.keyNode.set(node.key, node);53 }54 55 get(key) {56 if (this.keyNode.has(key)) {57 const node = this.keyNode.get(key);58 const val = node.value;59 this.updateFreqListMap(node);60 return val;61 }62 return -1;63 }64 65 put(key, value) {66 if (this.maxSizeCache === 0) return;67 if (this.keyNode.has(key)) {68 const node = this.keyNode.get(key);69 node.value = value;70 this.updateFreqListMap(node);71 } else {72 if (this.curSize === this.maxSizeCache) {73 const list = this.freqListMap.get(this.minFreq);74 this.keyNode.delete(list.tail.prev.key);75 list.removeNode(list.tail.prev);76 this.curSize--;77 }78 this.curSize++;79 this.minFreq = 1;80 let listFreq = new List();81 if (this.freqListMap.has(this.minFreq)) {82 listFreq = this.freqListMap.get(this.minFreq);83 }84 const node = new Node(key, value);85 listFreq.addFront(node);86 this.keyNode.set(key, node);87 this.freqListMap.set(this.minFreq, listFreq);88 }89 }90}