Is this modern programming interview challenge's solution unreliable?

Question

So I failed the programming interview question that is like

"Given an array of ints 1, 2, ..., n with one of them missing, find the missing one."

The interviewer said the correct answer is to sum the numbers and subtract the sum from n(n+1)/2, that is, apply the formula https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

and said that any computer science student would've done this. My solution was like

char takenSpots [] = n*malloc(sizeof(char)); 
for (int k = 0; k < n; ++k) takenSpots[arr[k]-1] = 'x';
for (int k = 0; k < n; ++k) if (takenSpots[k] != 'x') return (k+1);

which isn't as "cool" as the summation solution that I confess I would've never thought to try.

First of all, isn't there danger of overflow using the summation method? I mean, what if arr contains ~((int)0) and ~((int)0) - 1 ? Then won't arr[0] + arr[1] + ... + arr[n-1] overflow? Or will the solution still work since 1 + 2 + ... + n overflows too?

Answer 1

Indeed, the solution the interviewer proposed would suffer from overflow. In fact, there is a better solution that does not suffer from overflow, which the interviewer might have followed up with if you had suggested the summation one.

The better solution is much less intuitive, but it's pretty well-known nowadays, as far as I know.

It relies on the following:

x xor y = y xor x
x xor 0 = x
x xor x = 0

So the better solution involves computing the xor of all the given numbers and then xoring that with the xor of all numbers from 1 to n. Those that appear in your array will cancel out with those from 1 to n. The one that was missing will remain.

As for how to think about such solutions, there's no recipe. You just have to be familiar with such challenge / interview questions and have some training in computer science and math.

Don't feel too bad about not getting it. I almost certainly would not have gotten the summation solution in an interview setting if I hadn't seen the problem before after finishing college (I might have figured it out eventually in my own time) and I definitely would not have come up with the xor solution without seeing it first. These kind of questions are pretty much hit or miss. And if it's a hit, they'll probably ask something else until you don't know the answer.

They don't do this to catch you off guard. They do it to see how you think about it, usually: can you come up with a naive solution (you did), can you tell what's wrong with it? can you think of ways to improve it, maybe with some nudging in the right direction? can you explain how you'd go about researching a better solution? The thought process can be more important than the solution.

If all the interviewer said was that your solution is bad and you should have known the better solution (I don't think there's a checklist of things you must absolutely know about X after finishing a major in X), you should look for a better place to work.

Answer 2

If you use unsigned integers, the method using the formula will still work because C standard specifies modular arithmetic for multiplication and addition. With n-bit integers you are guaranteed to get the correct result modulo 2^n, and since you know the result must be in range 0-2^n you know it must be correct.