6
\$\begingroup\$

I recently was in an interview where I was asked to implement a snippet that finds the matching key:value pair among two JavaScript arrays in which each member is an object:

var a = [{color:'blue'},{color:'green'}, {color:'brown'}, {color:'black'}]
var b = [{color:'white'},{color:'yellow'}, {color:'black'}, {color:'blue'}]
var expectedOutput = [{color:'blue'}, {color:'black'}]

Here's my implementation:

var a = [{color:'blue'},{color:'green'}, {color:'brown'}, {color:'black'}]
var b = [{color:'white'},{color:'yellow'}, {color:'black'}, {color:'blue'}]
var expectedOutput = [];
for(var i=0; i<a.length; i++){
	if(b[i].hasOwnProperty('color') && a[i].color===b[i].color){
		expectedOutput.push(a[i]);
	}
}

document.write(expectedOutput.toString());

In the interview, I communicated that using .hasOwnProperty() provides \$O(1)\$ lookup for keys (but not for values) from array b, and unfortunately, I wasn't able to fully implement this as my mind wandered across other possibilities there might be, not to mention the pressure.

I believe this still has \$O(n^2)\$ complexity as it simply checks the existence of child .color key as well as a supplementary check against values being equivalent. All in all, I suspect the interviewer was pointing me into this implementation for \$O(n)\$ complexity.

Do you think otherwise? If you do, could you kindly explain why and how? If my question is unclear, how would you solve it in \$O(n)\$ time in JavaScript?

\$\endgroup\$
2
  • \$\begingroup\$ Your expected output doesn't make sense to me. Your implementation computes an empty array for the given a and b array. Could you clarify? Also, is the search limited to the color property or any key value pair? \$\endgroup\$ – le_m May 6 '17 at 1:38
  • 1
    \$\begingroup\$ @le_m code should evaluate now as i have added the definition of arrays a and b. Search is limited to matching values. \$\endgroup\$ – Still Questioning May 6 '17 at 1:49
2
\$\begingroup\$

I would say that hasOwnProperty is not necessary in this case. If you want to make it O(n) you probably have to first convert one of the arrays into a hash of colors so that you can improve lookup speed. Something like:

var a = [{color:'blue'},{color:'green'}, {color:'brown'}, {color:'black'}];
var b = [{color:'white'},{color:'yellow'}, {color:'black'}, {color:'blue'}];
var aColors = a.reduce( function(obj, hash) { obj[hash.color] = true; return obj }, {} );

var expectedOutput = [];
for(var i=0; i<b.length; i++) {
	if (aColors[ b[i].color ] )
		expectedOutput.push( b[i] );
}

console.log(expectedOutput);

\$\endgroup\$
1
  • \$\begingroup\$ Conversion to hash is exactly what i was looking for! Thanks @marc-rohloff \$\endgroup\$ – Still Questioning May 6 '17 at 7:41
1
\$\begingroup\$

First, a few notes on your implementation:

if (b[i].hasOwnProperty('color') && a[i].color === b[i].color) {
  expectedOutput.push(a[i]);
}
  • It seems reasonable to constrain input elements to always have a color property and drop the hasOwnProperty check.

  • Pushing the results to a new output array and keeping the expectedOutput intact as given by the interviewer allows us to compare your output to the expected output later on.

Now, completing your attempted implementation we would come up with:

for (let i = 0; i < a.length; i++) {
  for (let j = 0; j < b.length; j++) {
      if (a[i].color === b[j].color) {
          output.push(a[i]);
      }
  }
}

This implementation works and is easy to validate. It is also the most performant solution for small input arrays. But it has drawbacks:

  • The runtime complexity is clearly O(n²) and thus slow for large inputs
  • It is not very descriptive, as it directly operates on array indices

Let's tackle the given problem on a more abstract level. We are given two collections of elements as inputs. The order of elements doesn't matter. And we want to find common elements. In other terms, we wand to find the set intersection:

let colors = new Set(a.map(obj => obj.color));
let output = b.filter(obj => colors.has(obj.color));

All popular JavaScript engines implement sets and maps via hash maps with nearly linear insertion and lookup times. Thus, above solution has a runtime complexity of O(n) for most inputs of length n.

You could further abstract away how you determine the identity of set elements by introducing an identity function and coming up with this reusable intersect implementation:

// Find intersection of arrays a, b by mapping elements to identity id:
function intersect(a, b, id) {
  let set = new Set(a.map(id));
  return b.filter(el => set.has(id(el)));
}

// Example:
let a = [{color:'blue'},{color:'green'}, {color:'brown'}, {color:'black'}];
let b = [{color:'white'},{color:'yellow'}, {color:'black'}, {color:'blue'}];
console.log(intersect(a, b, el => el.color));

\$\endgroup\$
1
  • \$\begingroup\$ @le-m thank you for well described solution and use of ES6 in the mix! \$\endgroup\$ – Still Questioning May 6 '17 at 19:14
0
\$\begingroup\$

The solution you provided does appear to be \$O(n)\$, but I agree that it is not correct.

I don't know of a way that you can compare elements in 2 separate arrays (lists, key/value pairs, etc) without an \$O(n2)\$ solution. It all comes down to traversing the first list element by element and then searching the second list for the same element value.

\$\endgroup\$
1
  • \$\begingroup\$ so the interviewer was pointing out that i should convert the array into an object for the fact that JavaScript objects implement hash tables, therefore, providing an ability check existence of key:value pair in \$O(n)\$ time. \$\endgroup\$ – Still Questioning May 6 '17 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.