2630. Memoize II
Problem Description
The problem requires us to enhance a given function fn
by adding memoization to it. Memoization is an optimization technique used to increase the performance by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
The goal is to ensure that fn
, once memoized, does not compute the result again for inputs it has already processed. Instead, it should return the previously computed result. It is important to note that inputs are considered identical when they are strictly equal to each other (===
), meaning that the comparison must consider both value and type.
Intuition
To memoize a function, we need two main components: a cache to store previously computed values and a way to uniquely identify each set of inputs.
The provided solution creates a memoized version of the fn
function. Here's the thought process behind it:
-
Define a cache mechanism. The solution uses two maps:
idxMap
andcache
.idxMap
is used to assign a unique index for every distinct object.cache
is where the actual function outputs are stored, mapped by a unique key representing the function arguments.
-
Generate unique keys for function arguments. Since the arguments could be objects, and we need a primitive value as a key for caching, the approach abstracts every input using an index representation. It assigns a unique index to every unique object input and then creates a string from these indices, which represents the combination of arguments.
-
Wrap the original function
fn
with a new function that intercepts calls tofn
. For every call:- Generate a unique key for the arguments provided.
- Check if the result is already present in the
cache
. If it's there, return the cached result. - If the result is not cached, call
fn
with the original arguments, store the result in thecache
, and then return the computed result.
This approach ensures that if the memoized function is called again with the same combination of arguments (based on strict equality), it does not recompute the result but instantly returns the cached result, thereby saving time on subsequent calls with identical inputs.
Solution Approach
The solution uses the following algorithms, data structures, and patterns:
-
Closures: The memoize function returns a new function that maintains a closure over the
idxMap
andcache
. This allows the new function to have persistent private data (caches) that are accessible across multiple invocations. -
Map Object: Two Map objects are used.
cache
stores the results of the function calls with a unique string key for each set of parameters.idxMap
maps objects to unique indices. This is needed because we cannot use objects directly as keys in the cache Map.
-
Unique Key Generation: Each set of parameters needs to be uniquely identified to decide if the function output for those parameters is already cached. To achieve that uniqueness:
- We assign a unique index to every distinct object encountered as a parameter via the
getIdx
function. For non-object parameters that can be directly compared by value (like numbers, strings, etc.), their "index" is effectively the value itself. - The unique key for the
cache
map is generated by concatenating the indices of the parameters with commas, ensuring a string that represents the parameters' combination.
- We assign a unique index to every distinct object encountered as a parameter via the
-
Memoization Logic: When the returned function is called, a key is generated to represent the parameters. The function then does the following:
- Checks
cache
to see if the key exists, indicating that the function has been called before with these parameters. If so, the cached value is returned, preventing the recalculation. - If the key does not exist in the cache, it calls
fn
with the given parameters, stores the result incache
using the generated key, and returns the result.
- Checks
The algorithm is efficient because it avoids redundant computation by storing function results that have already been computed, using only the memory needed to store unique calls. The use of a Map object for caching provides constant-time retrieval, making the look-up process fast.
Here's a walkthrough of the implementation steps in code:
- Define the
memoize
function which takes the functionfn
as an argument. - Inside
memoize
, initialize theidxMap
andcache
maps. - Define the
getIdx
function, which assigns and retrieves a unique index for object parameters. - Return a new function from
memoize
that wraps the original functionfn
. - In the wrapped function, generate a key based on the parameters using
getIdx
. - Check if the key exists in
cache
. If it does, return the stored value. - If the key does not exist, compute the result using
fn
, store it incache
, and return it.
This memoize
function can then be applied to any function fn
to create a memoized version of it, thereby optimizing it for scenarios where the function is likely to be called multiple times with the same set of parameters.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example by applying the memoization technique to a simple function — a Fibonacci sequence generator. The Fibonacci function fib
is well-known for its efficiency issues with recursive calls because it recalculates the same values multiple times.
Here's the fib
function without memoization:
1function fib(n) {
2 if (n === 0 || n === 1) {
3 return n;
4 }
5 return fib(n - 1) + fib(n - 2);
6}
Now, let's apply the memoize
function to fib
to create a memoized version:
1const memoizeFib = memoize(fib);
Next, we'll see how memoization optimizes the function calls. Suppose we call memoizeFib(5)
:
- The function checks if the result for
5
is in thecache
. It's not, so it computesfib(5)
. - To compute
fib(5)
, it needsfib(4)
andfib(3)
. These calls go through the memoized function as well. - Recursive calls continue until it hits the base case for
fib(0)
andfib(1)
, which return0
and1
, respectively. Each computed value gets stored in thecache
. - It then combines cached results to return
fib(5)
without additional redundant calls. - The result is stored in the
cache
with the key'5'
.
Now, if we call memoizeFib(5)
again:
- The function generates the key
'5'
. - It finds the key in the
cache
and returns the stored result immediately without recomputation.
Here are the specific steps the memoization follows for fib
:
- When
memoizeFib(5)
is called for the first time, thecache
is empty, so it calculates and stores the result for each unique call offib
(i.e.,fib(5)
,fib(4)
,fib(3)
,fib(2)
,fib(1)
, andfib(0)
). - For the sake of example, assume that calculating
fib(5)
indirectly led to two calls tofib(3)
. The first call would compute and cache the result. The second call tofib(3)
would immediately return the cached result. - The memoization saves computation time by storing the result of each unique
fib(n)
so all subsequent calls for thesen
values will be returned instantly from thecache
.
Applying the memoize
function to fib
drastically improves its performance, especially for large values of n
, because the number of computations from an exponential to a linear growth in terms of the input.
This walkthrough illustrates the core idea of memoization and how it can be applied to optimize a computationally expensive recursive function.
Solution Implementation
1from typing import Any, Callable, Dict
2
3# Define the type for a function that can take any number of any type of parameters and return any type.
4# In Python, we use 'Callable' from the 'typing' module to represent such a function.
5FunctionWithAnyParams = Callable[..., Any]
6
7def memoize(fn: FunctionWithAnyParams) -> FunctionWithAnyParams:
8 """
9 Utility function to memoize another function to cache its results based on the arguments passed.
10 This can optimize the performance of functions with expensive computations when called with the same arguments.
11 """
12 # Dictionary to keep track of a unique index for each unique object argument.
13 object_index_map: Dict[Any, int] = {}
14 # Cache to store results based on a unique key for the function arguments.
15 cache: Dict[str, Any] = {}
16
17 def get_object_index(obj: Any) -> int:
18 """
19 Helper function to obtain a unique index for an object.
20 If it encounters the same object multiple times, it returns the same index.
21 """
22 if obj not in object_index_map:
23 object_index_map[obj] = len(object_index_map)
24 return object_index_map[obj]
25
26 def memoized_function(*params: Any) -> Any:
27 """
28 Returns a function that wraps the passed function with memoization.
29 """
30 # Construct the cache key based on unique indices for the function arguments.
31 # For non-object parameters, their value is used directly in the cache key.
32 key = ','.join(str(get_object_index(param) if isinstance(param, (dict, list)) else param)
33 for param in params)
34 # Check the cache; if the result is not cached yet, compute and cache it.
35 if key not in cache:
36 # This calls the original function with the spread parameters.
37 cache[key] = fn(*params)
38 # Return the cached result.
39 return cache[key]
40
41 return memoized_function
42
43
44# Example of how to use:
45# call_count = 0
46
47# def add(a, b):
48# global call_count
49# call_count += 1
50# return a + b
51
52# memoized_add = memoize(add)
53# print(memoized_add(2, 3)) # returns 5, the result is computed.
54# print(memoized_add(2, 3)) # returns 5, the result is retrieved from cache.
55# print(call_count) # outputs 1, because the function was actually called only once.
56
1import java.util.HashMap;
2import java.util.Map;
3
4// Functional interface definition for a function that can take any number of any type of parameters and returns any type.
5@FunctionalInterface
6interface FunctionWithAnyParams {
7 Object apply(Object... params);
8}
9
10public class MemoizationUtil {
11
12 // Utility function to memoize another function to cache its results based on the arguments passed.
13 // This can optimize the performance of functions with expensive computations when called with the same arguments.
14 public static FunctionWithAnyParams memoize(FunctionWithAnyParams fn) {
15 // Map to keep track of a unique index for each unique object argument.
16 Map<Object, Integer> objectIndexMap = new HashMap<>();
17 // Cache to store results based on a unique key for the function arguments.
18 Map<String, Object> cache = new HashMap<>();
19
20 // Return a function that wraps the passed function with memoization.
21 return (params) -> {
22 // Construct the cache key based on unique indices for the function arguments.
23 final StringBuilder keyBuilder = new StringBuilder();
24 for (Object param : params) {
25 if (param instanceof Object[]) {
26 keyBuilder.append(System.identityHashCode(param));
27 } else {
28 keyBuilder.append(param == null ? "null" : param.toString());
29 }
30 keyBuilder.append(',');
31 }
32 String key = keyBuilder.toString();
33
34 // Check the cache; if the result is not cached yet, compute and cache it.
35 if (!cache.containsKey(key)) {
36 // This spreads the parameters and calls the original function.
37 cache.put(key, fn.apply(params));
38 }
39 // Return the cached result.
40 return cache.get(key);
41 };
42 }
43
44 // Example of how to use:
45 public static void main(String[] args) {
46 // Sample usage of the memoize function
47 int[] callCount = {0};
48 FunctionWithAnyParams memoizedAdd = memoize((params) -> {
49 callCount[0]++;
50 return (int) params[0] + (int) params[1];
51 });
52
53 // Compute the result of adding 2 and 3. The result is computed since it's not cached yet.
54 System.out.println(memoizedAdd.apply(2, 3)); // Outputs 5, the first time the result is computed.
55 // Try adding 2 and 3 again. This time the result is retrieved from the cache.
56 System.out.println(memoizedAdd.apply(2, 3)); // Outputs 5, the result is retrieved from cache.
57 // The number of times the function has actually been called. Should output 1.
58 System.out.println(callCount[0]); // Outputs 1, because the memoized function was actually called only once.
59 }
60}
61
1#include <functional> // for std::function
2#include <map> // for std::map
3#include <string> // for std::string
4#include <sstream> // for std::stringstream
5#include <vector> // for std::vector
6
7// Function type that takes any number of parameters of any type and returns any value.
8using FunctionWithAnyParams = std::function<std::string(std::vector<std::string>)>;
9
10// Utility function to memoize another function to cache its results based on the arguments passed.
11FunctionWithAnyParams memoize(FunctionWithAnyParams fn) {
12 // Map to keep track of a unique index for each unique object argument.
13 std::map<void*, int> objectIndexMap;
14 // Cache to store results based on a unique key for the function arguments.
15 std::map<std::string, std::string> cache;
16
17 // Functor to obtain a unique index for an object.
18 auto getObjectIndex = [&objectIndexMap](void* obj) -> int {
19 // If the object hasn't been seen before, assign it a new index.
20 if (objectIndexMap.find(obj) == objectIndexMap.end()) {
21 int index = objectIndexMap.size();
22 objectIndexMap[obj] = index;
23 }
24 return objectIndexMap[obj];
25 };
26
27 // Return lambda function wrapped around the passed function with memoization.
28 return [fn, &cache, getObjectIndex](std::vector<std::string> params) -> std::string {
29 std::stringstream keyStream;
30 // Construct the cache key based on parameters.
31 for (auto& param : params) {
32 keyStream << param << ",";
33 }
34 std::string key = keyStream.str();
35
36 // Check the cache; if the result is not cached yet, compute and cache it.
37 if (cache.find(key) == cache.end()) {
38 // This calls the original function with the parameters.
39 cache[key] = fn(params);
40 }
41
42 // Return the cached result.
43 return cache[key];
44 };
45}
46
47// Example usage:
48/*
49int callCount = 0;
50auto memoizedAdd = memoize([&callCount](std::vector<std::string> params) -> std::string {
51 callCount++;
52 int a = std::stoi(params[0]);
53 int b = std::stoi(params[1]);
54 return std::to_string(a + b);
55});
56
57std::cout << memoizedAdd({"2", "3"}) << std::endl; // Outputs "5", the function computes the result.
58std::cout << memoizedAdd({"2", "3"}) << std::endl; // Outputs "5", the result is retrieved from the cache.
59std::cout << callCount << std::endl; // Outputs "1", function is actually called only once.
60
1// Type definition for a function that can take any number of any type of parameters and returns any type.
2type FunctionWithAnyParams = (...params: any[]) => any;
3
4// Utility function to memoize another function to cache its results based on the arguments passed.
5// This can optimize the performance of functions with expensive computations when called with the same arguments.
6function memoize(fn: FunctionWithAnyParams): FunctionWithAnyParams {
7 // Map to keep track of a unique index for each unique object argument.
8 const objectIndexMap: Map<unknown, number> = new Map();
9 // Cache to store results based on a unique key for the function arguments.
10 const cache: Map<string, any> = new Map();
11
12 // Helper function to obtain a unique index for an object.
13 // If it encounters the same object multiple times, it returns the same index.
14 const getObjectIndex = (obj: unknown): number => {
15 if (!objectIndexMap.has(obj)) {
16 objectIndexMap.set(obj, objectIndexMap.size);
17 }
18 return objectIndexMap.get(obj)!; // Using non-null assertion because we know the key exists in the map.
19 };
20
21 // Return a function that wraps the passed function with memoization.
22 return function (...params: any[]): any {
23 // Construct the cache key based on unique indices for the function arguments.
24 const key = params.map(param => typeof param === 'object' ? getObjectIndex(param) : param).join(',');
25 // Check the cache; if the result is not cached yet, compute and cache it.
26 if (!cache.has(key)) {
27 // This spreads the parameters and calls the original function.
28 cache.set(key, fn(...params));
29 }
30 // Return the cached result.
31 return cache.get(key)!; // Using non-null assertion because we set the value before or it's already cached.
32 };
33}
34
35// Example of how to use:
36// let callCount = 0;
37// const memoizedAdd = memoize(function (a, b) {
38// callCount += 1;
39// return a + b;
40// });
41// memoizedAdd(2, 3) // returns 5, the result is computed.
42// memoizedAdd(2, 3) // returns 5, the result is retrieved from cache.
43// console.log(callCount) // outputs 1, because the function was actually called only once.
44
Time and Space Complexity
The time complexity and space complexity of the code are as follows:
Time Complexity
For function memoize
:
- The
getIdx
function has a time complexity ofO(1)
for each call due to the direct access of Maps. memoize
generates a key by iterating over the input parameters and callinggetIdx
. If there aren
parameters, this process has a time complexity ofO(n)
since it maps each parameter.- Checking the cache and potentially executing the function
fn
with...params
depends on:- The number of unique parameter combinations passed (
m
), which would be the number of unique keys, and - The time complexity of the function
fn
itself (let's denote this asT(fn)
).
- The number of unique parameter combinations passed (
Hence, the time complexity can vary depending on whether the data is present in the cache:
- First call with new parameters:
O(n) + T(fn)
. - Subsequent calls with the same parameters:
O(n)
, since it will retrieve the result directly from the cache.
Space Complexity
- The
idxMap
map keeps growing as new unique objects are passed, which leads to space complexity ofO(u)
, whereu
is the number of unique object parameters seen over all calls. - Similarly, the
cache
map stores the results for each unique parameter combination. Thus, it has a space complexity ofO(m)
, wherem
is the number of unique parameter combinations.
The overall space complexity is O(u + m)
.
In conclusion, the final overall time complexity is dependent on the specific use case, particularly the complexity of fn
and the unique parameter combinations. The space complexity is a combination of unique objects encountered and unique stored results.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time