Problem Description

You need to create a memoization wrapper function that takes any function as input and returns a memoized version of it. A memoized function caches its results based on the input arguments, so when called with the same inputs again, it returns the cached result instead of recalculating.

The function should handle three specific types of input functions:

1. sum(a, b): Takes two integers and returns their sum a + b. Important note: the order of arguments matters - (3, 2) and (2, 3) are treated as different inputs and should have separate cache entries.

2. fib(n): Calculates the Fibonacci number for a given integer n. Returns 1 if n <= 1, otherwise returns fib(n - 1) + fib(n - 2).

3. factorial(n): Calculates the factorial of an integer n. Returns 1 if n <= 1, otherwise returns factorial(n - 1) * n.

The memoization mechanism should:

• Check if the result for given arguments already exists in the cache
• If yes, return the cached value without calling the original function
• If no, call the original function, store the result in the cache, and return it

The provided solution uses a JavaScript object as a cache, where the arguments array is used as the key (which gets implicitly converted to a string). When the memoized function is called, it first checks if the arguments exist in the cache. If found, it returns the cached result immediately. Otherwise, it executes the original function, stores the result in the cache, and returns it.

Intuition

The key insight here is recognizing that many functions, especially recursive ones like Fibonacci and factorial, end up computing the same values multiple times. For example, when calculating fib(5), we need fib(4) and fib(3). But fib(4) itself needs fib(3) and fib(2). Notice how fib(3) gets calculated twice? This redundancy grows exponentially as n increases.

Memoization solves this by trading space for time - we store previously computed results so we never have to recalculate them. Think of it like taking notes while solving a math problem: once you've calculated something, you write it down so you can just look it up if you need it again.

The natural data structure for this is a hash map (or JavaScript object), where we can store key-value pairs. The challenge is determining what to use as the key. Since functions can have multiple arguments, we need a way to uniquely identify each combination of arguments.

In JavaScript, when we use an array as an object key like cache[args], the array gets automatically converted to a string. For example, [2, 3] becomes "2,3". This works perfectly for our use case because:

• It creates a unique string for each combination of arguments
• The order is preserved (so [2, 3] and [3, 2] create different keys: "2,3" vs "3,2")
• It handles single arguments naturally ([5] becomes "5")

The wrapper function pattern (returning a new function that has access to the cache through closure) allows us to maintain state between function calls while keeping the interface clean. Each memoized function gets its own cache, isolated from others, which is exactly what we want.

Solution Approach

The implementation uses a closure pattern to create a memoized version of any function. Let's walk through the solution step by step:

1. Function Signature

function memoize(fn: Fn): Fn

The function takes a function fn as input and returns a new function with the same signature but with memoization capability.

2. Cache Storage

const cache: Record<any, any> = {};

We create an empty object to serve as our cache. This object will store key-value pairs where:

• Key: stringified version of the arguments array
• Value: the result of calling fn with those arguments

3. Return a Wrapper Function

return function (...args) {
    // memoization logic
}

We return a new function that accepts any number of arguments using the rest parameter ...args. This wrapper function has access to both the original function fn and the cache object through closure.

4. Cache Lookup

if (args in cache) {
    return cache[args];
}

When the wrapper function is called, we first check if we've seen these arguments before. The args array is automatically converted to a string when used as an object key. For example:

• memoizedSum(2, 3) → args = [2, 3] → key = "2,3"
• memoizedFib(5) → args = [5] → key = "5"

If the key exists in our cache, we immediately return the cached value without executing the original function.

5. Compute and Cache

const result = fn(...args);
cache[args] = result;
return result;

If the arguments haven't been seen before:

1. Call the original function with the spread arguments fn(...args)
2. Store the result in the cache using the arguments as the key
3. Return the result

Why This Works:

• The string conversion of arrays preserves order, so (2, 3) and (3, 2) map to different cache keys ("2,3" vs "3,2")
• Each memoized function maintains its own cache through closure
• The solution is generic enough to work with any function signature
• Once a value is cached, subsequent calls with the same arguments have O(1) lookup time

This approach is particularly effective for recursive functions like Fibonacci, where the same subproblems are solved multiple times. With memoization, each unique input is computed only once, dramatically improving performance from exponential to linear time complexity.

Example Walkthrough

Let's walk through how memoization works with a Fibonacci example, calculating fib(4):

Initial Setup:

function fib(n) {
    if (n <= 1) return 1;
    return fib(n - 1) + fib(n - 2);
}
const memoizedFib = memoize(fib);

First Call: memoizedFib(4)

• Check cache for key "4": Not found
• Execute fib(4), which needs fib(3) + fib(2)
• This triggers recursive calls:

Recursive Call: memoizedFib(3)

• Check cache for key "3": Not found
• Execute fib(3), which needs fib(2) + fib(1)

Recursive Call: memoizedFib(2)

• Check cache for key "2": Not found
• Execute fib(2), which needs fib(1) + fib(0)

Base Cases:

• memoizedFib(1): Cache miss → compute result = 1 → cache["1"] = 1
• memoizedFib(0): Cache miss → compute result = 1 → cache["0"] = 1

Unwinding:

• memoizedFib(2) returns 1 + 1 = 2 → cache["2"] = 2
• memoizedFib(1): Cache hit! → return cache["1"] = 1 (no recomputation)
• memoizedFib(3) returns 2 + 1 = 3 → cache["3"] = 3
• memoizedFib(2): Cache hit! → return cache["2"] = 2 (no recomputation)
• memoizedFib(4) returns 3 + 2 = 5 → cache["4"] = 5

Final Cache State:

cache = {
    "0": 1,
    "1": 1,
    "2": 2,
    "3": 3,
    "4": 5
}

Second Call: memoizedFib(4)

• Check cache for key "4": Found!
• Return cache["4"] = 5 immediately (no function execution)

Notice how memoizedFib(2) and memoizedFib(1) were called multiple times during the recursion, but only computed once. The second time they were needed, we retrieved them from the cache instantly. This transforms the exponential time complexity O(2^n) into linear O(n).

Solution Implementation

Time and Space Complexity

Time Complexity:

• Cache lookup: O(k) where k is the number of arguments, as JavaScript converts the array args to a string key when using it with the in operator
• Cache insertion: O(k) for the same reason - array-to-string conversion
• Function execution: O(f) where f is the time complexity of the original function fn
• Overall per call:
  • First call with unique arguments: O(k + f)
  • Subsequent calls with same arguments: O(k)

Space Complexity:

• Cache storage: O(n * m) where n is the number of unique argument combinations cached and m is the average size of the stored results
• Closure scope: O(1) for maintaining reference to the original function
• Per call stack space: O(k) for storing the arguments array
• Overall: O(n * m + k)

Note on Implementation Issue: The current implementation has a bug - using args (an array) as a key in cache will convert it to a string using toString(), which means [1,2] and ["1,2"] would incorrectly map to the same cache key "1,2". A proper implementation should use JSON.stringify(args) or another serialization method for the cache key.

Common Pitfalls

1. Unhashable Arguments Problem

The most significant pitfall in the provided solution is that it uses json.dumps() to serialize arguments as cache keys. This approach fails when arguments contain unhashable or non-JSON-serializable objects:

Problem Example:

def process_data(data_dict):
    return sum(data_dict.values())

memoized_fn = memoize(process_data)
memoized_fn({1, 2, 3})  # TypeError: Object of type set is not JSON serializable
memoized_fn(lambda x: x)  # TypeError: Object of type function is not JSON serializable

Solution: Use a more robust key generation strategy that handles various data types:

def memoize(fn: Callable[..., Any]) -> Callable[..., Any]:
    cache = {}
  
    def memoized_function(*args: Any) -> Any:
        # Try to create a hashable key from arguments
        try:
            # For hashable arguments, use them directly as tuple
            key = args
        except TypeError:
            # For unhashable arguments, convert to string representation
            key = str(args)
      
        if key in cache:
            return cache[key]
      
        result = fn(*args)
        cache[key] = result
        return result
  
    return memoized_function

2. Memory Leak with Unbounded Cache

The cache grows indefinitely without any mechanism to limit its size, potentially causing memory issues in long-running applications:

Problem Example:

# This will create millions of cache entries
memoized_sum = memoize(lambda a, b: a + b)
for i in range(10_000_000):
    memoized_sum(i, i + 1)  # Each unique pair creates a new cache entry

Solution: Implement an LRU (Least Recently Used) cache with a maximum size:

from functools import lru_cache

def memoize(fn: Callable[..., Any]) -> Callable[..., Any]:
    # Use built-in LRU cache with max size
    @lru_cache(maxsize=128)
    def memoized_function(*args):
        return fn(*args)
  
    return memoized_function

# Or implement manually with OrderedDict
from collections import OrderedDict

def memoize_with_limit(fn: Callable[..., Any], maxsize: int = 128) -> Callable[..., Any]:
    cache = OrderedDict()
  
    def memoized_function(*args: Any) -> Any:
        key = str(args)
      
        if key in cache:
            # Move to end (most recently used)
            cache.move_to_end(key)
            return cache[key]
      
        result = fn(*args)
        cache[key] = result
      
        # Remove oldest item if cache exceeds max size
        if len(cache) > maxsize:
            cache.popitem(last=False)
      
        return result
  
    return memoized_function

3. Mutable Arguments Causing Incorrect Cache Hits

When arguments include mutable objects (lists, dictionaries), changes to these objects after caching can lead to incorrect results:

Problem Example:

def sum_list(lst):
    return sum(lst)

memoized_sum = memoize(sum_list)
my_list = [1, 2, 3]
print(memoized_sum(my_list))  # 6 (cached)
my_list.append(4)  # Modify the list
print(memoized_sum(my_list))  # Still returns 6 (incorrect!)

Solution: Create deep copies of mutable arguments or use immutable representations:

import copy
import json

def memoize(fn: Callable[..., Any]) -> Callable[..., Any]:
    cache = {}
  
    def memoized_function(*args: Any) -> Any:
        # Create immutable representation of arguments
        immutable_args = []
        for arg in args:
            if isinstance(arg, (list, dict)):
                # Convert to immutable representation
                immutable_args.append(json.dumps(arg, sort_keys=True))
            else:
                immutable_args.append(arg)
      
        key = tuple(immutable_args)
      
        if key in cache:
            return cache[key]
      
        result = fn(*args)
        cache[key] = result
        return result
  
    return memoized_function

These solutions address the major pitfalls while maintaining the core memoization functionality and ensuring correctness across different use cases.