Build a Cache with Pluggable EvictionStep 3 of 5

The LFU Policy

12345

Step 3: The LFU Policy

LFU (least-frequently-used) evicts the key with the fewest accesses, betting that popularity predicts future use. It needs a frequency count per key, and a tie-breaker when several keys share the lowest count, here, the oldest-inserted among them.

  • LFUPolicy.evict(): return and remove the key with the smallest access count, breaking ties by insertion order
Hints
Starter code
class EvictionPolicy:
    def on_insert(self, key):
        raise NotImplementedError

    def on_access(self, key):
        raise NotImplementedError

    def evict(self):
        raise NotImplementedError


class LFUPolicy(EvictionPolicy):
    def __init__(self):
        self._counts = {}           # key -> access count
        self._order = []            # insertion order, for tie-breaking

    def on_insert(self, key):
        self._counts[key] = 1
        self._order.append(key)

    def on_access(self, key):
        self._counts[key] = self._counts.get(key, 0) + 1

    def evict(self):
        """Remove and return the least-frequently-used key (ties: oldest first)."""
        # TODO: choose the victim with the smallest count in self._counts,
        # scanning in the order recorded by self._order so a tie goes to the
        # oldest-inserted key. Forget the victim in both structures, then hand
        # the victim key itself back to the caller.
        pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step