CODEWITHSUNDEEP
javascriptcachingmemoization
Dan Zuzevich
Dan Zuzevich

Reputation: 3831

Memoizing Objects With Same Keys, But Different Order

I had an interview the other day, and was asked to write my own memoize function that accepts a function, and returns a wrapped version of it. I've used functions that utilize memoization before, but never took the time to look into how they work internally. Needless to say, I didn't get the job, haha.

One interesting requirement was that for arguments of type object, the function should treat them as the same argument if the keys are the same, but are in different order:

For example:

const one = {
   a: 1,
   b: 2,
   c: 3
}

const two = {
  c: 3,
  a: 1,
  b: 2
}

would be counted as the same argument. Here's my memoize function, and it's implementation:

const memoize = fn => {
  const cache = {};

  return (...args) => {
    const key = JSON.stringify(args);

    if (!cache.hasOwnProperty(key)) {
      cache[key] = fn(...args);
    }

    return cache[key];
  };
}

const stringifyObj = (obj) => {
   console.log(obj)
   return JSON.stringify(obj)
}

const myMemo = memoize(stringifyObj)

const a = myMemo({ hello: "world", goodnight: "moon" })
const b = myMemo({ goodnight: "moon", hello: "world" })

Executing myMemo twice ends up in both objects being logged to the console. However, if the memoize function was setup to properly handle objects with the same keys in different orders, I would expect the console.log to only execute once, printing { hello: "world", goodnight: "moon" }

In this example I am using just one object as an argument, but in reality the memoize function is supposed to support n amount of arguments of all different types. It would be awesome if someone could explain how to deal with the problem for any amount of arguments, but its not required. Posting a solution that solves the same keys, different order problem for just one object argument is cool too.

Upvotes: 3

Views: 661

Answers (1)

Dan Zuzevich
Dan Zuzevich

Reputation: 3831

I used Robert's recommendation of sorting the objects by key. My implementation seems to work for multiple arguments of any type, including multiple objects. I don't think the check to see if an arg is an object is bulletproof, but it works good enough.

const memoize = (fn) => {
  const cache = {};

  return (...args) => {
    let i = 0;

    for (const arg of args) {
      if (
        typeof arg === "object" &&
        arg.constructor === Object &&
        arg !== null
      ) {
        const sortObject = (o) =>
          Object.keys(o)
          .sort()
          .reduce(
            (acc, key) => ({
              ...acc,
              [key]: o[key],
            }), {}
          );
        args[i] = sortObject(arg);
      }
      i++;
    }

    const key = JSON.stringify(args);

    if (!cache.hasOwnProperty(key)) {
      cache[key] = fn(...args);
    }

    return cache[key];
  };
};

Putting it in a text editor and testing out it should result in the following:

function x(str, obj, num, obj) {
  console.log("hola");
}

const myMemo = memoize(x);
myMemo("hey", { a: 1, b: 2, c: 3 }, 24, { b: 2, c: 3, a: 1 }); // log
myMemo("bye", { a: 1, b: 2, c: 3 }, 24, { b: 2, c: 3, a: 1 }); // log
myMemo("hey", { a: 1, b: 2, c: 3 }, 24, { b: 2, c: 3, a: 1 }); // no log
myMemo("hey", { a: 1, b: 2, c: 3 }, 24, { b: 2, c: 3, a: 1 }); // no log
myMemo("bye", { a: 1, b: 2, z: 3 }, 24, { b: 2, z: 3, a: 1 }); // log
myMemo("bye", { a: 1, b: 2, z: 3 }, 24, { b: 2, z: 3, a: 1 }); // no log

Upvotes: 0

Related Questions