Python Solution using Dictionaries and Deque. Problem with RunCodeResults


  • 0
    O

    This here is my solution to the LFU Cache problem using Python (3.5.2). The solution hinges on the use of two dictionaries and a double ended queue. I wrote some tests to make sure that my solution provided the expected outputs, and they all passed on my machine. The problem I'm having is that the answer I get from the Run Code Results is different from what I get on my machine.

    0_1482563963333_RunCodeResult.png

    I would love some help with resolving this issue. So far, I've manually traced the output given the logic in my solution, but I get the correct output. So, I'm not really sure what might be causing this discrepancy.

    Solution in Python

    from collections import deque
    
    class LFUCache:
        def __init__(self, capacity):
            self.capacity = capacity
            self.cache = {}
            self.lru = deque()
            self.lfu = {}
    
        def get(self, key):
            if not key in self.cache:
                return -1
            self._update_lru(key)
            self._update_lfu(key)
            return self.cache[key]
    
        def set(self, key, value):
            if not key in self.cache:
                if self._full():
                    lfu_count = min(self.lfu.values())
                    lfu_items = [key for key in self.lfu if self.lfu[key] == lfu_count]
                    if len(lfu_items) > 1:
                        lru_item = self.lru.pop()
                        self.cache.pop(lru_item)
                        self.lfu.pop(lru_item)
                    else:
                        self.cache.pop(lfu_items[0])
                        self.lru.remove(lfu_items[0])
                        self.lfu.pop(lfu_items[0])
            self.cache[key] = value
            self._update_lru(key)
            self._update_lfu(key)
    
        def _update_lru(self, key):
            if key in self.lru:
                self.lru.remove(key)
            self.lru.appendleft(key)
    
        def _update_lfu(self, key):
            if not key in self.lfu:
                self.lfu[key] = 0
            self.lfu[key] += 1
    
        def _full(self):
            return len(self.cache) == self.capacity
    
    def main():
        lfu_cache = LFUCache(3)
        assert lfu_cache.get(1) == -1
        lfu_cache.set(1, 20)
        lfu_cache.set(2, 30)
        lfu_cache.set(3, 40)
        assert set(lfu_cache.cache.keys()) == {1,2,3}
        assert lfu_cache._full() == True
        assert lfu_cache.lru == deque([3,2,1])
        lfu_cache.get(1)
        assert lfu_cache.lru[0] == 1
        assert lfu_cache.lfu[1] == 2
        lfu_cache.get(3)
        assert lfu_cache.lru[0] == 3
        assert lfu_cache.lfu[3] == 2
        lfu_cache.set(4, 50)
        assert lfu_cache.lru[0] == 4
        assert lfu_cache.lfu[4] == 1
        assert lfu_cache._full() == True
    
        # sample test
        lfu2 = LFUCache(2)
        lfu2.set(1,1)
        lfu2.set(2,2)
        assert lfu2.get(1) == 1
        lfu2.set(3,3)
        assert lfu2.get(2) == -1
        assert lfu2.get(3) == 3
        lfu2.set(4,4)
        assert lfu2.get(1) == -1
        assert lfu2.get(3) == 3
        assert lfu2.get(4) == 4
    
    
    if __name__ == '__main__':
        main()
    

Log in to reply
 

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