Bounded Memoization Cache

Jane StreetPhone screenMedium

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.

Part 1: Unbounded memo

Implement get, computations and size with a cache that keeps every result forever. Here Memo() is constructed with no arguments.

A call for an argument seen before returns the stored value and does not evaluate f.

Example 1
init
[]
operations
[["get",[3]],["get",[3]],["get",[4]],["get",[3]],["computations",[]],["size",[]]]
Output
[10,10,17,10,2,2]
Why: 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.

Constraints

1 <= len(operations) <= 10^4
-10^4 <= x <= 10^4