We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Memoize II

Number: 2744

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given any function fn with arbitrary arguments, return a memoized version of that function. A memoized function caches its results so that if it is ever called with the same inputs (using strict equality – === in JavaScript), it returns the cached result instead of recomputing it. Note that even if two objects look the same, they are only considered identical if they reference the same instance.

Key Insights

  • We must cache each unique set of input arguments to avoid re-computation.
  • In JavaScript (and similar languages), inputs are compared using strict equality (===); therefore, objects with the same structure but different references will not be treated as identical.
  • A nested Map (or trie) structure is useful when dealing with functions with multiple arguments. Each argument leads to a deeper Map until the final node holds the cached result.
  • When implementing in languages that do not natively support identity based hashing (like Python for mutable types), custom wrappers or strategies may be needed.

Space and Time Complexity

Time Complexity: O(n) per memoized function call, where n is the number of arguments (the lookup traverses a nested structure proportional to the number of arguments).
Space Complexity: O(m) where m is the number of unique combinations of arguments encountered.

Solution

We implement a memoization wrapper that caches results based on the identity of its arguments. The typical approach is to use a nested hashmap (or Map) where each level corresponds to one argument. For example, in JavaScript a top-level Map is created; for every argument in the call, we descend into the next-level Map. If a path doesn’t exist, we create it. At the final level, we either return the cached result or compute, cache, and then return the value by calling fn.

Important considerations:

  • For languages like JavaScript, using a Symbol as the key for storing the result prevents any collisions with actual input values.
  • For Python, since some objects are unhashable or may not compare using identity by default, one efficient strategy is to wrap arguments in a helper object that uses id() for hashing and equality.
  • In statically typed languages like C++ and Java, care must be taken when handling generic types. A nested mapping solution is one common approach.

Code Solutions

# Python solution using an identity wrapper for memoization.
class IdentityWrapper:
    def __init__(self, obj):
        self.obj = obj
    def __hash__(self):
        # Use the unique id of the object as hash
        return id(self.obj)
    def __eq__(self, other):
        # Equality is based on reference (identity)
        return self.obj is other.obj

def memoize(fn):
    cache = {}
    def memoized_fn(*args):
        # Wrap arguments in IdentityWrapper to enforce identity comparison.
        key = tuple(IdentityWrapper(arg) for arg in args)
        if key in cache:
            return cache[key]
        result = fn(*args)
        cache[key] = result
        return result
    return memoized_fn

# Example usage:
if __name__ == "__main__":
    def add(a, b):
        return a + b
    memoizedAdd = memoize(add)
    print(memoizedAdd(2, 2))  # First call, computes 4
    print(memoizedAdd(2, 2))  # Second call, cached result 4
← Back to All Questions