DEV Community

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

Collapse
 
ggorantala profile image
Gopi Gorantala • Edited

This is cool.. I love the single line snippets 😍.. but in coding interviews tech giants and fewer companies expect you to write an algorithm instead re-use an existing built-in function/methods.

Collapse
 
jonrandy profile image
Jon Randy πŸŽ–οΈ

I somehow don't think you're going to be penalised for using stuff like map, filter, and reduce - these are pretty much cornerstones of functional programming

Thread Thread
 
jonrandy profile image
Jon Randy πŸŽ–οΈ • Edited

I would actually look down upon a candidate reinventing any of the above methods, as the resulting code would likely be less efficient - and they've also demonstrated a lack of knowledge of the language.

The key here is the XOR stuff... the loops and other things are just fluff.

Thread Thread
 
ggorantala profile image
Gopi Gorantala

Yup.. the key is xor. Functional programming is quite fun. I got interviewed at Amazon last December, I was asked to implement a longest connected nodes for a binary tree.. it was easy and I did it using iteration first, she asked me to go for recursion and I did. next, she asked me to try with another approach. So the point is, if you implement the solution one way, they tweak it ask you for some other cases, what if that and what if this happens on the writtten algorithm. The point is, we need to train our brain for all possible solutions and optimize them πŸ˜‰

Collapse
 
peerreynders profile image
peerreynders • Edited

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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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.

Thread Thread
 
ggorantala profile image
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!!