Memoize II - Practice Coding Problems

Memoize II - Problem

JavaScript Hard

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.

The function fn can be any function and there are no constraints on what type of values it accepts. Inputs are considered identical if they are === to each other.

Input & Output

Example 1 — Basic Function Memoization

$ Input: fn = (a, b) => a + b

› Output: memoized function that caches results

💡 Note: First call fn(2,3) computes 5 and caches it. Second call fn(2,3) returns cached 5 without computation.

Example 2 — Factorial Memoization

$ Input: fn = (n) => n <= 1 ? 1 : n * fn(n-1)

› Output: memoized factorial function

💡 Note: Recursive calls get memoized. factorial(5) caches results for 1,2,3,4,5. Later calls reuse cached values.

Example 3 — Object Arguments

$ Input: fn = (obj) => obj.x + obj.y

› Output: memoized function handling objects

💡 Note: Same object reference returns cached result. Different objects with same values are treated as different inputs.

Constraints

1 ≤ inputs.length ≤ 10⁵
0 ≤ inputs.flat().length ≤ 10⁵
inputs[i][j] != NaN

Visualization

Tap to expand

Understanding the Visualization

Input

Original function that may be expensive to compute

Process

Wrap with caching mechanism that stores results

Output

Memoized function that avoids redundant computations

Key Takeaway

🎯 Key Insight: Cache function results by using arguments as keys to avoid redundant computations

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is to cache function results using arguments as keys. Best approach uses Map/WeakMap for efficient caching with proper memory management. Time: O(1), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Map with Argument-based Keys	O(1)	O(n)	Use Map with custom key generation for better argument handling
Basic Cache with JSON Stringify	O(1)	O(n)	Use JSON.stringify to create cache keys from function arguments
WeakMap with Object Reference Caching	O(1)	O(n)	Use WeakMap for object arguments and combined caching strategy

Map with Argument-based Keys — Algorithm Steps

Create a Map for caching
Generate custom key from arguments
Use Map.has() for existence check
Store and return results

Visualization

Tap to expand

Step-by-Step Walkthrough

Custom Key

Generate key by joining arguments with delimiter

Map Lookup

Use Map.has() for efficient existence check

Cache Result

Store in Map for future lookups

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CACHE_SIZE 1000

typedef struct CacheEntry {
    char key[100];
    int value;
    int used;
} CacheEntry;

typedef struct {
    CacheEntry entries[MAX_CACHE_SIZE];
    int (*original_fn)(int, int);
} MemoizedFunction;

int find_cache_entry(MemoizedFunction* memo, const char* key) {
    for (int i = 0; i < MAX_CACHE_SIZE; i++) {
        if (memo->entries[i].used && strcmp(memo->entries[i].key, key) == 0) {
            return i;
        }
    }
    return -1;
}

int memoized_call(MemoizedFunction* memo, int a, int b) {
    char key[100];
    snprintf(key, sizeof(key), "%d|%d", a, b);
    
    int idx = find_cache_entry(memo, key);
    if (idx >= 0) {
        return memo->entries[idx].value;
    }
    
    int result = memo->original_fn(a, b);
    
    // Find empty slot
    for (int i = 0; i < MAX_CACHE_SIZE; i++) {
        if (!memo->entries[i].used) {
            strcpy(memo->entries[i].key, key);
            memo->entries[i].value = result;
            memo->entries[i].used = 1;
            break;
        }
    }
    
    return result;
}

MemoizedFunction* solution(int (*fn)(int, int)) {
    MemoizedFunction* memo = malloc(sizeof(MemoizedFunction));
    memset(memo->entries, 0, sizeof(memo->entries));
    memo->original_fn = fn;
    return memo;
}

int test_sum(int a, int b) {
    return a + b;
}

int main() {
    char fnType[20];
    fgets(fnType, sizeof(fnType), stdin);
    fnType[strcspn(fnType, "\n")] = 0;
    
    MemoizedFunction* memoized = solution(test_sum);
    printf("memoized_function\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Map operations (get/set/has) are constant time

✓ Linear Growth

Space Complexity

O(n)

Map stores results for n unique argument combinations

⚡ Linearithmic Space

24.5K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Map with Argument-based Keys — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler