lfu_letcode.py

from collections import deque

class LFUCache(object):

    def __init__(self, capacity):
        self.value = {}
        self.resque = {}
        self.capacity = capacity
        self.evictionQueue = deque()
        

    def get(self, key):
        ret = -1
        if key in self.value:
            ret = self.value[key]
            self.resque[key] = self.resque.get(key, 0)+1
            
        return ret
        

    def set(self, key, value):
        if self.capacity == 0:
            return
        # Eviction is needed
        if key not in self.value and self.capacity == len(self.value):
            eviction = False
            while not eviction:
                key2evict = self.evictionQueue.popleft()
                if self.resque.get(key2evict, 0) > 0:
                    self.resque[key2evict] -= 1
                    self.evictionQueue.append(key2evict)
                else:
                    eviction = True
                    if key2evict in self.value:
                        self.value.pop(key2evict)
                    if key2evict in self.resque:
                        self.resque.pop(key2evict)
        
    
        self.value[key] = value
        self.resque[key] = 0
        self.evictionQueue.append(key)