An array of 100 elements contains values ranging from 0 to 100, inclusive. Determine which value is missing.

Question

Anonymous · Accepted Answer

Ok here's my algorithm. 
Loop though the array, keep updating the sum of indices (indSum += i) and the sum of values at these indices (valSum += a[i]). 
once the loop ends, add i (ie 100) to indSum.
Now ( indSum - valSum ) will give you the answer. TIme Complexity O(n)

Jason Mitchell · Answer

The last comment (answer) is spot on.  But, I would suggest using the summation formula to get indSum rather than doing it in the loop.  It would show the interviewer you have some knowledge of math formulas as well.  You can sum up any range by simple doing: ((i*i) + i) / 2 

For example: if you wanted to sum up all digits between  0 to 10 (inclusive) you could do ((10*10)+10)/2 which gives you 55.

In pseudo-code:
valSum = 0
for array_value in array:
  valSum += array_value
print "Missing Number: " + (((i*i) + i ) / 2) - valSum

Sigiloso · Answer

This was a software question but only pseudo-code was needed. Brute force method works but opportunity is also given for a more elegant solution. Not a very difficult question at all - thought process is most important.

National Instruments

Pergunta de entrevista da empresa National Instruments

Respostas da entrevista

Empresas seguidas

Buscas de vagas