Three dictionaries, One doubly linked list - everything is O(1)


  • 0
    S
    class Node(object):
        def __init__(self, val):
            self.val, self.next, self.prev = val, None, None
    
    class DLL(object):
        def __init__(self):
            self.head, self.tail = None, None
            self.table  = dict()
            self.length = 0
        
        def append(self,val):   # O(1)
            node            = Node(val)
            self.table[val] = node
            if not self.head:
                self.head = self.tail = node
            else:
                self.tail.next = node
                node.prev      = self.tail
                self.tail      = self.tail.next
            self.length += 1
                
        def remove(self,val): # O(1)
            node = self.table.get(val,None)
            if not node:
                raise RuntimeError('remove on invalid value')
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev
            if self.head == node:
                self.head = node.next
            if self.tail == node:
                self.tail = node.prev
            del self.table[node.val]
            self.length -= 1
            return node.val
        
        def popleft(self): # O(1)
            if not self.head:
                raise RuntimeError('popleft on empty DLL attempted')
            val  = self.head.val
            return self.remove(val)
        
        def __len__(self): # O(1)
            return self.length
    
    class LFUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.capacity   = capacity
            self.kvstore    = dict()
            self.freqstore  = collections.defaultdict(DLL)
            self.used       = 0
            self.minfreq    = 1
    
        def get(self, key):  # O(1)
            """
            :type key: int
            :rtype: int
            """
            if key not in self.kvstore:  #O(1)
                return -1
            
            (value,freq) = self.kvstore[key]      
            self.freqstore[freq].remove(key)     
            if not self.freqstore[freq]:
                del self.freqstore[freq]
                if self.minfreq == freq:
                    self.minfreq = freq + 1
            self.kvstore[key] = (value,freq+1)
            self.freqstore[freq+1].append(key)
            return value
            
        def put(self, key, value): # O(1)
            """
            :type key: int
            :type value: int
            :rtype: void
            """
            if self.capacity:
                if key not in self.kvstore:
                    while self.used >= self.capacity:  # Runs only once
                        evicting_key = self.freqstore[self.minfreq].popleft()  # O(1)
                        if not self.freqstore[self.minfreq]:
                            del self.freqstore[self.minfreq]
    
                        del self.kvstore[evicting_key]
                        self.used -= 1
                    self.used += 1
                    self.kvstore[key] = (value,1)
                    self.freqstore[1].append(key)
                    self.minfreq = 1
                else:
                    oldvalue, freq = self.kvstore[key]
                    self.freqstore[freq].remove(key)
                    if not self.freqstore[freq]:
                        if freq == self.minfreq:
                            self.minfreq = freq + 1
                        del self.freqstore[freq]
                    self.kvstore[key] = (value,freq+1)
                    self.freqstore[freq+1].append(key)
    
    
    
    # Your LFUCache object will be instantiated and called as such:
    # obj = LFUCache(capacity)
    # param_1 = obj.get(key)
    # obj.put(key,value)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.