LeetCode 460. LFU Cache

December 11, 2020

We can keep a linked list of frequencies, $f$ , where each node contains a linked list of keys, $[k,\dots]$ with that frequency, sorted in least-recently-used order. For now, we're going to use more space ( $O(\text{frequency range})$ space instead of $O(\text{keys})$ ) and use a map for frequencies. We will also have an accompanying map, $values$ , with $\{k: value\}$ , a map, $references$ , with $\{k: \text{reference to spot in frequency list}\}$ . And we would also need to track the minimum current frequency.

With that, we have an LFU cache algorithm:

$LFUCache(capacity)$

store $capacity$ and $min\_frequency$ .

$\_remove()$

given a reference to the lowest frequency node in the frequency list.
remove the LRU key from that node and from $values$ .
if this empties the node, shift the given reference and delete this node.

$\_insert(k)$

if 1 is not in the frequency map, add an entry.
$f[1].add(k)$ . We can use an OrderedDict for the values of $f$ instead of implementing our own doubly linked list and reference map.

$\_increment(k)$

remove $k$ from the OrderedDict at $f[k]$ .
add $k$ to the OrderedDict at $f[k+1]$ , or create it if it doesn't exist.

$put(k,v)$

if the size of $values$ is equal to $capacity$ and $k$ is not in $values$ , then $\_remove()$
if $k$ is not in $values$ , $\_insert(k)$ , else $\_increment(k)$
$values[k] = v$

$get(k)$

if $k$ isn't in $values$ , return -1.
$\_increment(k)$

Asymptotic Runtime:

Every operation on this LFUCache is $O(1)$ .

from collections import defaultdict, OrderedDict
import unittest

class Test(unittest.TestCase):

    def test_example1(self):
        s = LFUCache(2)
        s.put(1, 1)
        s.put(2, 2)
        self.assertEqual(s.get(1), 1)
        s.put(3, 3)
        self.assertEqual(s.get(2), -1)
        self.assertEqual(s.get(3), 3)
        s.put(4, 4)
        self.assertEqual(s.get(1), -1)
        self.assertEqual(s.get(3), 3)
        self.assertEqual(s.get(4), 4)

    def test_example2(self):
        s = LFUCache(1)
        s.put(2, 1)
        self.assertEqual(s.get(2), 1)
        s.put(3, 2)
        self.assertEqual(s.get(2), -1)
        self.assertEqual(s.get(3), 2)

    def test_example3(self):
        s = LFUCache(3)
        s.put(2, 2)
        s.put(1, 1)
        self.assertEqual(s.get(2), 2)
        self.assertEqual(s.get(1), 1)
        self.assertEqual(s.get(2), 2)
        s.put(3, 3)
        s.put(4, 4)
        self.assertEqual(s.get(3), -1)
        self.assertEqual(s.get(2), 2)
        self.assertEqual(s.get(1), 1)
        self.assertEqual(s.get(4), 4)

class LFUCache:

    def __init__(self, capacity: int):
        self.c = capacity
        self.minf = 0
        self.f = defaultdict(OrderedDict)
        self.vs = {}
        self.refs = {}

    def get(self, k: int) -> int:
        if k in self.vs:
            self._increment(k)
            return self.vs[k]
        return -1

    def put(self, k: int, v: int) -> None:
        if self.c == 0:
            return
        if k not in self.vs:
            if len(self.vs) == self.c:
                # remove
                del self.vs[self.f[self.minf].popitem(last=False)[0]]
                self._update_minf()
            # insert
            self.f[0][k] = 1
            self.minf = 0
            self.refs[k] = 0
        else:
            self._increment(k)
        self.vs[k] = v

    def _update_minf(self) -> None:
        if len(self.f[self.minf]) == 0:
            del self.f[self.minf]
            self.minf += 1

    def _increment(self, k: int) -> None:
        del self.f[self.refs[k]][k]
        self._update_minf()
        self.refs[k] += 1
        self.f[self.refs[k]][k] = 1


if __name__ == "__main__":
    unittest.main()