Simple and Self-explained Python Solution (2 hash maps, no linked list)


  • 0

    Instead of using a linked list, I use a minfreq to keep track of the LFU frequency.

    d: Store key -> [freq, value] pair.
    freq: Store freq -> OrderedDict(key1, key2, ...) # Here I use an OrderedDict as an ordered set to store the keys in the same frequency so that it contains LRU functionality if we use .popitem(last=False) method.
    Function touch: update freq (frequency increased by 1) whenever we read or write a key.

    class LFUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.capacity = capacity
            self.usage = 0
            self.d = {}
            self.freq = {}
            self.minfreq = 0
    
        def get(self, key):
            """
            :type key: int
            :rtype: int
            """
            if key in self.d:
                # add freq
                self.touch(key)
                # return value
                return self.d[key][1]
            else: # not found
                return -1
    
        def put(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: void
            """
            if not self.capacity:
                return
            if key in self.d: # old key
                self.d[key][1] = value # update value
                self.touch(key)   # update freq in the system
            else: # new key
                if self.usage >= self.capacity:
                    # remove a key from the cache first before add the new key
                    deletedkey = self.freq[self.minfreq].popitem(last=False)[0] # get the LFU key
                    self.d.pop(deletedkey) # delete the key in self.d
                    if not self.freq[self.minfreq]:
                        self.freq.pop(self.minfreq)
                    self.usage -= 1
                self.d[key] = [1,value] # add to self.d
                if not 1 in self.freq:
                    self.freq[1] = collections.OrderedDict()
                self.freq[1][key] = 1   # add to self.freq
                self.usage += 1
                self.minfreq = 1
            
        def touch(self, key):
            # add freq by one for key
            # pop key from freq[old_freq]
            old_freq = self.d[key][0]
            self.freq[old_freq].pop(key)
            # delete freq[old_freq] if it's empty
            if not self.freq[old_freq]:
                self.freq.pop(old_freq)
                # if minfreq is affected, update its value
                if self.minfreq == old_freq:
                    self.minfreq += 1
            # add key to new_freq, if freq[new_freq] does not exist, create one
            new_freq = old_freq + 1
            if not new_freq in self.freq:
                self.freq[new_freq] = collections.OrderedDict()
            self.freq[new_freq][key] = 1
            # update the freq in self.d
            self.d[key][0] += 1
    
    # 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.