Cache Eviction (Strategy Pattern)Step 1 of 5

The Strategy Interface + FIFO

12345

Step 1 — The Strategy Interface + FIFO

A cache that is full must throw something out, but which key is a separate decision from how the cache works. The Strategy pattern captures that decision as a swappable object: an EvictionPolicy the cache will consult. Every policy answers the same three questions — a key was inserted, a key was accessed, and who should be evicted.

Start with the simplest policy, FIFO (first-in, first-out): evict whichever key was inserted longest ago, ignoring reads entirely.

  • FIFOPolicy.evict() — return and remove the oldest-inserted key
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 FIFOPolicy(EvictionPolicy):
    def __init__(self):
        self._order = []            # keys in insertion order

    def on_insert(self, key):
        self._order.append(key)

    def on_access(self, key):
        pass                        # FIFO does not care about reads

    def evict(self):
        """Return and remove the oldest-inserted key."""
        # TODO: return self._order.pop(0)
        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.

OverviewNext step