Microsoft Interview Question for SDE-2s


Country: United States
Interview Type: Phone Interview




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

Maybe he was expecting that you precalculate the number of bits set in all 256 chars?

- kp May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

In more detail: create an array (of ints) where each item contains the bits in the character that is indexing it (e.g. numBits['A'] = 2; etc)
Then it is just an indexing/adding per each character in the array.

- Selmeczy, Péter May 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

didn't understand it. Can someone elaborate?

- aka[1] May 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

preprocess all characters say "a" to "z" and create a map (index) <Character, number of bits set>. Now you just to look up the map to get the answer.

- Vib May 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hamming weight

- SK May 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

HI JSDUDE. Can you please post your solution ?
I believe a optimised way than what you suggested might be a SWAR Algo. Check out these posts
http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer
http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20%28Ones%20Count%29

Also as KP mentioned if we can use some extra memory lookupTable caching count for 8 bit words can be precomputed

- um01 May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

he wanted to see if you can imagine character array as block of integers or not ?
As you know how to count number of set bits in a integer you just have to pair 4 integers together out of character array and apply the same old question "how to count number of set bits in a integer"

- aka[1] May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,

Please evaluate my solution. I am preparing for the interview. Please anyone review it.

void bits() {

char string[] = "numberofbits";

int n = 0; // The variable that indicated the number of bits set

int i,j; // loop variables

char c; //temporary variable to read each character in string as there is manipulation

j=7; // 8-1 which is the number of bits used to represent a character, here used as count

for(i=0; i < strlen(string); i++) {

c=string[i];

while(j>=0) {

if((int)c && 1) n++;

c=c>>1;
j++;

}
}
}

- Anonymous May 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Calling strlen(string) for each and every iteration is not very effective!
Call it once and use the value.

- Selmeczy, Péter May 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

decrement j, not j++

- Vib May 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think if you create multiple threads then each of the character can be evaluated in parallel without having to wait for the next character as we know the boundaries are fixed. Thus the update to n because there is no other way to reduce number of read operations. Thus the parallelism can give us better performance.

Another optimal solution I see it is that if we can read more bytes at time we can reduce the number of read operations which is based on per character basis.

- Mookambika May 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a case of using bitwise dark magic

public int bitsSet(char[] arr) {
	
	int currentRep;
	int count = 0;

	for (int i = 0; i < arr.length; i += 4) {


		currentRep = hammingWeight[i] << 24 | hammingWeight[i + 1] << 16 | hammingWeight[i + 2] << 8 | hammingWeight[i + 3];  
		count += hammingWeight(currentRep);
	}
}

public int hammingWeight(int i) {
	
	//bit magic here- there is a way to do this in O(1)

     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

- SK May 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

make correction - hammingWeight[i] should be arr[i]

- vishgupta92 August 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void countBitset(std::string s){
  	        auto a[256], p = 2, z;
		a[0] = 0;
		a[1] = 1;
		while (p < 256){
			z = p << 1;
			a[p]=1;
			for (auto i=p+1;i < z;i++){
				a[i] = a[p]+a[i-p];
			}
			p = z;
		}
		auto total = 0;
		for (auto i=0;i < s.length();i++){
			total = total + a[s[i]];
		}
		std::cout << total;
}

- xyz May 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Method 1:
better than O(n). O(b) where b = number of set bits.

int countBits(char c) {
		int x = (int) c;
		int bitCount = 0;
		while(x > 0) {
			x = x & (x - 1); 
			bitCount++;
		}
		return bitCount;
	}

Method 2:
O(1)

If character is 8-bit then use following. It can be extended for 32 bits.

int countBitsInChar(char c) {
		int x = (int) c;
		x = (x & 0x55) + (x >> 1) & 0x55;
		x = (x & 0x33) + (x >> 2) & 0x33;
		x = (x & 0x0F) + (x >> 4) & 0x0F;
		return x;
	}

This can be optimized even further but then it becomes less readable. From the book Hacker's Delight :-)

- blue-j June 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not O(1), it is O(log_2(n)).

- Maxus July 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey,
what is the complexity of the solution. Because you are doing x & (x-1) it needs to do a bitwise AND on n bits so you are performing that operation k times so the total complexity is O(k*n) where k = No of set bits

Isn't that worst than plain one time scan of bits and counting number of 1's

- rayasamharish September 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

char* arr="string";
char* ptr=arr;

while(*ptr != '\0')
{
c=*ptr++;
while(c)
{
i+=PICK_LSB(c);
c>>=1;
}
}
printf("Number of ones: %d\n",i);

- Anonymous October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int numbits(char *c){
char *it = c;
int num = 0;
while(*it!=0){
for (int i = 0; i < 8 ; i++){
unsigned char mask = (1<<i);
if( *it & mask ){
num++;
}
}
it++;
}
return num;
}

- i.d.c.a.m.u.s October 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <conio.h>


void main()
{
int num=0,count=0;
printf("Enter any number: ");
scanf("%d",&num);

while(num)
{
num &= (num-1);
count++;

}
printf("Number of set bits in given number are %d\n",count);
getch();
}

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

One of the best approaches to solving the above algorithm is to use the bit manipulation technique and count the bit 1 in the binary representation

Implementation:

#include<bits/stdc++.h>
using namespace std;
int findcount(int n){
    int count = 0;
    while(n){
        if(n & 1 == 1)
            count++;
        n = n>>1;
    }
    return count;
}
int main()
 {
	int t, n;
	cin>>t;
	while(t--){
	    cin>>n;
	    cout<<findcount(n)<<endl;
	}
	return 0;
}

- swapnilkant11 June 15, 2019 | 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