⚡Flashcard Drill➔
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

  1. Use a Map from a serialised argument signature to the result.
  2. Serialise the argument array with JSON.stringify(args) to form the key.
  3. Check the cache before calling; on a miss, run fn, store the result, and return it.
  4. A Map is 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 argument 1,2 serialise to the same text.
  • Using a plain object instead of a Map: string keys such as constructor collide with inherited prototype properties.
  • Declaring the cache outside the returned function: separate memoize instances would then share one cache.
  • Calling get without has: a cached undefined value 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.
🎯 Drill This Card Now➔

🧩 Related JavaScript Problems