I ran across a couple of nice interview questions and an interesting story over at Tanya Khovanova’s Math Blog. The two questions are:
- Given a list of integers from 1 to n but with one of the integers missing, write an efficient algorithm for finding the missing integer.
- Given a list of integers from 1 to n but with one of the integers missing and another integer repeated, write an efficient algorithm for finding the missing and repeated integers.
In both problems the numbers in the list are in no particular order.
So the challenge is to write the two algorithms in Emacs Lisp. The interviewer expected a O(n log n) algorithm for time for the second problem. Can you do better?
Don’t go over to Khnovanova’s blog until you have solved the problems because there are spoilers in the comments. After you solve the problem, though, be sure to read her story about “hiring the smartest people in the world.”