Discussion on: How To Solve Missing Number Problem In Java, An Amazon Interview Question

[peerreynders]

In principle reduce can be viewed as a shorthand for recursion over a collection

const xorKVs = (values, key, n) =>
  key >= 0 ? xorKVs(values, key - 1, n ^ key ^ values[key]) : n;
const xorKVAll = (values) => xorKVs(values, values.length - 1, values.length);

console.log(xorKVAll([9, 6, 4, 2, 3, 5, 7, 0, 1])); // 8

while recursion is immutable iteration

console.log(xorKVAll([9, 6, 4, 2, 3, 5, 7, 0, 1])); // 8

function xorKVAll(values) {
  let n = values.length; // from range of values [0, n]
  for (let key = n - 1; key >= 0; key -= 1) n ^= key ^ values[key];

  return n;
}

While some people using reduce() (foldl()) may not be comfortable with the recursive alternative, they'll more than likely be capable of formulating the iterative version.

I suspect the question has less to do with the actual solution implementation but more with determining whether the candidate

• is aware of the properties of bitwise XOR operation
• has the insight that the keys/indices (and the length) of the array provide a "free" master set of values that should be in the array - creating the opportunity to leverage the properties of bitwise XOR in the first place.

Though I also suspect that the minority of candidates actually arrive at this from first principles but only hit on this because of interview preparation.

So really what is largely being assessed is

• whether the candidate could be bothered to prepare for the interview
• whether the candidate happened upon this exact problem during preparation
• whether the candidate could recall enough to reconstruct the solution

So being asked to tweak the solution and being able to adapt is really the core of the interview.

[Gopi Gorantala]

Thanks for the notes 🤩, they’re helpful to me! ☺️

You’re right about the assessments of candidates. It’s the thought process and different approaches the candidates think of… that’s what interviewers look for!!