Memoize - Problem
Given a function fn, return a memoized version of that function.
A memoized function is a function that will never be called twice with the same inputs. Instead it will return a cached value.
You can assume there are 3 possible input functions: sum, fib, and factorial.
- sum accepts two integers a and b and returns a + b. Assume that if a value has already been cached for the arguments (b, a) where a != b, it cannot be used for the arguments (a, b). For example, if the arguments are (3, 2) and (2, 3), two separate calls should be made.
- fib accepts a single integer n and returns 1 if n <= 1 or fib(n - 1) + fib(n - 2) otherwise.
- factorial accepts a single integer n and returns 1 if n <= 1 or factorial(n - 1) * n otherwise.
Input & Output
Example 1 — Fibonacci Function
$
Input:
fn = "fib"
›
Output:
8
💡 Note:
The memoized fibonacci function calculates fib(5). With memoization, fib(1) through fib(5) are calculated only once each, returning 8 efficiently.
Example 2 — Sum Function
$
Input:
fn = "sum"
›
Output:
5
💡 Note:
The memoized sum function calculates sum(2, 3) = 5. The result is cached, so subsequent calls with (2, 3) return instantly.
Example 3 — Factorial Function
$
Input:
fn = "factorial"
›
Output:
120
💡 Note:
The memoized factorial function calculates factorial(5) = 5! = 120. Each factorial(n) for n=1 to 5 is computed once and cached.
Constraints
- 1 ≤ function calls ≤ 105
- 1 ≤ function arguments ≤ 100
- Functions will be one of: sum, fib, factorial
Visualization
Tap to expand
Understanding the Visualization
1
Input
Original function (sum, fib, or factorial)
2
Process
Wrap function with cache layer
3
Output
Memoized function with O(1) cache lookups
Key Takeaway
🎯 Key Insight: Memoization transforms expensive recursive computations into fast cached lookups using a hash map
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code