Help please. O(n) Python Soln - Can't figure out what's wrong.


  • 0
    D

    I figured I'll move to the O(1) soln after solving it in O(n)

    class LFUCache(object):
    
        def __init__(self, capacity):
            """
            
            :type capacity: int
            """
            
            self.c = capacity
            self.d = {}
            self.f = {}
            self.l = []
            
    
        def get(self, key):
            """
            :type key: int
            :rtype: int
            """
            d = self.d
            f = self.f
            c = self.c
            l = self.l
            
            if c==0:
                return -1
            
            if key in d:
                print('Key {} Found. Value = {}'.format(key,d[key]))
                f[key]+=1
                
                if key in l:
                    l.remove(key)
                
                l.append(key)
                
                
                return d[key]
            
            else:
                print('Key {} not Found'.format(key))
                return -1
                
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: void
            """
            d = self.d
            f = self.f
            c = self.c
            l = self.l
            
            if c==0:
                return
            
            if key not in d:
                # If dictionary is at capacity, we need to pop something.
                if len(d)==c:
                    print('Capacity Reached')
                    
                    print('d = {}'.format(d))
                    print('f = {}'.format(f))
                    print('l = {}'.format(l))
                    
                    # Get least frequently used item
                    lfu = self.getLFU()
                    
                    # Delete the retrieved element
                    del d[lfu]
                    del f[lfu]
                    l.remove(lfu)
            
            # Dictionary now has space
            print('Setting {}={}'.format(key,value))
            d[key] = value
            f[key] = 0
            if key in l:
                l.remove(key)
            l.append(key)
            
        
        def getLFU(self):
            d = self.d
            f = self.f
            
            min = float('inf')
            key = None
            
            lru = []
            # Find the min
            for k,v in f.items():
                if v < min:
                    min = v
                    key = k
            
            # Check for same min
            for k,v in f.items():
                if v==min:
                    lru.append(k)
            
            # If lru has more than one element, we have a couple of elements with the same frequency.
            # Now we need to return the least recently used element in these.
            if len(lru)>1:
                return self.getLRU(lru)
            else:
                print('LFU Key deleted = {}'.format(key))
                return key
        
        # Compares their indices and returns the one with least
        # Least index means least recent
        def getLRU(self,lru):
            l = self.l
            
            min = float('inf')
            key = None
            
            for k in lru:
                index = l.index(k)
                
                if index<min:
                    key = k
                    min = index
            
            print('LRU Key deleted = {}'.format(key))
            return key
    
    # Your LFUCache object will be instantiated and called as such:
    # obj = LFUCache(capacity)
    # param_1 = obj.get(key)
    # obj.set(key,value)
    

Log in to reply
 

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