Practice problem · Anthropic · Hard

Python LRU Cache: Call Keys and Crash Safety

memo.py holds memoize(maxsize=128), a decorator that keeps a function's results in a least-recently-used cache. 2 stages in Python written by you, with an assistant that only answers. Pro.

Stage 1 of 2: Same call, same entry

memo.py holds memoize(maxsize=128), a decorator that keeps a function's results in a least-recently-used cache. A call whose key is held returns the stored result and becomes the most recently used entry; otherwise the function runs, its result is stored, and when more than maxsize entries are held the least recently used one is dropped. cache_info() returns CacheInfo(hits, misses, maxsize, currsize) and cache_clear() empties the cache and sets both counts to 0. Today make_key builds the key from the arguments exactly as they are written.

Rewrite make_key(func, args, kwargs) so that two calls share one cache entry exactly when they are the same call.

  • The same call. Match each call to the function's parameters the way Python does when it calls the function, with every parameter that is not passed taking its default. Two calls are the same call when every parameter gets the same value. So an argument passed by position or by keyword, keyword arguments in any order, and an argument left out or passed as its default are all the same call. Extra positional arguments (*args) are compared in order, extra keyword arguments (**kwargs) as a mapping, in any order. Positional-only and keyword-only parameters follow the same matching.
  • The same value. Two values are the same when they have the same type and: for None, bool, int, float and str, equal values; for lists and tuples, the same length and the same values in order; for dicts, the same keys with the same values, in any order; for sets and frozensets, the same elements, in any order. So 1, 1.0, True and "1" are four different values, [1, 2] is not (1, 2) and {1} is not frozenset({1}), while {"a": 1, "b": 2} is {"b": 2, "a": 1}.
  • What arguments hold. Argument values are built from None, bool, int, float, str, lists and tuples, dicts with string keys, and sets and frozensets of None, bool, int, float and str, nested to any depth. A call with a value of any other type anywhere in its arguments (bytes, a complex number, an object, a function) raises TypeError before the function runs, and changes nothing: nothing is stored and both counts stay as they were. That includes a dict key that is not a str, a set element that is not one of the five scalar types, and a value of a subclass of these types (an OrderedDict, an IntEnum member): a subclass is another type.
  • Calls that do not fit. A call that does not match the function's parameters raises TypeError, as calling the function would. The function does not run and nothing changes.
  • The function sees its own arguments. On a miss it runs with its arguments exactly as given: a list stays a list, a set a set.

The cache itself is correct and stays as it is. Each decorated function has its own cache.

Example

@memoize(maxsize=2)
def price(item, qty=1, *extras, currency="EUR", **options):
    ...

price("tea", 2)                                   # miss: the function runs
price(qty=2, item="tea")                          # hit: the same call
price("tea", 2, currency="EUR")                   # hit: currency left out is its default
price("tea", 2, gift=True, wrap=["red", "gold"])  # miss
price("tea", 2, wrap=["red", "gold"], gift=True)  # hit: extra keywords in any order
price("tea", 2.0)                                 # miss: 2.0 is a float, not the int 2
price.cache_info()  # CacheInfo(hits=3, misses=3, maxsize=2, currsize=2)

Notes

  • The decorated functions in the tests are plain functions written with def. No test passes a NaN or infinite float, or -0.0, or an int of more than 4300 digits.
  • No test nests values more than a few levels deep, so walking them recursively is fine.
  • Every default value in the tests is a supported value.
  • On the starter, 16 of the 20 tests in tests/test_part1.py fail.

Done when Submit goes green.

Constraints

  • Python 3.12 standard library only
  • Editable: memo.py
  • Read-only: all tests/test_*.py files
  • Supported argument values are None, bool, int, float, str, lists, tuples, dicts with string keys, and sets and frozensets of those five scalar types, nested; a call with any other value, a subclass of these types included, raises TypeError
  • No test passes a NaN or infinite float, or -0.0, or an int of more than 4300 digits

What comes after stage 1

The next stage opens once the tests for the one before it pass. Each raises the bar, the way an interviewer does in the room.

  1. Stage 2: Survive a crash. The cache must come back after its process is killed at any moment, even partway through writing to disk.

The files you get

  • Yours to edit: memo.py.
  • Tests you can read and run: tests/test_part1.py. Hidden tests run on Submit.

The round: no AI, an assistant that only answers

Anthropic runs this round without AI. Here the closest format is answer-only: the assistant answers your questions and reviews your code when you ask, the way an interviewer would, and never writes a line of it. The interviewer asks about your decisions as you go, and the report states the format. You can switch to the agent format when you press Begin.

Frequently asked, briefly answered

Is Python LRU Cache: Call Keys and Crash Safety 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?

Anthropic. It is modelled on Anthropic's coding round, which runs without AI. Based on candidates' reports of Anthropic interviews. Nyrion wrote this version, so the question you get may differ.

Do I bring my own AI tool?

No. The real round has no AI, so this one opens answer-only: an assistant that answers your questions and can't write code. You can switch to an agent that proposes changes when you press Begin.

What does the interviewer ask?

4 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, Anthropic's interviews, the AI coding interview guide.