## Deshaw Inc Interview Question

Country: United States

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

What exactly do you mean by "identify"? The rank of the bit? There's no general solution for an N-bit integer, but for reasonably small values you can make a lookup table to get O(1).

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

By identify, I meant to get the Position of Set Bit

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

Java impl.

``````public class IdentifySetBit {
public static int find_set_bit(int num){

if(num / 256 == 0){
switch(num){
case 1: return 1;
case 2: return 2;
case 4: return 3;
case 8: return 4;
case 16: return 5;
case 32: return 6;
case 64: return 7;
case 128: return 8;
}
}

else if((num>>8) / 256 == 0){
switch(num>>8){
case 1: return 1+8;
case 2: return 2+8;
case 4: return 3+8;
case 8: return 4+8;
case 16: return 5+8;
case 32: return 6+8;
case 64: return 7+8;
case 128: return 8+8;
}
}
else if((num>>16) / 256 == 0){
switch(num>>16){
case 1: return 1+16;
case 2: return 2+16;
case 4: return 3+16;
case 8: return 4+16;
case 16: return 5+16;
case 32: return 6+16;
case 64: return 7+16;
case 128: return 8+16;
}
}

else if((num>>24) / 256 == 0){
switch(num>>24){
case 1: return 1+24;
case 2: return 2+24;
case 4: return 3+24;
case 8: return 4+24;
case 16: return 5+24;
case 32: return 6+24;
case 64: return 7+24;
case 128: return 8+24;
}
}

return -1;
}

public static void main(String[] args) {
System.out.println("Set bit: " + find_set_bit(1));
System.out.println("Set bit: " + find_set_bit(4));
System.out.println("Set bit: " + find_set_bit(16));
System.out.println("Set bit: " + find_set_bit(32));
System.out.println("Set bit: " + find_set_bit(64));
System.out.println("Set bit: " + find_set_bit(128));
System.out.println("Set bit: " + find_set_bit(256));
System.out.println("Set bit: " + find_set_bit(1024));
}

}``````

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

``````public static void main(String[] args) {
int num=1;

for(int iter=1;iter<=32;iter++){
System.out.println("Set bit for " + num+": " + find_set_bit(num));
num <<= 1;
}
}``````

Output:
Set bit for 1: 1
Set bit for 2: 2
Set bit for 4: 3
Set bit for 8: 4
Set bit for 16: 5
Set bit for 32: 6
Set bit for 64: 7
Set bit for 128: 8
Set bit for 256: 9
Set bit for 512: 10
Set bit for 1024: 11
Set bit for 2048: 12
Set bit for 4096: 13
Set bit for 8192: 14
Set bit for 16384: 15
Set bit for 32768: 16
Set bit for 65536: 17
Set bit for 131072: 18
Set bit for 262144: 19
Set bit for 524288: 20
Set bit for 1048576: 21
Set bit for 2097152: 22
Set bit for 4194304: 23
Set bit for 8388608: 24
Set bit for 16777216: 25
Set bit for 33554432: 26
Set bit for 67108864: 27
Set bit for 134217728: 28
Set bit for 268435456: 29
Set bit for 536870912: 30
Set bit for 1073741824: 31
Set bit for -2147483648: 32

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

Fix: use unsigned riht-shift operator

``````public class IdentifySetBit {
public static int find_set_bit(int num){

if(num / 256 == 0){
switch(num){
case 1: return 1;
case 2: return 2;
case 4: return 3;
case 8: return 4;
case 16: return 5;
case 32: return 6;
case 64: return 7;
case 128: return 8;
}
}

else if((num>>>8) / 256 == 0){
switch(num>>>8){
case 1: return 1+8;
case 2: return 2+8;
case 4: return 3+8;
case 8: return 4+8;
case 16: return 5+8;
case 32: return 6+8;
case 64: return 7+8;
case 128: return 8+8;
}
}
else if((num>>>16) / 256 == 0){
switch(num>>>16){
case 1: return 1+16;
case 2: return 2+16;
case 4: return 3+16;
case 8: return 4+16;
case 16: return 5+16;
case 32: return 6+16;
case 64: return 7+16;
case 128: return 8+16;
}
}

else if((num>>>24) / 256 == 0){
switch(num>>>24){
case 1: return 1+24;
case 2: return 2+24;
case 4: return 3+24;
case 8: return 4+24;
case 16: return 5+24;
case 32: return 6+24;
case 64: return 7+24;
case 128: return 8+24;
}
}

return -1;
}``````

Output:
Set bit for 1: 1
Set bit for 2: 2
Set bit for 4: 3
Set bit for 8: 4
Set bit for 16: 5
Set bit for 32: 6
Set bit for 64: 7
Set bit for 128: 8
Set bit for 256: 9
Set bit for 512: 10
Set bit for 1024: 11
Set bit for 2048: 12
Set bit for 4096: 13
Set bit for 8192: 14
Set bit for 16384: 15
Set bit for 32768: 16
Set bit for 65536: 17
Set bit for 131072: 18
Set bit for 262144: 19
Set bit for 524288: 20
Set bit for 1048576: 21
Set bit for 2097152: 22
Set bit for 4194304: 23
Set bit for 8388608: 24
Set bit for 16777216: 25
Set bit for 33554432: 26
Set bit for 67108864: 27
Set bit for 134217728: 28
Set bit for 268435456: 29
Set bit for 536870912: 30
Set bit for 1073741824: 31
Set bit for -2147483648: 32

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

Refactored.

``````public class IdentifySetBit {
public static int octet_ordinal(int num){
if(num/256 == 0){
return 1;
}
else if((num>>>8)/256==0){
return 2;
}
else if((num>>>16)/256==0){
return 3;
}
else
{
return 4;
}
}

public static int find_set_bit(int num){
int octet_ordinal=octet_ordinal(num);
int shift_count = 8*(octet_ordinal-1);

//System.out.println("Octet: "+octet_ordinal);
//System.out.println("Shift count: " + shift_count);

if((num>>>shift_count) / 256 == 0){
switch(num>>>shift_count){
case 1: return 1+shift_count;
case 2: return 2+shift_count;
case 4: return 3+shift_count;
case 8: return 4+shift_count;
case 16: return 5+shift_count;
case 32: return 6+shift_count;
case 64: return 7+shift_count;
case 128: return 8+shift_count;
}
}

return -1;
}

public static void main(String[] args) {
int num=1;

for(int iter=1;iter<=32;iter++){
System.out.println("Set bit for " + num+": " + find_set_bit(num));
num <<= 1;
}
}

}``````

Output:
Set bit for 1: 1
Set bit for 2: 2
Set bit for 4: 3
Set bit for 8: 4
Set bit for 16: 5
Set bit for 32: 6
Set bit for 64: 7
Set bit for 128: 8
Set bit for 256: 9
Set bit for 512: 10
Set bit for 1024: 11
Set bit for 2048: 12
Set bit for 4096: 13
Set bit for 8192: 14
Set bit for 16384: 15
Set bit for 32768: 16
Set bit for 65536: 17
Set bit for 131072: 18
Set bit for 262144: 19
Set bit for 524288: 20
Set bit for 1048576: 21
Set bit for 2097152: 22
Set bit for 4194304: 23
Set bit for 8388608: 24
Set bit for 16777216: 25
Set bit for 33554432: 26
Set bit for 67108864: 27
Set bit for 134217728: 28
Set bit for 268435456: 29
Set bit for 536870912: 30
Set bit for 1073741824: 31
Set bit for -2147483648: 32

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

Guys, and gals, you have been tricked. O(1) is a misnomer, it basically suggests that there exists a fixed constant C, and the total no of operations would be less than that constant, at most. Thus, given the integer bit size known ( it is known for most languages ) and is constant, a fixed sized loop on the integer bit size (K) is indeed O(K) and is O(1).

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

System.out.println(Math.log(n));

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

I guess it won't meet the condition of O(1). As log(n) would also follow a series at the back

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

``````#include<bits/stdc++.h>
using namespace std;
int main()
{
int a;
cin>>a;
int ans=log(a)/log(2) + 1;
cout<<ans;
return 0;
}``````

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

``````public class IdentifysetBit {

int identifysetBit(int n){
for(int i=0;i<32;i++){
int num = 1<<i;
if((num&n)!=0)
return i;
}
return -1;
}
public static void main(String[] args) {
System.out.println(new IdentifysetBit().identifysetBit(1));
System.out.println(new IdentifysetBit().identifysetBit(2));
System.out.println(new IdentifysetBit().identifysetBit(4));
System.out.println(new IdentifysetBit().identifysetBit(8));
System.out.println(new IdentifysetBit().identifysetBit(1<<31));

}

}``````

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

``````public class IdentifysetBit {

int identifysetBit(int n){
for(int i=0;i<32;i++){
int num = 1<<i;
if((num&n)!=0)
return i;
}
return -1;
}
public static void main(String[] args) {
System.out.println(new IdentifysetBit().identifysetBit(1));
System.out.println(new IdentifysetBit().identifysetBit(2));
System.out.println(new IdentifysetBit().identifysetBit(4));
System.out.println(new IdentifysetBit().identifysetBit(8));
System.out.println(new IdentifysetBit().identifysetBit(1<<31));

}

}``````

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.