Cache Eviction (Strategy Pattern)Step 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:
        #   victim = min(self._order, key=lambda k: self._counts[k])
        #   self._order.remove(victim)
        #   del self._counts[victim]
        #   return victim
        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