Memoization Cache

Asked at Jane Street· Screen

Reported by the problem's creator, not verified

You memoize the function f(x) = x * x + 1 for an integer x. Pretend each evaluation of f is costly.

Implement a class Memo with three methods:

get(x) returns f(x), evaluating f only when the result is not already cached.
computations() returns how many times f has been evaluated so far.
size() returns how many results are cached right now.

The constructor is Memo(capacity=None, policy="fifo"). Each test drives one Memo instance through a sequence of calls and checks every return value.

Example 1
Input: init = [], operations = [["get",[3]],["get",[3]],["get",[4]],["get",[3]],["computations",[]],["size",[]]]
Output: [10,10,17,10,2,2]
Explanation: The first get(3) computes 3*3+1 = 10. The second is a hit, so only get(4) adds a second computation; computations() and size() are both 2.

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question

Memoization Cache

Examples

Example 1

Code