CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

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).

- 010010.bin July 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Enkesh Gupta July 12, 2015 | Flag
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));
	}

}

- Yev July 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

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

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

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

- Yev July 12, 2015 | Flag
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).

- NoOne October 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Answer:- log(n)

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

- X July 12, 2015 | Flag Reply
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

- Enkesh Gupta July 12, 2015 | Flag
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;
}

- Pragya July 30, 2015 | Flag Reply
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));

	}

}

- vivek October 27, 2015 | Flag Reply
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));

	}

}

- vivek October 27, 2015 | 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