Tricky Microsoft interview question that Reddit got so wrong

1 point

17 years ago

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