Katkat
Back

Code Review: Find the Problems in a Python Dict-Based Memoization Cache

MercorSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

A Python code review question about a function that memoizes an expensive computation in a module-level dictionary. It tests whether a candidate can find correctness, memory, concurrency and key-equality problems in simple caching code and propose fixes with clear trade-offs.

Review the following Python code, which caches the results of an expensive computation. Explain everything that is wrong with it or risky about it, and how you would fix it.

from library import expensive_computation

cache = {}

def compute(x):
 if x in cache
 return cache[x]
 y = expensive_computation(x)
 cache[x] = y
 return y

The code is shown as the source reported it, including the if line without a trailing colon. library stands for any module that provides the expensive function.

Clarifying Questions

  • Is expensive_computation deterministic and free of side effects, or can its result for the same input change over time?
  • What types can x be, and does the function return mutable objects such as lists or dicts?
  • Is compute called from several threads, several processes, or both?
  • Roughly how many distinct inputs are there, and how much memory may the cache use?

Hints

Hint 1

Beyond a single call: Picture this function inside a long-running service with many callers, and think about what the module-level dict looks like after a week.

Hint 2

What counts as the same x: Consider which arguments can be dict keys at all, and when two different arguments end up on the same entry.

Follow-up questions

  • Rewrite the function with `functools.lru_cache`. What does the decorator guarantee under concurrent calls, and what does it not?
  • Two threads ask for the same uncached `x` at the same moment. Change the code so that `expensive_computation` runs only once for it.
  • The service now runs as several worker processes on several machines. Where should the cache live, and what changes?
  • `expensive_computation` sometimes raises or times out. Should failures be cached?