Tricky Microsoft interview question that Reddit got so wrong

1 points by ovi256 16y ago ↗ HN

Here is the question: http://mindcipher.net/puzzle/166-microsoft-interview-question-count-it-out

And here is the Reddit thread: http://www.reddit.com/r/programming/comments/95hl2/tricky_microsoft_interview_question/

The obvious solution I see is O(N) in both space and time: just go through the numbers and mark the ones you see in an array. The one that is left unmarked is the missing number.

Reddit commentors propose O(nlogn) complex solutions. Modified quicksort ? Map reduce ? Oh common.

1 comment

[ 2.6 ms ] story [ 11.4 ms ] thread

ErrantX 16y ago ↗

There is a horrifically easy way ofc.

Sum the array then subtract from 5050 (the sum of 1 - 100). There is your missing number.

EDIT: I didnt read the reddit thread before posting this... why would you say that is the wrong approach? (or, bleh. your being ironic.. sorry ;) too early in the morning).