Microsoft Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
As simple as knowing the sum of all numbers and then finding the difference between that and the sum of remaining numbers?
simple!
Just to add to it, initial is the sum of first 100 natural number = 100 * 101 / 2
Binary Search is a valid answer if the numbers are sorted, but in the question it has not mentioned that bag is in sorted order. It just says number are between the range "1....100" or lowRange .... highRange.
For efficient algorithm we will use the XOR operation to find the missing number. Algorithm
1. Iterate over all the numbers in the bag and perform the XOR with each other and store the value in variable "XORBag".
2. Iterate over the numbers from lowRange to highRange and perform XOR with each other and store in variable XORRange.
3 now XOR XORBag and XORRange this is your missing number.
Worst case 2 for loops = 2N so complexity O(n).
example:
LowRange = 1 and high range 5 missing number 4.
Bag 3,5,1,2
XOR (3^5) 011 ^ 101 = 110
XOR (result ^ 1) 110 ^ 001 = 111
XOR (result ^ 2) 111 ^ 010 = 101
so XORBag = 101.
For XORRange we just need to XOR above result to 4
so 101 ^ 100 = 001
XORRange = 001
Now, for final answer XORBag ^ XORRange = 101 ^ 001 = 100 = 4
Infact i answered same. Then he proceed and asked another question that numbers are too large and you can't store in memory.
If you meant the sum is too large then sort the bag, then scan to find the missing number.
Sum is not too large. He mentioned that let's say we are having maximum number of 64 bit machine(2pow64 -1 )
How to handle this scneario
I think this problem can be solved in O(logN) time limit..even if N is very large.
at first, you must know that the value f(x) = 1^2^3....^x can be solved in O(1)
if (0 == x % 4) f(x) = x;
else if (1 == x % 4)f(x) = 1;
else if (2 == x % 4) f(x) = x + 1;
else f(x) = 0;
and then you can find the removed value by binary search, you only need to judge whether f(x) = "1^2^...^x", follow me ?
xor
- guest.guest April 24, 2014you have array of a[0] to a[98]
1 ^ 2 ^ .. ^ 100 ^ a[0] ^ ... ^a[98]