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
The easy part is that we know that if x and y are the missing and duplicate indices form vector V then we have:
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 ;)