Want a job working on mongoDB? Your first online interview is in this post

Here's a sketchy description for a possible solution.<p>The easy part is that we know that if x and y are the missing and duplicate indices form vector V then we have:<p><pre><code> |x-y| = |sum(V) - (N*(N-1))/2| </code></pre> 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 ;)

Pretty easy.<p>Compare the sum with the expected sum. Compare the sum of squares with the expected sum of squares.<p>Two equations, just solve them. I wrote the final equations in the blog comments.

This seems to work (in Ruby):<p><pre><code> def find_missing_duplicate(seq) sum = seq.reduce(0, :+) corrsum = (seq.size*(seq.size+1))/2 sumpow = seq.map{|i| i*i}.reduce(0, :+) corrsumpow = (1..seq.size).map{|i| i*i}.reduce(0, :+) diff = sum - corrsum diffpow = sumpow - corrsumpow seq.each do |i| miss = i-diff if (i*i - miss*miss == diffpow) return miss, i end end end </code></pre> And here's some code to test it:<p><pre><code> MIN_N = 2 MAX_N = 1000 (MIN_N..MAX_N).each do |n| duplicate = missing = rand(n)+1 duplicate = rand(n)+1 while duplicate == missing seq = (1..n).map{|i| i} seq[missing-1]=duplicate miss, dup = find_missing_duplicate(seq) if !(miss == missing and dup == duplicate) $stderr.puts "ERROR: expecting #{missing}:#{duplicate} got #{miss}:#{dup}" end end</code></pre>

Here's a solution in Go.<p><pre><code> package main import ( "fmt" ) func main() { // a is the sample array a := []int{0,2, 3, 3} // Reorder values such that a[i] == i when i is not the missing value. for i := 0; i &#60; len(a); i++ { j := a[i] k := a[j] a[j] = j a[i] = k } // Look for a[i] != i for i := 0; i &#60; len(a); i++ { if a[i] != i { fmt.Println("missing:", i, "duplicate:", a[i]) break } } } </code></pre> This is a simple expression of a solution. The code can be improved.

(EDIT: this doesn't work, as lisper pointed out below)<p>I haven't worked out the details or explicitly proven that this will work, but I think the following algorithm should do it:<p>1) Count up the number of even numbers in the list and compare it to the number we'd expect if the list was "right". This will either be correct (in which case both missing and dupe are even, or both are odd), high (the missing one was odd and the duped one was even), or low (the missing one was even and the duped one was odd).<p>If high or low, we've just pinned down the last binary digit of each of the numbers.<p>If even, the digit remains in an unknown state.<p>2) Slice off the last digit.<p>3) Repeat 1) and 2) for all 64 bits.<p>4) Now we have our missing number in the form 001001x1...xx01x (64 bits worth), where the x's represent digits where the missing number's digit matches the duped one.<p>5) We know the difference between the missing and duped numbers because of the triangular sum formula N(N+1)/2. Use that to solve for the xs in the missing number. That equation will <i>not</i> be possible to solve in general, but the statement of the problem here assures us that it will have a solution; further, I'm pretty sure that as long as the duped and missing numbers are not equal, that solution will be unique (EDIT: it's not, and this method doesn't work at all :P ).<p>Maybe I'm missing something, though? Haven't thought this through too deeply...

This is the solution I posted there:<p>Called the missing number m, duplicate d.<p>The main idea is to find m+d and m-d. Then it’s trivial to find m and d.<p>1) Find n XOR d:<p><pre><code> X_array = 1; I_array = 1; for (i=2..N) X_array = X_array XOR A[i]; I_array = I_array XOR i; endfor </code></pre> Then m XOR d = I_array XOR X_array<p>2) Find m – d<p>It will be a little bit more complicated. The idea is to get the sum of (1..N) subtract the sum of our array. But we have to be careful not to over or underflow the result.<p><pre><code> Diff = 0; i = j = 0; // i index I, j index A while (i &#60; N) &#38;&#38; (j &#60; N) if (Diff + i &#60; N-1) Diff = Diff + i; i++; //consume one in I else Diff = Diff – A[j]; j++; // consume one in J endif end </code></pre> // Need some corner case check here to but I will omit<p>3) So we have (m XOR d) and m – d. Also, note that m XOR d is basically m + d without the carry bit so it will be trivial to get m and d.<p>running time : 3 N &#60;- can be squeeze to 2N if merge the two logic<p>space : O(1)

Since the list consists entirely of 64-bit integers, there's a trivial linear-time solution:<p><pre><code> for x in [0..2^64) count = 0 for i in [0..N) count += (array[i] == x) } number[count] = x // 0 &#60;= count &#60;= 2 } print "missing: ", number[0]," duplicate: ", number[2]</code></pre>

One of my friend came up with this solution:<p>m is missing,d is duplicate. I is 1..N, A is input.<p>Step 1: Compute m XOR d by XOR all values of A and I together. let say x = m XOR d. Then x must has at least one 1 bit (or else m == d). Call the bit p. So now we can separate A into two list A0 are those with bit p == 0 and A1 are those with bit p == 1. So we have separated m and d into two different list.<p>Step 2: Iterate through I, maintain two number x0 and x1 as the results of XOR operations of those elements with p bit == 0 and == 1 respectively. Do the same for A to get a0 and a1. Then we know that m is either a0 XOR x0 or a1 XOR x1. One more linear test in A to confirm the missing element m.<p>In the end, the running time can be squeezed into 2 N. space = O(1).

I wonder if a Bloom filter would allow you to (probably) identify the missing value and the duplicated value.<p>Create a Bloom filter on your array, one element at a time. For each element, test whether it is present in the set, and then add it to the set. By testing whether the element is already in the set, you identify the <i>duplicated value</i>. After creating your complete Bloom filter, then test integers 1 to N to see which is not in the set; this is your <i>missing value</i>. I believe this should be constant space and linear time.<p>Above I said "probably" because there are false positives (though not false negatives).

This was a common Microsoft interview question in the 1990s. The answer is probably easy to find on the inter-tubes.

Not sure if this is what's being discussed in the comments already, but it seems like you should be able to XOR all the numbers in the array, and then compare that to the XOR of all the consecutive numbers (which will xor to 0 if n mod 4 == 3).

Python solution. <a href="http://pastebin.com/KyFTXpEr" rel="nofollow">http://pastebin.com/KyFTXpEr</a> O(N) / No additional arrays

bitmap, one extra int and some bitfucking at the end to get the zero bit.

This site is flagged as "Sites likely to contain little of no useful content" by my Universities web filtering software.