Build a function memoizer [Part-1]

#javascript #memo #interview

The Problem Statement

Build a function which takes an input function and returns a new function which will memoize/cache the results.

I was asked this question in an interview and felt it's a good problem to solve and learn from. We'll focus on building something "good enough".

Rather than trying to solve for all the scenario's in one shot, it is better go incrementally especially during an interview. A solution that works for few scenarios is better than one which attempts to solve everything but doesn't run.

Let's start with an minimum viable option, assume a simple scenario: A function which performs some complex math operations on a set of input numbers

Breaking down the problem

We have to write a function which returns a function with caching
Where do we cache? In a closure
How do we cache? We need a unique key, we can form a key from all the input parameters. Since it's only numbers we can just join the values by '-'.

First step is to write a frame for our function


// takes and input function 
// returns a function wrapped in a closure
function memoizer(fn) {
  // capture all the input args
  return (...args) => {
    // call input function with args
    return fn(...args);
  };
}

// a test function
function add(a, b) {
  return a + b;
}

// call our memoizer
const memoAdd = memoizer(add);

console.log(memoAdd(1, 2)); // output: 3
console.log(memoAdd(2, 4)); // output: 6

Next, a cache key maker

const generateCacheKey = (args) => args.join("-");

console.log(generateCacheKey([1, 2, 8, 44]));
// output: 1-2-8-44

Next, we add add caching. Check if the key is in cache, if found then return from cache, otherwise call the function and cache result before returning it.

// build cache key
const generateCacheKey = (args) => args.join("-");

function memoizer(fn) {
  // cache store
  const resultsCache = {};

  // capture all the input args
  return (...args) => {
    const cacheKey = generateCacheKey(args);

    if (!(cacheKey in resultsCache)) {
      // cached value not found, call fn and cache result
      resultsCache[cacheKey] = fn(...args);
    }

    // return result from cache;
    return resultsCache[cacheKey];
  };
}

// we can use a counter to test if our cache is working
let count = 0;
function add(a, b) {
  count++;
  return a + b;
}

const memoAdd = memoizer(add);

const prettyPrint = (result) =>
  console.log(`result: ${result}, count: ${count}`);

prettyPrint(memoAdd(1, 2)); // result: 3, count: 1
prettyPrint(memoAdd(2, 4)); // result: 6, count: 2
prettyPrint(memoAdd(2, 4)); // result: 6, count: 2
prettyPrint(memoAdd(22, 33, 44)); // result: 55, count: 3
prettyPrint(memoAdd(1, 2)); // result: 3, count: 3

The cache is working, the second time we called with args (2,4), the count remained the same proving that the value was returned from cache.

Now that we have a basic working implementation, it's time to list down the next set of features that we have to add and prioritise.

support for complex input params like Objects and Arrays
support for caching asynchronous functions like api calls
a clear cache option
support for a max cache limit, otherwise our cache will keep growing with variations in input
option to expire cached values based on time

I've listen these in order that I feel will add most value to the solution (if in an interview)

The following parts of this series will solve the listed items one by one.

Photo by Tim Mossholder on Unsplash