Problem Description
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. You can assume there are three possible input functions: sum, fib, and factorial.
Key Insights
- A memoized function stores results of expensive function calls and returns the cached result when the same inputs occur again.
- The sum function requires separate caching for different argument orders (e.g., (a, b) and (b, a) should be treated independently).
- The fib and factorial functions are recursive and can benefit significantly from memoization to avoid redundant calculations.
- The solution needs to handle a large number of function calls efficiently.
Space and Time Complexity
Time Complexity: O(n) for each function call, where n is the size of inputs. For the memoized functions, the average time complexity can be reduced significantly due to caching. Space Complexity: O(n) for the cache to store results of function calls.
Solution
To solve the problem, we will create a memoization function that wraps the original function and maintains a cache. We will use a dictionary (or map) to store the results of previously computed values. For the sum function, we will use a tuple of the arguments as the key. For fib and factorial, we will use the integer input directly. We will also maintain a call count to track how many times the original function has been invoked.