Medium

Commutative Memoization

Prompt

In previous memoize challenges, you learned how to cache results based on exact arguments. But there is a special optimization we can make for commutative functions.

A commutative function is one where the order of arguments does not matter. The classic example is addition: 1 + 22 is exactly the same as 22 + 1.

In this challenge, your task is to implement a sum(a, b) function with an integrated memoization cache. But there is a catch: since addition is commutative, your memoization logic should be smart enough to recognize this and return the cached result for sum(22, 1) if sum(1, 22) has already been computed.

Requirements:

• Print exactly "It is memoized result" for cache hits.
• Print exactly "It is fresh calculated result" for fresh computations.

Playground

Solution

Explanation

I will walk you through this interview challenge asked at Adobe. We will go through the solution step by step, where candidates usually go wrong, and tips to do well.

Before we start coding, let's understand what this question is really asking. In normal memoization, sum(1, 22) and sum(22, 1) would be treated as two separate calls because the arguments are in a different order. But since addition is commutative (1 + 22 is the same as 22 + 1), we should be smart about it and return the cached result even when the arguments are flipped.

Now, let's start solving.

Step 1: Setting up the cache

We need a place to store our results. We will use a simple object called memoizedResults for this.

let memoizedResults = {};

Step 2: Building the cache key

The first thing we need to figure out is how to create a cache key from our two arguments. The simplest approach is to combine a and b into a string like "1-22".

const key = `${a}-${b}`;

This works for exact repeated calls like sum(1, 22) followed by another sum(1, 22). But it does not handle the commutative case. If we call sum(22, 1), the key becomes "22-1", which is a completely different string from "1-22". So we miss the cache.

Step 3: Handling both orderings

To solve this, we generate both possible key combinations and check if either one exists in the cache.

const keyComb = [`${a}-${b}`, `${b}-${a}`];

Now when sum(22, 1) is called, we check for both "22-1" and "1-22". Since "1-22" was stored by the earlier sum(1, 22) call, we get a cache hit.

Step 4: Putting it all together

let memoizedResults = {};

function sum(a, b) {
  const keyComb = [`${a}-${b}`, `${b}-${a}`];

  if (
    memoizedResults[keyComb[0]] ||
    memoizedResults[keyComb[1]]
  ) {
    console.log('It is memoized result');
    return (
      memoizedResults[keyComb[0]] ||
      memoizedResults[keyComb[1]]
    );
  }

  console.log('It is fresh calculated result');
  const result = a + b;
  memoizedResults[`${a}-${b}`] = result;
  return result;
}

We only store the result under one key ("a-b"), not both. There is no need to store it twice because our lookup already checks both combinations.

Walking through the example

Let's trace through a couple of calls to make sure this makes sense.

sum(1, 22) — First call

We generate keys "1-22" and "22-1". Cache is empty, so both lookups return undefined. We calculate 1 + 22 = 23, store it as memoizedResults["1-22"] = 23, and log "It is fresh calculated result".

sum(22, 1) — Commutative call

We generate keys "22-1" and "1-22". We check memoizedResults["22-1"] which is undefined. Then we check memoizedResults["1-22"] which is 23. Cache hit! We log "It is memoized result" and return 23 without doing any calculation.

sum(22, 3) — New arguments

We generate keys "22-3" and "3-22". Neither exists in the cache. We calculate 22 + 3 = 25, store it, and log "It is fresh calculated result".