Simple Python solution fails long test case, did it on paper and I agree with my solution


  • 0
    M

    Disclaimer: I'm looking for a simple functional solution, not an optimal one.

    So my solution seems to be working for most test cases, but fails the following more complicated one. The problem is: I did it on paper (a little bit tedious), and I agree with my solution, not leetcode's. The key 6 should indeed be replaced by the 7, such that at execution 49, get 6 should return -1 and not 14.

    Input:

    ["LFUCache","set","set","set","set","set","get","set","get","get","set","get","set","set","set","get","set","get","get","get","get","set","set","get","get","get","set","set","get","set","get","set","get","get","get","set","set","set","get","set","get","get","set","set","get","set","set","set","set","get","set","set","get","set","set","get","set","set","set","set","set","get","set","set","get","set","get","get","get","set","get","get","set","set","set","set","get","set","set","set","set","get","get","get","set","set","set","get","set","set","set","get","set","set","set","get","get","get","set","set","set","set","get","set","set","set","set","set","set","set"]
    [[10],[10,13],[3,17],[6,11],[10,5],[9,10],[13],[2,19],[2],[3],[5,25],[8],[9,22],[5,5],[1,30],[11],[9,12],[7],[5],[8],[9],[4,30],[9,3],[9],[10],[10],[6,14],[3,1],[3],[10,11],[8],[2,14],[1],[5],[4],[11,4],[12,24],[5,18],[13],[7,23],[8],[12],[3,27],[2,12],[5],[2,9],[13,4],[8,18],[1,7],[6],[9,29],[8,21],[5],[6,30],[1,12],[10],[4,15],[7,22],[11,26],[8,17],[9,29],[5],[3,4],[11,30],[12],[4,29],[3],[9],[6],[3,4],[1],[10],[3,29],[10,28],[1,20],[11,13],[3],[3,12],[3,8],[10,9],[3,26],[8],[7],[5],[13,17],[2,27],[11,15],[12],[9,19],[2,15],[3,16],[1],[12,17],[9,1],[6,19],[4],[5],[5],[8,1],[11,7],[5,2],[9,28],[1],[2,2],[7,4],[4,22],[7,24],[9,26],[13,28],[11,26]]
    

    Output:

    [null,null,null,null,null,null,-1,null,19,17,null,-1,null,null,null,-1,null,-1,5,-1,12,null,null,3,5,5,null,null,1,null,-1,null,30,5,30,null,null,null,-1,null,-1,24,null,null,18,null,null,null,null,-1,null,null,18,null,null,11,null,null,null,null,null,18,null,null,24,null,4,29,-1,null,12,11,null,null,null,null,29,null,null,null,null,17,-1,18,null,null,null,24,null,null,null,20,null,null,null,29,18,18,null,null,null,null,20,null,null,null,null,null,null,null]
    

    Expected:

    [null,null,null,null,null,null,-1,null,19,17,null,-1,null,null,null,-1,null,-1,5,-1,12,null,null,3,5,5,null,null,1,null,-1,null,30,5,30,null,null,null,-1,null,-1,24,null,null,18,null,null,null,null,14,null,null,18,null,null,11,null,null,null,null,null,18,null,null,-1,null,4,29,30,null,12,11,null,null,null,null,29,null,null,null,null,17,-1,18,null,null,null,-1,null,null,null,20,null,null,null,29,18,18,null,null,null,null,20,null,null,null,null,null,null,null]
    

    My code:

    class LFUCache(object):
    
        def __init__(self, capacity):
            """
            
            :type capacity: int
            """
            
            self.capacity = capacity
            self.num = 0
            self.command_id = 0
            
            self.vals = {}
            self.usage = {}
            self.last_usage = {}
    
        def get(self, key):
            """
            :type key: int
            :rtype: int
            """
            
            self.command_id += 1
            
            if key in self.vals:
                self.usage[key] += 1
                self.last_usage[key] = self.command_id
                return self.vals[key]
            else:
                return -1
            
    
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: void
            """
            
            self.command_id += 1
            
            if self.capacity == 0:
                return
            
            min_val = None
            exists = key in self.vals
            
            if not exists and self.num == self.capacity:
                # Find lowest value.
                for k in self.vals:
                    if min_val is None or self.usage[k] < self.usage[min_val] \
                            or (self.usage[k] == self.usage[min_val] and self.last_usage[k] < self.last_usage[min_val]):
                        min_val = k
                
                # Remove it.
                del self.vals[min_val]
                del self.usage[min_val]
                del self.last_usage[min_val]
                self.num -= 1
            
            self.vals[key] = value
            self.last_usage[key] = self.command_id
    
            if not exists:
                self.usage[key] = 0
                self.num += 1
    

  • 1
    M

    I had a similar problem and it was due to an incomplete explanation of the expected behavior. The solution updates the access count when you set a key that already exists in the cache.


  • 0
    M

    Wow, okay. That was not properly explained. Thanks for the reply!


Log in to reply
 

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