News for hackers. Stuff that matters.
Re:Want a job working on mongoDB? Your first online intervie... by yuvadam on Saturday April 23, 2011 @03:33PM (#2477367)
Here's a sketchy description for a possible solution.

The easy part is that we know that if x and y are the missing and duplicate indices form vector V then we have:

    |x-y| = |sum(V) - (N*(N-1))/2|
So far - constant space and linear time. From here it's either cleverly (linearly!) scanning the vector or similarly concluding something else about the vector and crossing that info with what we have ;)
Re:Want a job working on mongoDB? Your first online intervie... by makmanalp on Saturday April 23, 2011 @03:54PM (#2477421)
This is close to the solution I had in mind, however summing lots of 64 bit integers probably yields a huge number that overflows, so some Bigints (which are comparatively slow) or clever hackery might be required to mitigate that.
Re:Want a job working on mongoDB? Your first online intervie... by antics on Saturday April 23, 2011 @04:16PM (#2477498)
That's not (EDIT:) space-constant.
Re:Want a job working on mongoDB? Your first online intervie... by pdhborges on Saturday April 23, 2011 @04:39PM (#2477543)
The sum is guaranteed to fit into 128 bits
Re:Want a job working on mongoDB? Your first online intervie... by slay2k on Saturday April 23, 2011 @03:59PM (#2477443)
Did you mean (N*(N+1))/2 ?
Re:Want a job working on mongoDB? Your first online intervie... by yuvadam on Sunday April 24, 2011 @11:10AM (#2478958)
Nope :)