Practice problem · Bloomberg · Medium

Cache Policies: Refactor LRU for LFU and Beyond

A local in-memory cache, lru_cache.py: get, put, delete, a fixed capacity, and one eviction policy, least recently used, with the order kept in a doubly linked list. 3 stages in Python with an AI assistant. Pro.

Stage 1 of 3: Split the cache from its policy

Background. A local in-memory cache, lru_cache.py: get, put, delete, a fixed capacity, and one eviction policy, least recently used, with the order kept in a doubly linked list. The team wants other policies next (LFU first), and does not want a second cache per policy. The storage should know nothing about how a victim is chosen.

Refactor it into cache.py: Cache(capacity, policy) owns the storage and exposes capacity; a policy owns the order. The interface the cache uses is EvictionPolicy, already in the file: touch(key) when an existing key is accessed (a get hit, or a put that updates it), add(key) after a new key is stored, remove(key) when a key is deleted, and evict(), asked only when the cache is full and a new key is about to be stored; the cache drops the key the policy returns and never looks inside the policy. Implement Cache and LRUPolicy. runner.py is not part of this stage; leave it as it is.

  • get(key) returns the value, or None for a miss; a miss tells the policy nothing. put(key, value) stores or updates. delete(key) returns whether the key was there; deleting a missing key tells the policy nothing. len(cache) and key in cache work and are not accesses.
  • capacity must be a positive integer (ValueError otherwise; True and 2.0 are not integers).
  • Evict, then add: when a new key arrives at a full cache, the policy chooses among the keys the cache holds, the cache drops that one, stores the new key, and then tells the policy add.
  • Cache(n, LRUPolicy()) behaves exactly like LRUCache(n) on any sequence of operations. lru_cache.py stays as it is; the tests use it as the oracle.

Example

c = Cache(2, LRUPolicy())
c.put("a", 1); c.put("b", 2)
c.get("a")            # 1; b is now the least recently used
c.put("c", 3)         # b is evicted
c.get("b")            # None

Done when Submit goes green.

Constraints

  • Python 3.12+ standard library only
  • Time limit: 10 seconds per test file
  • Editable: cache.py, runner.py
  • Read-only: lru_cache.py, test_helpers.py and all tests/test_*.py files

What comes after stage 1

The next stages open once the tests for the one before them pass. Each raises the bar, the way an interviewer does in the room.

  1. Stage 2: Least frequently used. The second policy, and the reason for the first stage: counts, a tie rule, and the same cache underneath.
  2. Stage 3: FIFO, MRU, scripts and speed. Two policies that should cost nothing to add, a script format, and a time budget at 100,000 operations.

The files you get

  • Yours to edit: cache.py, runner.py.
  • Read-only: lru_cache.py, test_helpers.py, tests/__init__.py.
  • Tests you can read and run: tests/test_part1_refactor.py. Hidden tests run on Submit.

The round: an agent in the editor

The assistant here works like the one in the interview IDE. It reads your files, runs code and proposes changes, and you accept or reject each one. It doesn't volunteer ideas, so what gets built is what you asked for. Along the way the interviewer asks about your decisions, and at the end the report says what you checked and what you accepted unread.

Frequently asked, briefly answered

Is Cache Policies: Refactor LRU for LFU and Beyond free?

It is a Pro problem. Free plan includes one complete problem, plus the first stage of several more, so you can see how a round works before you pay.

Which company asks something like this?

Bloomberg. It is modelled on Bloomberg's round: Technical phone screen round with an AI assistant, and two AI-enabled interviews in the 2027 new-grad process: an existing implementation to refactor or extend while the interviewer discusses the design.

Do I bring my own AI tool?

No. The assistant is in the editor, same as in the interview IDEs at Meta, Stripe and Amazon. What you choose at Begin is the format: an agent that proposes changes you accept or reject, an answer-only assistant that can't write code, or no assistant at all.

What does the interviewer ask?

3 questions along the way about your own code, and one at the end about the whole session. A weak answer gets one follow up. The answers go into the report, which ends with a hire or no hire verdict.

Start the problem

Sign in and the problem opens where you left it. New here? An account takes a minute to create, and the Pro plan starts at the first stage of this problem.

Start this problem → Sign in

More like it: every practice problem, how Bloomberg runs its AI round, the AI coding interview guide.