## Riverbed Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Phone Interview

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

when array is not sorted, create an array (which will act like a hash map, index as key). If you get number for which the array[number] is already filled, you found a duplicate. Now, you can stop right there and using summation function for 1toN number, you can find missing number.
sum_of_n = (N (N+1))/2
i.e. missing_number = sum_of_n - (sum_of_array_elements - duplicate_number_found)

If array is sorted, traverse the array, if A[i] != i+1 then i is a duplicate number and again use above formula for missing number.

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

This can be done in O(n) time and constant space
1. for every element of array a[i] . if (a[abs(a[i])-1] > 0) a[abs(a[i])-1] = -1*a[abs(a[i])-1]
2. if (a[abs(a[i])-1] <0) it means abs(a[i]) is a duplicate element
3. To get the missing element, we can traverse the array again and find the only +ve element, lets say a[k] is +ve then k+1 is the missing element

E.g. say we have array 1,3,3,2
i = 0 a[1-1] is +ve so array would be {-1,3,3,2}
i = 1 a[3-1] is +ve so array would be {-1,3,-3,2}
i = 2 a[3-1] is -ve which means abs(a) which is 3 is a duplicate element
i = 3 a[2-1] is +ve so array would be {-1,-3,-3,2}

Now the only +ve in this array is 2 i.e. k=3, hence the missing element is k+1 which is 4

Comment hidden because of low score. Click to expand.
0

What if the underlying type is unsigned?

What you are basically doing is using the sign bits as a bit-vector....

Comment hidden because of low score. Click to expand.
0

Good question.
Actually in that case we can modify the logic by adding n to the number and checking for if number is greater than n instead of checking for -ve.

Comment hidden because of low score. Click to expand.
0

What if adding n will overflow?

Comment hidden because of low score. Click to expand.
0

Good Question again. This is the limitation.
Do you have any solution for unsorted array when adding n overflows?

Comment hidden because of low score. Click to expand.
0

The XOR trick works, but makes two passes (posted in other answer).

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

This can be done in O(n) time and constant space
1. for every element of array a[i] . if (a[abs(a[i])-1] > 0) a[abs(a[i])-1] = -1*a[abs(a[i])-1]
2. if (a[abs(a[i])-1] <0) it means abs(a[i]) is a duplicate element
3. To get the missing element, we can traverse the array again and find the only +ve element, lets say a[k] is +ve then k+1 is the missing element

E.g. say we have array 1,3,3,2
i = 0 a[1-1] is +ve so array would be {-1,3,3,2}
i = 1 a[3-1] is +ve so array would be {-1,3,-3,2}
i = 2 a[3-1] is -ve which means abs(a) which is 3 is a duplicate element
i = 3 a[2-1] is +ve so array would be {-1,-3,-3,2}

Now the only +ve in this array is 2 i.e. k=3, hence the missing element is k+1 which is 4

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

Using a bitset of size n, initialized to 0.
As you traverse the array, set the particular bit in the bitset. If you see any bit already set, that's the duplicate. To find the missing number, you will need to traverse the bitset, and any number set to 0 is the missing integer.
O(n) time and O(n) space...

If the array is sorted, then a single traversal will do... without needing a bitset... O(n) time and constant space..

Comment hidden because of low score. Click to expand.
0
of 2 vote

Method 1:

``For unsorted case, you can use bitset of JustCoding says, and is a good solution.``

Method 2:

``If you want O(1) space, then you can compute the XOR of the array with 1 to n. If the missing number is a, and repeated number is b, then you get a XOR b as the result, which will be non-zero. Pick one bit position p, and then do the XOR again, but consider two separate buckets: bucket 0 = numbers whose bit position p is 0, bucket 1 = numbers whose bit position p is 1. At the end, you will get the two numbers a and b. Make another pass, and find out which is which (if also you need to specify that).``

Sorted case:

In the case of sorted, it might seem like a binary search might work, but i think we can prove that we need to look at atleast n/2 positions.

Suppose you didn't, then your algorithm misses two consecutive spots. Now an adversary can choose those two spots and make the missing and duplicated number to fit in those spots. All your algorithm gets information is the presence of n/2 elements.

In fact, we can achieve the n/2 bound in the sorted case.

Assume array is index 1...n.

Look at A. If A = 1, then 1 2 is missing. if A > 2, then 1 is missing.
Now look at A and so on.

Comment hidden because of low score. Click to expand.
0

Actually I misssed one case, when A = 2, in which case we need to check if A = 2 or not...

So the part about n/2 is incorrect (as of now).

Comment hidden because of low score. Click to expand.
0

I guess, the proof of n/2 kind of carries over to prove an n-2 (or n-1) lower bound. If you missed i but looked at i+1, we can have i missing and i+1 repeated. Similarly if you missed i, but looked at i-1, we can have i-1 repeated.

In any case, looking at even numbers will reduce the average number of compares we do, I suppose.

Comment hidden because of low score. Click to expand.
0

Nevermind about the average case. I am dumb.

Comment hidden because of low score. Click to expand.
0

Actually in the sorted case, we can do one optimization.

First scan from left to right and find a discrepancy (missing or repeated). Once we find that, we can do a binary search for the other number!

Comment hidden because of low score. Click to expand.
0

Can you please elaborate method 2 i.e. XOR case.
After getting a xor b, how will taking seperate xor for a particular bit position give us a and b?

Comment hidden because of low score. Click to expand.
0

If you cant understand, Go To Hell LOL

Comment hidden because of low score. Click to expand.
0

Please don't show your frustration on the forum Loler. If you don't want to answer you can choose not to answer. Someone else can always explain. Get some help Loler. Take a break.

Comment hidden because of low score. Click to expand.
0

@Anonymous2: You do understand that there are impersonators about?

@Anonymous1: Once you find a XOR b, which is non-zero, there will be one bit position where it is non-zero. This implies that a and b differ in that bit!

This bit position can be used to bucket the numbers.

For example, say the last bit was the bit where they are different. Now that implies one of a and b is odd, and the other is even! Now when you go through the array again, you XOR the even numbers separately and the odd numbers separately.

@Impersonator Loler: Please stop. Don't force me to register!

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

I think Loler is the most dumb guy i have ever seen... so much explanation for such a bad solution...

Comment hidden because of low score. Click to expand.
0

Shut up Manan.

Comment hidden because of low score. Click to expand.
0

:P

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

can be solved using Mathematics.

public void findTwoNumbers(){
/*let duplicated number be x and missing number be y
sum the elements to n numbers sum =(n)(n+1)/2-x+y
since we know sum and n we get x-y
similarly sum the sqare of elements we get sq_sum=(n)(n+1)(2n+1)/6-x2+y2
from this we get x2-y2
we can get x and y from this
complexity o(n)

ex: 1,2,3,4,5,5,7
x-y = 1
x2-y2 = 11

x2 = 11 + y2
x = y + 1
(Y+1)2 = 11+y

y=5;
x=6;
*/

}

Comment hidden because of low score. Click to expand.
0

Awesome

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.

### 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.