Microsoft Interview Question for Software Engineer / Developers






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

//algorithm to get next integer
//i/p = 10011100; o/p = 10100111
(1) check from right to left
(2) leave trailing 0's and find the first 0 (10 0 11100)
(3) we have to make this 0 to 1
(4) watever 1's are there bubble all those 1's to trailing side
u have the answer

ex:

(1)
6543210(poistion)
1011010(num)
1st zero position after getting 1 1's is 2, make it 1 and all 1-1 1's at rightmost side
1011100

(2)
6543210(poistion)
1011100(num)
1st zero position after getting 3 1's is 5, make it 1 and all 3-1 1's at rightmost side
1100111

(3)
6543210(poistion)
1100111(num)
1st zero position after getting 3 1's is 3, make it 1 and all 3-1 1's at rightmost side
1101011

etc

check this code
int bitPosition(int n)
{
int count = 0;
while(n>1)
{
n/=2;
count++;
}
return count;
}

int nextInt(int n)
{
int a, b, c, d, e, f, g, val;
a = n ^ (n-1);
b = n | a;
c = b + 1;
d = b ^ c;
e = n & d;
f = a & e;
g = (e >> bitPosition(f));
val = c | g;
return(val);
}

if we can write bitPosition(n) where only 1 bit is set in n in O(1), then nextInt(n) is O(1) time algorithm else its O(log n)

- mail2vcp@gmail.com September 29, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does the Q mean same number of 1 bits(001, 010, 100) or same 1 bit set(001,011) in the representation.

- MS November 09, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

same number of 1 bits(001, 010, 100). say, given 5(101), 3(011) is the previous one and 6(110) is the next one.

- AK47 November 09, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For the left neighbor:

int number = inputNumber;
int delta = 1, moves = 0;
bool neighborNotFound = false;
while ((number & 3) != 2) { // for right neighbor, change this line to
// (number & 3) != 1
number >>= 1;
delta <<= 1;
if (moves++ > 32) {
neighborNotFound = true;
break;
}
}

if (neighborNotFound)
cout << "no left neighbor"
else
cout << "left neighbor is " << inputNumber - delta << endl;


ps: right neighbor can be found in the similar manner. The basic idea is to find first 10(for left neighbor) and 01(for right neighbor) from the right end of the number's binary form.

- greatht November 09, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,
Can you please explain your algorithm in detail? I dont understand why it works.

Thanks

- Spirit November 14, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This does not work 100%. For 10001 (=17) the above will obtain 01001 (17-8 = 9), whereas the correct answer is 01100(=12). Once you have subtracted delta, all the 1s to the right needs to move the the left. This will make the difference between number and left neighbor the minimum.

Same for right neighbor. Try with 011100. After adding the delta, all 1's need to move to right most positions to make difference smallest.

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

Good solution.

- J May 04, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Greatht

Can you explain your algorithm more in details? I still don't get why it works.

- vodangkhoa November 13, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class SameNumOfOnes
    {
        public SameNumOfOnes()
        {
            string inpStr;
            while ((inpStr = ReadInt()) != "END")
            {
                if(!inpStr.Equals("Error")) 
                    if (GetPrevNextSameOnes(long.Parse(inpStr)) < 0)
                        Console.WriteLine("Error");
            }
        }

        private string ReadInt()
        {
            Console.Write("Enter an integer to convert to words (Enter 'END' to quit):");
            long inpNum;
            string inpStr;

            try
            {
                inpStr = Console.ReadLine();
                if (inpStr.Equals("END"))
                    return inpStr;
                inpNum = long.Parse(inpStr);
                return inpStr;
            }
            catch (FormatException ex)
            {
                Console.WriteLine("Entered an invalid integer!!!. -- " + ex.Message );
                return "Error";
            }
            catch (OverflowException ex)
            {
                Console.WriteLine("Entered an invalid integer!!!. -- " + ex.Message);
                return "Error";
            }
            catch (ArgumentNullException ex)
            {
                Console.WriteLine("Entered an invalid integer!!!. -- " + ex.Message);
                return "Error";
            }
        }

        private int GetPrevNextSameOnes(long inpNum)
        {
            if (inpNum == 0)
            {
                return -1;
            }

            int countOfOnes = GetNumOfOnes(inpNum);
            long tempNum = inpNum;
            
            while (inpNum != long.MaxValue && countOfOnes != GetNumOfOnes(++inpNum)) ;
            if (inpNum != long.MaxValue)
                Console.WriteLine("Next integer with same number of ones:{0}", inpNum);
            else
                return -1;
            
            while (tempNum != long.MinValue && countOfOnes != GetNumOfOnes(--tempNum)) ;
            if (tempNum != long.MinValue)
                Console.WriteLine("Previous integer with same number of ones:{0}", tempNum);
            else 
                return -1;

            return 0;
        }

        private int GetNumOfOnes(long n)
        {
            Console.Write(".");
            bool isNegative = n < 0 ? true : false;
            n = isNegative ? -1 * n : n;
            int count = 0;
            while (0 != n)
            {
                if (n % 2 == 1)
                    count++;
                n /= 2;
            }

            count = isNegative ? (sizeof(int) * 8) + 1 - count : count;
            return count;
        }

}

- spirit November 14, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Greatht's algorithm is correct.
To explain this, let's take 1000101111 for example.

Since we want to find the next binary with same number of 1's. So if we treat this as a string, the next number is among all the strings that swap some 0 and 1 in this string. (If it's all 1, then image there is a leading 0)

We obviously don't want it to be very large. So if there is a 0 in the lower bit for us to swap with some 1 in even lower bit, then we can always keep the higher bit unchanged. [Otherwise we will make this number larger].

So, now we have 10001-01111 with 10001 unchanged, this implies that we have to find the rightmost 01 pattern. Once we get this, the rest of this is simple, just swap the 01 and we get the next neighbor.

- Eric November 14, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it is wrong. Consider the following example

Number = 236 = 11101100

Iteration1:
11101100 & 11 = 00
Number = 11101100 >> 1 = 1110110 (118)
Delta = 1 << 1 = 10 (2)

Iteration2:
1110110 & 11 = 10 (2) So will come out of while loop
Will print Number - Delta = 1110110 - 10 = 118 - 2 = 116

The answer should be 234 (11101010) 5 ones in it. 236 also has 5 ones in it.

- Spirit November 15, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Spirit, you might be wrong. Notice that it's
InputNumber - delta. It's not Number - delta.

It equals to "change that 10 to 01" in InputNumber

- Eric November 15, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

My Solution. Though brute force it works.

class SameNumOfOnes
    {
        public SameNumOfOnes()
        {
            string inpStr;
            while ((inpStr = ReadInt()) != "END")
            {
                if(!inpStr.Equals("Error")) 
                    if (GetPrevNextSameOnes(long.Parse(inpStr)) < 0)
                        Console.WriteLine("Error");
            }
        }

        private string ReadInt()
        {
            Console.Write("Enter an integer to convert to words (Enter 'END' to quit):");
            long inpNum;
            string inpStr;

            try
            {
                inpStr = Console.ReadLine();
                if (inpStr.Equals("END"))
                    return inpStr;
                inpNum = long.Parse(inpStr);
                return inpStr;
            }
            catch (FormatException ex)
            {
                Console.WriteLine("Entered an invalid integer!!!. -- " + ex.Message );
                return "Error";
            }
            catch (OverflowException ex)
            {
                Console.WriteLine("Entered an invalid integer!!!. -- " + ex.Message);
                return "Error";
            }
            catch (ArgumentNullException ex)
            {
                Console.WriteLine("Entered an invalid integer!!!. -- " + ex.Message);
                return "Error";
            }
        }

        private int GetPrevNextSameOnes(long inpNum)
        {
            if (inpNum == 0)
            {
                return -1;
            }

            int countOfOnes = GetNumOfOnes(inpNum);
            long tempNum = inpNum;
            
            while (inpNum != long.MaxValue && countOfOnes != GetNumOfOnes(++inpNum)) ;
            if (inpNum != long.MaxValue)
                Console.WriteLine("Next integer with same number of ones:{0}", inpNum);
            else
                return -1;
            
            while (tempNum != long.MinValue && countOfOnes != GetNumOfOnes(--tempNum)) ;
            if (tempNum != long.MinValue)
                Console.WriteLine("Previous integer with same number of ones:{0}", tempNum);
            else 
                return -1;

            return 0;
        }

        private int GetNumOfOnes(long n)
        {
            Console.Write(".");
            bool isNegative = n < 0 ? true : false;
            n = isNegative ? -1 * n : n;
            int count = 0;
            while (0 != n)
            {
                if (n % 2 == 1)
                    count++;
                n /= 2;
            }

            count = isNegative ? (sizeof(int) * 8) + 1 - count : count;
            return count;
        }

- Spirit November 15, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int p;
int a[32] = {0}, b[32] = {0}, c[32] = {0};
int i = 31;

p = 0x51; // Is the input no.


while(p)
{
if(p & 0x80000000)
{
a[i] = c[i] = b[i] = 1;
}
p = p << 1;
i--;
}

for (i =1; i<32; i++)//Find lesser than p with same no. of bits on
{
if(b[i] == 1 && b[i-1] == 0)
{
b[i] = 0;
b[i-1] = 1;
break;
}
}

for (i=1; i<32;i++) //Find more than p with same no. of bits on
{
if(c[i] == 0 && c[i-1] == 1 )
{
for(;i>0;i--)
c[i]=c[i-1];
c[0] = 0;
break;
}
}

- Vicky November 17, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Consider the binary number as a string...

For the Next Number -- Traverse the string from right to left,if you find 10 then swap them ...if you dont find any pair of that sort then it is the number with max. number of 1's usually it happens with all 1's

Prev. Number -- Traverse from left to right , if you find 10 then swap them ,similarly..

- Vamsi December 04, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ Vamsi

It doesn't work for 2.

- Crab March 01, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check the number from the least significant bit and if you find 1 and 0 combination then swap them else the number doesn't have a next number with same number of bits ... similarly for the previous number start from the most significant bit and try to find 1 and 0 combination if found swap else doesnt have previous number with same number of bits ..

for Next Number

for(int i=0;i<str-1;i++){
		if(str[i]=='1' && str[i+1]=='0'){
			swap(str[i],str[i+1]);
			print(str);
			break;
		}
	}

}

- Vamsi December 06, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think we need to start from LSB in both cases

- Anonymous December 01, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think we need to start from LSB in both cases

- Anonymous December 01, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Nice Solution Vasami :)

- Swati February 13, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry for typo
nice solution vamsi :)

- Swati February 13, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vamsi, you solution has a problem. Think about 6 (0110), the next integer should be 9 (1001), but your solutions gives 10 (1010). So not only you should swap, but you also need to move all other 1's you meet to the LSB side.

So for next number:

int j = 0; /* The least significant bit which is 0 */
for(int i=0;i<str-1;i++){
if(str[i]=='1' && str[i+1]=='0'){
swap(str[i],str[i+1]);
print(str);
break;
} else if (str[i]=='1') {
swap(str[i], str[j]);
j ++;
}
}

- integer March 08, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int numbits ( int n )
{
int count = 0; for ( ; n; count++) { n &= n-1 } return count;
}
<safetychecks = "off>

int bitcount = numbits ( N ); // N is the integer in question
int tmp = N;
while ( numbits ( --tmp ) != bitcount; // tmp has prev neighbor
tmp = N;
while ( numbits ( ++tmp ) != bitcount; // tmp has next neighbor

</safetychecks = "on">

Doc

- DrFunFrock March 13, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just Find first 01 and 10.

- hp March 22, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;


int CountOnes(int num)
{
	int count = 0;
	while(0 != num)
	{
		if(num%2==1)
			count++;
		num/=2;
	}

	return count;
}

int main()
{
	int num,passnum,NxtNum;

	num=passnum=NxtNum=6;

	int count = CountOnes(num);

	bool prevnum = false;
	bool nxtnum = false;

	int prevcount,nxtcount;
	int prev_num,nxt_num;

	prevcount=0;nxtcount=0;

	while( !prevnum || !nxtnum )
	{		
		if ( prevcount == count )
		{
			prev_num = passnum;
			prevnum = true;
		}
		else
		{
			prevcount = CountOnes(--passnum);
		}

		if ( nxtcount == count )
		{
			nxt_num = NxtNum;
			nxtnum = true;
		}
		else
			nxtcount = CountOnes(++NxtNum);
	}

	return 0;
}

tested with VS 2005....works fine for me..

- Anonymous March 28, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i think the question says this-
1.find the next no having the same no of 1s as this no. say we have 0101, so the next no having the same no of 1s(here 2)is 0110 also for 0111 the answer is 1011. so we are not talking about the just next no(n+1) (i.e for 0001 the answer is 0010, which BTW also satisfies our criteria.
2.similary for the previous no.

Vamsi solution with alongwith Integers Patch is OK....

- Anonymous April 21, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think all of the above discussion missed one point.
For the next neighbor, after finding the rightmost "01" pattern and swap it, we still need to swap the "1"s and "0"s to the right. For example, say A=011,011,111,000. The rightmost "01" pattern appears at position 9(starting from 1 and from left to right). After swapping "0" and "1" in this pattern we get "011,101,111,000". We still need to swap position 7 and 1, 6 and 2, 5 and 3 to get "011,100,001,111". This is the correct next neighbor.
Based on this, the code is very very simple.

- creepingdog April 29, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool after_power2(int& b)
{
int w = 1;

if (b == 0) return false;

while(w < b)
{
w *= 2;
}

if(w > b) w /= 2;

b -= w;

return true;;
}

int count_1(int b)
{
int ctr = 0;

while(after_power2(b))
{
ctr++;
}

return ctr;
}

void find_neighbor(const int a, int& p, int& n)
{
int* b = const_cast<int*>(&a);
int ca = count_1(*b);

p = *b - 1;
n = *b + 1;

while(p && count_1(p) != ca)
{
p--;
}

while(n < 0xFFFF && count_1(n) != ca)
{
n++;
}
}

- here May 02, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i/p: n
previous {
1. find rightmost 10 in n
2. flip it.
3. shift all 1's (if any present after '10' we found in step1) to left till
we get 1.
}

eg. 100011 -> 35
1. 100011
2. 010011
3. 011100 -> 28

next{
1. find rightmost 01 in n
2. flip it.
}

eg. 100011 -> 35
1. 100011
2. 100101 -> 37

- binaryNos May 25, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ok, here comes some bit wizardy:

int prev(int n) {
    
    int y = ~n;
    y &= -y; // lowest zero bit
    n &= ~(y-1); // reset all bits below y
    int z = n & -n; // lowest set bit
    n &= ~z;        // clear z bit
    n |= (z - z / (2*y)); // add requried number of bits below z
    return n;
}

int next(int n) {

    int lo = n & -n;       // lowest one bit
    int lz = (n + lo) & ~n;      // lowest zero bit above lo
    n |= lz;                     // add lz to the set
    n &= ~(lz - 1);              // reset bits below lz
    n |= (lz / lo / 2) - 1;      // put back right number of bits at end
    return n;
}

- pavel.em June 05, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what's 3 's previous number? it seems numbers whose bits are all 1 have no previous number

- travelinglion September 05, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

to binaryNos:
i think there is a missing in your next section.
for example use your method
10110->11010 but actually we know 11001 is the next to 10110
my mothed is very similar to yours but with correction

X0[1][0]
prev: find righttmost 10 and flip it
next: find rightmost 01, flip it and shift the rest '1's in [1] to left until we get lsb

X1[0][1]
prev: find rightmost 10, flip it and shift all 1s in [1] to left until we get a 1
next: find rightmost 01 and flip it

X represents any digits

- winia September 12, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//not compliled
//algorithm to get previous integer
//i/p:11000111; o/p:10111000
int a,b,c,d,e,f,g,h,val;
a = n & (n-1);
b = a ^ (a-1);
c = (b>>1) + 1;
d = n & ~c;
e = d ^ (d+1);
f = log(c, 2) - log(e, 2); //O(log n) step
g = b & d;
h = g << f;
val = a | h; //ANSWER

- mail2vcp@gmail.com September 29, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//algorithm to get next integer
//i/p = 10011100; o/p = 10100111
(1) check from right to left
(2) leave trailing 0's and find the first 0 (10 0 11100)
(3) we have to make this 0 to 1
(4) watever 1's are there bubble all those 1's to trailing side
u have the answer

int nextInt(int n)
{
int a, b, c, d, e, f, g, val;
a = n ^ (n-1);
b = n | a;
c = b + 1;
d = b ^ c;
e = n & d;
f = a & e;
g = (e >> bitPosition(f));
val = c | g;
return(val);
}

if we can write bitPosition(n) where only 1 bit is set in n in O(1), then nextInt(n) is O(1) time algorithm else its O(log n)


//not compliled
//algorithm to get previous integer
//i/p:11000111; o/p:10111000
int a,b,c,d,e,f,g,h,val;
a = n & (n-1);
b = a ^ (a-1);
c = (b>>1) + 1;
d = n & ~c;
e = d ^ (d+1);
f = log(c, 2) - log(e, 2); //O(log n) step
g = b & d;
h = g << f;
val = a | h; //ANSWER

- mail2vcp@gmail.com September 29, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if (LSB == 0) {
if (continue to find next 1 at index i) {
swapbit(i, i-1); // i is 1, i-1 is 0, get the smaller value
if (continue to find next 0 at index j) {
swapbit(i, j); // j is 0, i is j; get the bigger value
}
else {
// input value is negative value
bigger value = (unsigned int)(input) >> i;
}
}
else {// no value could be found, all 0...}
}
// LSB is 1
else {
if (find next 0 at index i) {
swapbit(i, i-1);// get bigger value;
if (continue to find next bit 1 at index j) {
swapbit(i, j); // get smaller value;
}
else {
smaller value = inputvalue << (sizeof(int)*8-i);
}
}
else {
// all 1, cannot find
}
}

- ppp October 07, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For the next number, scan from left to right to find the last 01 pair, swap it and then sort all the 1's and 0's right of the pair in ascending order.

For the previous number, scan from right to left to find the first 10 pair, swap it and then sort all the 1's and 0's right of the pair in descending order.

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

you are absolutely correct.

- durgaprasad March 16, 2011 | Flag


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