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

Number: 2731

Difficulty: Medium

Paid? No

Companies: Apple

Problem Description

Implement a higher‐order function memoize(fn) that takes a function fn and returns a memoized version of it. The memoized function caches the result for every unique set of input arguments so that repeated calls with the same arguments do not invoke fn again. Note that the cache key must respect argument order (for example, for the sum function, the call with (2,3) is distinct from (3,2) if the function treats the order as significant).

Key Insights

  • Cache previously computed results using a data structure keyed by the function arguments.
  • Ensure the key uniquely represents the argument order; simple tuple (or equivalent) suffices.
  • Use closures (or object state) to maintain both the cache and a call count tracking actual function invocations.
  • Expose a method (getCallCount) on the memoized function to report the number of times the original function was actually called.
  • The memoized version works for functions that might take one or more parameters.

Space and Time Complexity

Time Complexity: O(1) average for each call assuming efficient hashing of arguments. Space Complexity: O(n) for caching n distinct input combinations.

Solution

We use a hash-based cache (a dictionary or map) to store results for every unique set of arguments. Upon each call, we check if the key (constructed from the input arguments) exists in the cache. If not, we increment a counter, call the original function, store the result in the cache, and return it. Otherwise, we return the cached result. The memoized function is augmented with a getCallCount method to report the number of actual calls made to the original function.

Code Solutions

# Define a function 'memoize' that takes a function 'fn' and returns a memoized version.
def memoize(fn):
    cache = {}                  # Dictionary to cache computed values
    call_count = 0              # Counter for real function calls

    # The wrapper function handles any number of arguments.
    def wrapper(*args):
        nonlocal call_count
        # Use the arguments tuple as a key (order sensitive).
        if args not in cache:
            call_count += 1     # Increment call count when computing new result
            cache[args] = fn(*args)
        return cache[args]
    
    # Expose the getCallCount method on the memoized function.
    wrapper.getCallCount = lambda: call_count
    return wrapper

# Example usage:
# def sum_func(a, b): return a + b
# memoizedSum = memoize(sum_func)
# print(memoizedSum(2, 2))
# print(memoizedSum(2, 2))
# print(memoizedSum.getCallCount())
← Back to All Questions