Caching Grid Computations with Tuple Keys

Hard ⏱ 18 min 34% acceptance ★★★★☆ 4.4
Implement get_or_compute(cache, x, y, compute_fn), where cache is a dict whose keys are (x, y) coordinate tuples. If (x, y) is already a key in cache, return the cached value without calling compute_fn. Otherwise call compute_fn(x, y), store the result under the (x, y) tuple key, and return it. This relies on tuples being hashable — unlike lists, they can be used directly as dict keys.

Examples

Example 1
Input
cache = {}; get_or_compute(cache, 2, 3, lambda x, y: x * y)
Output
6
Explanation

Computed once and stored under cache[(2, 3)] = 6.

Example 2
Input
get_or_compute(cache, 2, 3, some_fn)  # called again with the same coords
Output
6
Explanation

Returned straight from the cache; some_fn is never invoked this time.

Constraints

  • compute_fn must not be called again for coordinates already present in cache.

Topics

TuplesDictionaries

Companies

UberSwiggyDataVix

Hints

Hint 1

Build key = (x, y) and check `if key in cache` first.

Hint 2

Only call compute_fn(x, y) on a cache miss, then store and return it.

← Employee Records with namedtuple Rotate Three Variables in One Line →
Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.