NeetCode #952LC-2623MediumJavaScript
← Back to All Problems#952 · #2623 · Memoize(记忆函数)
📌 Problem Statement & Constraints
Implement
memoize(fn), returning a cached version of fn. If the function has already been called with the same arguments, return the cached result without re-executing fn. There may be 1 to 10 arguments, all strings or integers.💡 Core Algorithmic Approaches
- Use a
Mapfrom a serialised argument signature to the result. - Serialise the argument array with
JSON.stringify(args)to form the key. - Check the cache before calling; on a miss, run
fn, store the result, and return it. - A
Mapis preferred over a plain object because it avoids prototype-key collisions and supports any string key safely.
💻 Benchmark Python3 Implementation
function memoize(fn) {
const cache = new Map();
return function(...args) {
const key = JSON.stringify(args); // serialise arguments into a cache key
if (cache.has(key)) {
return cache.get(key); // cache hit
}
const val = fn(...args);
cache.set(key, val);
return val;
};
}⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) per call besides serialisation, which is proportional to the argument count.
💾 Space Complexity
O(k): one entry per distinct argument combination.
⚠️ Interview Pitfalls & Follow-ups
- Using
args.toString()as the key: different argument lists can collide, since[1, 2]and a single string argument1,2serialise to the same text. - Using a plain object instead of a
Map: string keys such asconstructorcollide with inherited prototype properties. - Declaring the cache outside the returned function: separate
memoizeinstances would then share one cache. - Calling
getwithouthas: a cachedundefinedvalue would be recomputed every time.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.