LFU Cache LeetCode solution in Python

1
class Node:
2

3
    def __init__(self, key, val, cnt=1, nxxt=None, prev=None):
4
        self.key = key
5
        self.val = val
6
        self.cnt = cnt
7
        self.nxxt = nxxt
8
        self.prev = prev
9

10

11
class NodeList(Node):
12

13
    def __init__(self):
14
        self.head = Node(0, 0)
15
        self.tail = Node(0, 0)
16
        self.head.nxxt = self.tail
17
        self.tail.prev = self.head
18
        self.size = 0
19

20
    def addFront(self, node):
21
        temp = self.head.nxxt
22
        self.head.nxxt = node
23
        node.prev = self.head
24
        node.nxxt = temp
25
        temp.prev = node
26

27
        self.size += 1
28

29
    def removeNode(self, node):
30
        delprev = node.prev
31
        delnxxt = node.nxxt
32
        delprev.nxxt = delnxxt
33
        delnxxt.prev = delprev
34

35
        self.size -= 1
36

37

38
class LFUCache(NodeList):
39

40
    def __init__(self, capacity: int):
41
        self.keyNode = {}
42
        self.freqNodeList = {}
43
        self.maxSizeCache = capacity
44
        self.currSize = 0
45
        self.minFreq = 0
46

47
    def updateFreqNodeList(self, node):
48
        del self.keyNode[node.key]
49
        nodelist = self.freqNodeList[node.cnt]
50
        nodelist.removeNode(node)
51

52
        if node.cnt == self.minFreq and self.freqNodeList[node.cnt].size == 0:
53
            self.minFreq += 1
54

55
        if (node.cnt + 1) in self.freqNodeList:
56
            nextHigherFreqNodeList = self.freqNodeList[node.cnt + 1]
57
        else:
58
            nextHigherFreqNodeList = NodeList()
59

60
        node.cnt += 1
61
        nextHigherFreqNodeList.addFront(node)
62

63
        self.freqNodeList[node.cnt] = nextHigherFreqNodeList
64
        self.keyNode[node.key] = node
65

66
    def get(self, key: int) -> int:
67
        if key in self.keyNode:
68
            node = self.keyNode[key]
69
            ans = node.val
70
            self.updateFreqNodeList(node)
71

72
            return ans
73

74
        else:
75
            return -1
76

77
    def put(self, key: int, value: int) -> None:
78
        if self.maxSizeCache == 0:
79
            return
80

81
        if key in self.keyNode:
82
            node = self.keyNode[key]
83
            node.val = value
84
            self.updateFreqNodeList(node)
85
            return
86

87
        else:
88
            if self.currSize == self.maxSizeCache:
89
                nodelist = self.freqNodeList[self.minFreq]
90
                del self.keyNode[nodelist.tail.prev.key]
91
                nodelist.removeNode(nodelist.tail.prev)
92
                self.currSize -= 1
93

94
            self.currSize += 1
95
            self.minFreq = 1
96

97
            if self.minFreq in self.freqNodeList:
98
                nodelist = self.freqNodeList[self.minFreq]
99
            else:
100
                nodelist = NodeList()
101

102
            node = Node(key, value)
103
            nodelist.addFront(node)
104

105
            self.keyNode[key] = node
106
            self.freqNodeList[self.minFreq] = nodelist
107

108

109
# Your LFUCache object will be instantiated and called as such:
110
# obj = LFUCache(capacity)
111
# param_1 = obj.get(key)
112
# obj.put(key,value)