Is this the wrong solution for a modern interview interview?

Question

So, I could not answer the question related to programming, which is similar to

"Given an array of integers 1, 2, ..., n, one of which is missing, find the missing one."

The interviewer said that the correct answer is to sum the numbers and subtract the sum from n (n + 1) / 2, i.e. 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 do that. My decision 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, which, I admit, I would never have thought of trying.

First of all, is there a danger of overflow using the summation method? I mean, what if arr contains ~((int)0) and ~((int)0) - 1 ? Then there will be no arr[0] + arr[1] + ... + arr[n-1] overflows? Or will the solution work even after overflow 1 + 2 + ... + n ?

Answer 1

Indeed, the solution proposed by the interviewer will suffer from overflow. In fact, there is a better solution that does not suffer from overflow, which might have followed the interviewer if you suggested summing.

The best solution is much less intuitive, but as far as I know, it is pretty well known these days.

He relies on the following:

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

Thus, the best solution involves computing xor of all given numbers, and then xoring with xor of all numbers from 1 to n . Those that appear in your array will be canceled with tags from 1 to n . One that was absent will remain.

As for how to think about such solutions, there is no recipe. You just need to be familiar with such questions about problems / interviews and have some background in computer science and math.

Do not feel too bad not to get it. I almost certainly wouldn’t get the summation solution in setting up the interview if I hadn’t seen the problem before graduating from college (maybe I understood this at the time), and I definitely wouldn’t come up with an xor solution without seeing it in the first place. These questions are pretty much hit or missed. And if it's a blow, they will probably ask for something else until you know the answer.

They do not do this to catch you. They do this to see how you think about it, as a rule: you can come up with a naive solution (you made), can you say what is wrong with him? can you figure out how to improve it, maybe with a little push in the right direction? can you explain how you are going to research the best solution? The thought process may be more important than the decision.

If the whole interviewer said that your decision is bad and you should have the best, best solution (I don’t think there is a checklist of things that you should absolutely know about X after finishing major in X), you should look for the best place to work .

Answer 2

If you use unsigned integers, the method using the formula will still work, because the 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 that the result must be in the range 0-2 ^ n, you know that it must be correct.

Answer 3

Almost any student in the field of computer science had to solve this problem. Its solution works in O (n) time and O (1) space, your solution works in O (n) time with a larger constant and O (n) space. Therefore, it is not surprising that his decision is better.

Regarding overflow. With almost any problem, you can find an input that will overflow. If you hear the “how to add two numbers” problem, and then you see the solution a + b, it will also overflow. Or print the number that you get from input is also full.

A good idea during an interview is to ask what contribution you expect. And when you propose a solution, you have to say what problems you expect. My adding two numbers will work if the sum is less than X. If you want better, use large int arithmetic.

PS did you think that you might not have enough memory for the malloc operation when the number n is too large?

Answer 4

This is a mathematical question, not a programming question. I'm not sure that majors in the field of computer engineering take a math course that includes a series, and if not, then it is somewhat random if the programmer has encountered this before. Other series exist, such as the power series as part of many http://en.wikipedia.org/wiki/List_of_mathematical_series .

At what point do these questions cease to be programming questions and mathematical questions?