Simulate an LRU-Evicted Prefix Cache
Intermediate
The problem, from first principles
Recomputing a prompt's shared prefix (a system prompt, a long set of instructions, the start of a multi-turn conversation) on every single request wastes compute that was already spent producing the exact same result moments earlier. Caching the computation for recently seen prefixes avoids that -- but the cache has finite room, so something has to give when it fills up.
The task
Write simulate_prefix_cache(capacity, requests), simulating a prefix cache holding at most capacity distinct prefixes with least-recently-used (LRU) eviction. For each request in order, return whether it was a hit (already cached) or a miss, and update recency accordingly.
Keywords
production-systemsinference-optimization
Python
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.