Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
8
of 8 vote

First, I assume you know how to solve the simpler problem when A and B have size n+1 and n and they differ by only one element, where you just XOR all the elements of both arrays together and all the common values cancel each other out, leaving the unique value.

The problem for two elements is a reduction to that special case. If you XOR all the elements of A and B then you get z = x ^ y as the result. Since x and y are presumed distinct, they must differ in at least one bit, and hence z must be nonzero in at least one bit, let's say the i-th. That partitions each of A and B into two parts, one where elements have 0 in their i-th bit, and one where elements have 1 in their i-th bit. By construction, x and y occur in separate parts, so we get a reduction to the earlier special case.

The code would look something like this:

#include <stdio.h>

void missing(int n, int *a, int *b, int *x, int *y)
{
	int z = 0;
	for (int i = 0; i < n; i++)
	    z ^= a[i];
    for (int i = 0; i < n-2; i++)	
        z ^= b[i];

    int m = 1;
    while (!(z & m))
        m <<= 1;

    *x = 0;
    *y = 0;
	for (int i = 0; i < n; i++) {
	    if (a[i] & m)
	        *x ^= a[i];
	    else
	        *y ^= a[i];
	}
    for (int i = 0; i < n-2; i++)	{
	    if (b[i] & m)
	        *x ^= b[i];
	    else
	        *y ^= b[i];
	}
}

int main()
{
    int a[] = {5,1,2,6,3,4};
    int b[] = {1,2,3,4};
    int x, y;
    missing(sizeof(a) / sizeof(*a), a, b, &x, &y);
    printf("x=%d y=%d\n", x, y);
	return 0;
}

- psykotic February 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one, this is the right solution!

I'd recommend changing this:
int m = 1;
while (!(z & m))
m <<= 1;

To this:
int m = z ^ (z-1);

XOR-ing the number to it's -1 decremented pair will give you the rightmost set bit.
(Of course your solution works too).

- Adam February 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How is this case when the two distinct elements differ in more than 1 bit handled here?

Suppose, z = x^y = 1100 . Then,
a = 1100, b = 0000
a = 1000, b = 0100
both are valid solutions...

- Anonymous February 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Adam: Yeah, you could also just use (a[i] & z == z) and (a[i] & z == z).

Anonymous: You're not recovering x and y uniquely from z alone. You're using z as a "separator mask" for a second pass over the arrays.

- psykotic February 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

xor solution is nice.. as an alternative we can compute
the sum and sum of squares which for 32-bit numbers won't produce an overflow (or we can work with 64-bit ints instead which wont change the complexity)

thus we get: x + y = SUM_A - SUM_B
x^2 + y^2 = SUMSQ_A - SUMSQ_B

from there x and y can be easily computed.

- Anonymous February 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually the mask should be
m = z ^ ~(z-1)
this will solve any number of bit changes in the two distinct numbers we want to find.

- Dev February 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Really neat algorithm

- saga February 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Really neat algorithm

- saga February 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Really neat algorithm

- saga February 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Add the numbers in both the arrays to get their sums : S1 , S2. Where
S1 = a[0] + a[1] + X + Y+ ..+a[n]+a[n+1] &
S2 = b[0] + b[1] .. + b[n-2] + b[n-1]
so X + Y = S1 - S2

Iterate through the arrays again and get the product of the elements in each array : P1 , P2
P1 = a[0] * a[1] * X * Y * ..a[n]*a[n+1]
P2 = b[0] * b[1] * .. b[n-2] * b[n-1]

So X*Y = P1/P2

We now have 2 equations :
X +Y = S1 - S2 &
X*Y = P1/P2

We can solve these to get the missing numbers in array b - X & Y. This will require 2 iterations of both the arrays. So the time complexity is O(n) and space is O(1).

The only downside of this technique is that if any of the array element is 0, this will not work.

- codemaniac February 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not the only downside. The really big downside is that this isn't an O(n) algorithm. The multiplies can be expected to overflow, and therefore you won't be able to use ordinary int or long variables. After n multiplications you can expect your total to have O(n) digits, which means that multiplying it just once with something else is O(n) or worse. So if a single multiply is O(n), this algo is O(n^2) at best. And...if you're going to spend O(n^2) time, you might as well just implement the naive compare-all-pairs algorithm.

You could fix the 0 problem by counting the number of 0s explicitly, but that won't change the O(n^2) performance.

- eugene.yarovoi February 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I do think your solution is the frequently-given solution to this problem, however. I've been asked this exact question in an interview with a financial firm before, and your answer was the answer my interviewer was expecting me to get. When I gave the same rebuttal I've presented just now, the interviewer realized that he was wrong and let me advance to the next round.


In interviews, I've actually been asked several questions to which the expected answers were wrong. It happens.

- eugene.yarovoi February 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hmmm. True. This solution works only for smaller number of elements where their products do not overflow. Were you able to get a proper solution for this problem ?

- codemaniac February 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And when we say smaller number of elements, we would really have to mean very, very small. Even if all entries in the array are < 100, we'd want n < 10 even for a 64-bit variable.

The top-voted solution here (by psykotic) appears to be correct and truly O(n).

- eugene.yarovoi February 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And as to your question as to whether I got a proper solution during the interview, no, since our time was spent discussing why this solution wasn't O(n). However, as the interviewer was also unable to come up with a correct solution, I advanced to the next round with flying colors.

- eugene.yarovoi February 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

agreed :) the XOR based solution is better ...

- codemaniac February 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

eugene..i don't understand what you mean by 100 and 10. Are you talking saying <=10 entries with a value of 100 or less? Doesn't look like this would overflow in 64 bit. Am I missing something?

- Anonymous February 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm saying that in order for it to not overflow for values ~100, you'd want n < 10 or so.

- eugene.yarovoi February 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another way could be to use a hashtable sort of data structure. Iterate over array b once and store everything into the hashtable. Now iterate over array a and see which ones are missing. this can be achieved in java using hashmap.

- punter February 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another way could be to use a hashtable sort of data structure. Iterate over array b once and store everything into the hashtable. Now iterate over array a and see which ones are missing. this can be achieved in java using hashmap.

- Anonymous February 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I wrote a line of code like
pB[i] & m == 0

but what I really mean is (pB[i] & m) == 0
then I got trouble

- hopeztm February 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Another way could be to use a hashtable sort of data structure. Iterate over array b once and store everything into the hashtable. Now iterate over array a and see which ones are missing. this can be achieved in java using hashmap.

- punter February 10, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More