Want a job working on mongoDB? Your first online interview is in this post
I like smart programmers.
So, I thought I’d put out a programming puzzle. If you an solve it, you are well on your way to a very cool job. If you can’t solve it, send it to a smart friend who can. Even if you don’t want a job, I promise you’ll enjoy the solution when you find it.
Here’s the puzzle:
You’re given an array of N 64 bit integers. N may be very large. You know that every integer 1-N appears once in the array, except there is one integer missing and one integer duplicated.
I’d like a linear time algorithm to find the missing and duplicated numbers. Further, your algorithm should run in small constant space and leave the array untouched.
PS I love smart people in other jobs too; while I think this problem will appeal mostly to programmers, 10gen is a company where solving a problem like this helps you get a job in marketing, finance, or any other area that fits your skills. Send me a solution and tell me what job you want to interview for!
NOTE 4/24 4am: I have caught up with all the responses but plan to take Sunday off and spend it with my family. Thanks for making a job at 10gen more popular than baby tips from Elton John today.