## Microsoft Interview Question for Software Engineer / Developers

• 0

Country: -

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

Assuming A is input: 1000111100
1000111100: A
1000111011: A-1
1000111111: A|(A-1)
1001000000: (A|A-1))+1 = B (Now we get the first part of our answer by shifting "least significant" '1' bit
0001111100: A^B = C
1110000011: ~C
0001111011: C-1
0000000011: ~C&(C-1)
0000000100: (~C&(C-1))+1 = D
0000000111: (C/D)>>2 = E (This is the second part of our answer)

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

finally some good solution ))
I think you can do this even simpler:

``````given a number x = 1000111100
lo = x & -x; // locate the lowest set bit: lo = 100
lz = (x + lo) & ~x; // locate the lowest zero above lo: lz = 1000000
x += lo; // flip the 'lz' bit: x = 1001000000
x |= (lz / lo / 2); // add the rest number of ones: x = 1001000111``````

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

I didn't think about -x trick. That's a good one and make it much more simpler :)
However, last line should be "x |= (lz / lo / 2) - 1" instead. You forgot -1 at the end and it would result in "1001001000" instead of "1001000111"
Then it should be a perfect solution :)

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

yep thanks for correction ))

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

Here's a 7 operations solution:

``````int x = Integer.parseInt("1000111100", 2);
int a = x & -x;
int b = x + a;
int c = b ^ x;
int d = c / (a << 2);
int y = d + b;
System.out.println(Integer.toString(y, 2));``````

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

I am expecting some comments as asm has given in his solution. Thanks in advance.

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

If x!=0 then
x&(x-1) + x^(x-1) + 1

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

not working:
x = 112
your formula gives: x0 = 128 while it should be 131

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

78 = 100001100
start from right side, when come up first combo of 01, reverse it,
100010100
then move all the 1 lover than the bombo pos, to the right most 0.
100010001 = 81
this should be able to apply to general situations!!!

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

without loops will also mean there will not be any recursion...right?

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

yes, that's right, just bit manipulations

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

Idea is to swap the least significant '1' with the adjust spot if its '0' (from LSB to MSB)

Why:
You are only adding "the least amount" to make the number larger than it is.

Example:

(for 8 bit numbers)

1) 1
0000 0001

swapping 1 with next 0(again, going LSB to MSB), we get

2) 19
0000 1011
--
swap second LSB with third LSB making it

``````int NextLargetsIntWithSameBits(int num)
{
bitset<sizeof(int)*8> bits(num);
bool prev = bits.at(0);
bool cur = true;
for(int i=1; i<bits.size(); i++)
{
cur = bits.at(i);
if(cur==false && prev==true)
{
bits.set(i);
bits.reset(i-1);
break;
}
}
cout<<bits.to_string()<<endl;
return bits.to_ulong();
}``````

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

nope, it's not working:

NextLargetsIntWithSameBits(76) == 76

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

And we should not use loops. So there should not be any for loops...

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

move from right to left..Locate the first '0' after '1' then exchange.
do the same now replace the first '1' after '0' , if that is not the previously exchanged bits.

ex: 0011 0100 - 52
0011 1000 - 56

0101 0110 - 86
0101 1010
0101 1001 - 89

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

What we need actually is the next permutation of the bits.
This should do it:

``````int main () {
int n = 76;
string s = bitset<32>(n).to_string();
next_permutation(s.begin(), s.end());
cout<<bitset<32>(s).to_ulong()<<endl; // prints 81
}``````

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

do you think an interviewer would accept your solution ? ))

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

Probably not, although he should.

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

well, honestly I did not know that STL has the algorithm 'next_permutation'.. Looking at its source code, it seems be a perfect solution to another problem, that is, generating permutations in lexicographical order

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

return ((x & x-1)==0) ? -1 : ((-x & x)>1) || (x&x-1);

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

this is for largest x0<x

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

<pre lang="" line="1" title="CodeMonkey6775" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
String s;
}
}

</pre><pre title="CodeMonkey6775" input="yes">
sdf</pre>

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

for next smallest number x,

convert x = ~x
do same operations as said by asm on x
convert x = ~x

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

The idea is to find right most string of 1′s in x, and shift the pattern to right extreme, except the left most bit in the pattern. Shift the left most bit in the pattern (omitted bit) to left part of x by one position.

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

// the mission is to find the first lsb set, clear it, and find the second lsb that is 0 and turn it to 1

main()
{
int a = 816;
int p = 0;
int flsb = 0; //first least significant bit set
int slsb = 0; //second least significant bit set

flsb = ((a & (a - 1))^a);

slsb = ~(a | (a - 1));

slsb = ((slsb & (slsb - 1)) ^ slsb);

a &= ~flsb;

a |= slsb;

printf("next int is %i \n",a);
}

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.