460. LFU Cache

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow-Up:

Could you do both operations in $O(1)$ time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Solution: Doubly Linked List & OrderedDict

import collections


class LinkedNode:
    def __init__(self, frequency=1, pre=None, nxt=None):
        self.keys = collections.OrderedDict()
        self.frequency = frequency
        self.pre = pre
        self.nxt = nxt
        if pre:
            pre.nxt = self
        if nxt:
            nxt.pre = self

    def __str__(self):
        keys = ', '.join(map(str, self.keys))
        return '{:s} {}({})'.format(self.pre, self.frequency, keys)

    def is_tail(self):
        return self.frequency == 1

    def remove(self):
        if self.pre:
            self.pre.nxt = self.nxt
        if self.nxt:
            self.nxt.pre = self.pre
        self.pre = None
        self.nxt = None

    def append(self, key):
        self.keys[key] = 0

    def pop(self, key=None):
        if key:
            del self.keys[key]
        else:
            key, _ = self.keys.popitem(last=False)
        if not self.keys and not self.is_tail():
            self.remove()
        return key

    def increment(self, key):
        freq = self.frequency + 1
        node = (self.pre if self.pre and self.pre.frequency == freq
                else LinkedNode(freq, self.pre, self))
        node.append(key)
        self.pop(key)
        return node

class LFUCache(object):
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.tail = LinkedNode()
        self.nodes = dict()
        self.cache = dict()

    def get(self, key):
        """
        :rtype: int
        """
        if key in self.cache:
            self.update(key)
            return self.cache[key]
        return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: nothing
        """
        if key in self.cache:
            self.update(key)
            self.cache[key] = value
        elif self.capacity > 0:
            if self.is_full():
                self.pop()
            self.tail.append(key)
            self.nodes[key] = self.tail
            self.cache[key] = value

    def is_full(self):
        return len(self.cache) == self.capacity

    def pop(self):
        tail = self.tail if self.tail.keys else self.tail.pre
        key = tail.pop()
        del self.nodes[key]
        del self.cache[key]

    def update(self, key):
        node = self.nodes[key]
        node = node.increment(key)
        self.nodes[key] = node

Lessons:

• Two dictionaries: {key: value} and {key: node}.
• Each node has an unique frequency and an ordered set of keys.
• Since Python doesn't have a OrderedSet class, use OrderedDict instead.

Related:

• 146. LRU Cache