Microsoft Interview Question for SDE-2s


Country: United States
Interview Type: Phone Interview




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

xor
you have array of a[0] to a[98]

1 ^ 2 ^ .. ^ 100 ^ a[0] ^ ... ^a[98]

- guest.guest April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

As simple as knowing the sum of all numbers and then finding the difference between that and the sum of remaining numbers?

- anon April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

simple!
Just to add to it, initial is the sum of first 100 natural number = 100 * 101 / 2

- puneet.sohi April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the meaning and use of one number is picked up randomly?

- rk April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It means, that one number is removed from the bag, randomly

- puneet.sohi April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Swapnil August 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Infact i answered same. Then he proceed and asked another question that numbers are too large and you can't store in memory.

- Mukesh Dua April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you meant the sum is too large then sort the bag, then scan to find the missing number.

- frankl April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Mukesh Dua April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

His main point is we can't load all numbers in memory.

- Mukesh Dua April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the numbers are too numerous to fit into memory try reading them from a file stream. Then you are limited to file size. If that doesn't suffice, use multiple files on multiple hard drives, machines, etc.

- Michael.J.Keating April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about not load all number into memory at once but load part of them? For example, we may calculate the sum of 1 to 100, if the sum is 5050, then we try from 101 to 200, and so on..

It looks similar to "The Two Egg Problem".

- Koegent April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ?

- Stomach_ache April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Find the sum of first 100 consecutive Numbers.This will be calculated by this formula
sum = N * (N +1)/2

2. Find the sum of array where 1 number is missing by adding all the numbers.

3. Subtract sum1 - sum2 and we have the answer.

- om April 24, 2014 | 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