## NVIDIA Interview Question for Software Engineer / Developers

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

bit hacking is way faster. This is for 16bit integer.

int table[] = {0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4}
#define f(x) table[x&(0xf)]

int count(int num){
return f(num) + f(num>>4) + f(num>>8) + f(num>>16);
}

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

I didn't understand why that table is used..?

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

the idea is correct, just extend it for 32-bit ints:
assume bitcount stores # of 1's set in 1 byte:

unsigned nbits(unsigned x)
{
unsigned char cnt = 0;
cnt += bitcount[ x & 0xff ]; x >>= 8;
cnt += bitcount[ x & 0xff ]; x >>= 8;
cnt += bitcount[ x & 0xff ]; x >>= 8;
cnt += bitcount[ x ];
return cnt;
}

however counting the number of operations + additional space for table this might be not optimal, other solution:

nbits(x) {
x = ((x>>1) & 0x55555555UL) + (x & 0x55555555UL);
x = ((x>>2) & 0x33333333UL) + (x & 0x33333333UL);
x = ((x>>4) + x) & 0x0f0f0f0fUL; // 0-8 in 4 bits
x += x>> 8; // 0-16 in 8 bits
x += x>>16; // 0-32 in 8 bits
return x & 0xff;
}

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

The last shift is >> 12, not >> 16!!

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

i think the question is about finding number of bit set to 1 in a binary representation of a given number.
sol :
cnt =0;
while(n)
{
n &= (n-1); // set left most 1's to 0
cnt++;
}
cout<< "number of 1's : " << cnt;

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

good solution, but the worst case scenario still results in n iterations. An LUT like tc/asm is a better solution.

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

1's in a number? I am not sure what i understand but isnt it like..
convert number to string and traverse the string counting 1's by matching it with ascii of '1' in O(n)

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

that last one should've been f(num>>12). My bad.

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

Can anyone explain the question and answer properly ..

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

i think the question is about finding number of bit set to 1 in a binary representation of a given number.
sol :
cnt =0;
while(n)
{
n &= (n-1); // set left most 1's to 0
cnt++;
}
cout<< "number of 1's : " << cnt;

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

i think the question is about finding number of bit set to 1 in a binary representation of a given number.
sol :
cnt =0;
while(n)
{
n &= (n-1); // set left most 1's to 0
cnt++;
}
cout<< "number of 1's : " << cnt;

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

Agree

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

int counter=0;
while(num>0)
{
if(num%10==1)
counter++;
num/=10;
}

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

i don't think that this will give anyway the solution to the aforsaid problem .

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.