Achieve Internet Interview Question for Analysts


Team: artificial intelligence team
Country: United States
Interview Type: Written Test




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

(1) Get the binary representations of N, and prepend it with a zero.
(2) Starting from least significant bit, look for the first zero bit that has a one bit before it.
(3) Flip the zero and one bit. Since we prepended the binary representation with a zero, we are guaranteed to find this pair of zero/one bit.

- Sunny December 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if there is no 0 ?

- Anon December 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Anon:

for 3 will not have any 0. binary of 3 = 11.
As per Sunny we will prepend with 0 means it will become 011. Now we will start from right and search for 1st 0 which will have 1 before that. we will get 0 at 3rd position. Then we will swap 3rd position number with 2nd position number so binary representation will be 101 i.e. 5.

- itsme.bikkie December 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you solution canot get the right answer in some case.
for example, N=(10110)2, in your case, you will get (11010)2, am i right? but the right answer is (11001)2, which is smaller than (11010)2.
so your step (3) of flip is just not enough, the right way is set the 0 you find in (2) to 1, and rearrange the 1's on the right side of this 0 to the lowest positions if there exist.

I will still use N=(10110)2 to demonstrate that. the 0 you find at (2) is at pos 3(pos 0 is the rightmost bit), so you flip it to 1, and there are 2-1=1(you already use one of it) 1's left on the right side of pos 3, so you set this 1 to the pos 0,then we'll get (11001)2 as the right answer.

you can use bit operation to solve it, assume the pos you find zero is i, there are j 1's on rightside, then the answer is: res = (N&(~(1<<i-1)))|(1<<(j-1)-1)

- busycai December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@busycai - good catch on the trailing zeroes case. Yes after the flip, we also need to rearrange all those ones to lowest positions. Multiple ways to do that, but I might jsut reverse the substring before the bit we are switching since that substring should consist of 1s followed by one more 0s.

- Sunny December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Written in C++.

Input:

2
3
7

Output:

5
11

Code:

#include <iostream>

int count_bits(int n) {
	int i = 0;
	while (n > 0) {
		if (n & 1)
			i++;
		n >>= 1;
	}
	return i;
}

int smallest_greater_same_weight(int n) {
	int i = count_bits(n);
	int m = n;

	for (;;) {
		if (i == count_bits(++m))
			break;
	}
	
	return m;
}

int main() {
	int ntests;
	std::cin >> ntests;
	if (std::cin.fail())
		return 1;
		
	while (ntests--) {
		int n;
		std::cin >> n;
		if (std::cin.fail())
			return 1;
			
		std::cout << smallest_greater_same_weight(n) << std::endl;
	}		
	
	return 0;
}

- Diego Giagio December 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think your program will return 5 for input 5. The result should be greater than the original number.

- Sunny December 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Sunny you are right. I changed the algorithm logic and now it's working. Thanks.

- Diego Giagio December 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int flag = 0;
int shift = 0;
while(true)
{
if(n & 1 == 0 && flag == 0)
continue;
if(n & 1 && flag == 0)
{
flag = 1;
}
if(n & 1 == 0 && flag == 1) //this means we have a bit 0 before bit 1
{
we exchange the bit 0 and bit 1(there are nearby bits), then we got the right number like: 1101 --> 1110; 0111->1011; 10101-->10110; 10100-->11000

}
n >>= 1;
shift += 1;
}

- Anonymous December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
 * binweight: The key is to find a 01 sequence.  Flipping that to
 * 10 will get us to the next integer of the same weight.  We need
 * to consider the corner case where we had one or more zeroes in
 * the least significant part and a 11 more significant to that.
 * The least significant 1 needs to be right shifted as far as it
 * will go.  Next for 0110 is 1001 not 1010.
 */
unsigned short
binweight(unsigned short i)
{
	if (i >= (1<<15))
		return 0;  /* next requires more than 16 bits */
	if (i == 0)
		return 0;  /* no set bits */
		
	int ls0pos = 1;  /* LSb that is still zero */
	for (unsigned short shift = 1; shift < (1<<15); shift <<= 1) {
		if ((i & shift) == 0)
			continue;
		unsigned short nextshift = shift << 1;
		if ((i & nextshift) == 0) {
			i |= nextshift;
			i &= ~shift;
			return i;
		}
		i &= ~shift;
		i |= ls0pos;
		ls0pos <<= 1;
	}
	
	assert(0);
}

- Event Horizon December 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,

I tried to solve this problem in a different way. I think it’s a more general one. I've started with writing the binary weight for the 20 first integer numbers:
N binary N W
---------------------------
(0) 0000 0000 - 0
(1) 0000 0001 - 1
(2) 0000 0010 - 1
(3) 0000 0011 - 2
---------------------------
(4) 0000 0100 - 1
(5) 0000 0101 - 2
(6) 0000 0110 - 2
(7) 0000 0111 - 3
---------------------------
(8) 0000 1000 - 1
(9) 0000 1001 - 2
(10) 0000 1010 - 2
(11) 0000 1011 - 3
---------------------------
(12) 0000 1100 - 2
(13) 0000 1101 - 3
(14) 0000 1110 - 3
(15) 0000 1111 - 4
---------------------------
(16) 0001 0000 - 1
(17) 0001 0001 - 2
(18) 0001 0010 - 2
(19) 0001 0011 - 3
---------------------------
(20) 0001 0100 - 2

The immediate solution will be to have a program which defines a pre-programmed array containing the binary weights, where the index to this array is N. For a given N - we first find its weight W by A[N] . Then, we search for the same W in the array starting the search with index equal to N+1. This algorithm is very efficient since the array serves as a look-up table. But now I wanted to solve it without having the look-up table.
Writing the binary weights above, I've observed two things:
1. The binary weights are elements of a sequence. I mean - the math term of a sequence.
0, 1, 1, 2, 1, 2, 2, 3, …
The weights form an ordered list with a “pattern”. Writing the weights as quadruplets, we get:
0 1 1 2 1 2 2 3
1 2 2 3 2 3 3 4
1 2 2 3 2 3 3 4

The first element of each quadruplet is the lowest value in the 4-element group; the last element has the greater value; the two mid elements have the same value and the difference between the values of first- mid-last -elements is always 1 (of course, it’s due to the bits combinations!). And the sequence, in some way, has a repeated quadruplet and “an increasing by one” quadruplet.

2. I also noticed that to find the smallest integer greater than N - it depends if N is even, or an odd number. So I'm looking for two roles.
By the way, I think that if you apply the algorithm suggested in this conversation (the find & flip algorithm) for an even number, it doesn't work. It works only for odd numbers. For example, let’s check it for N=6. Applying the steps described, the result is 5 which is NOT the smallest integer greater than 6, like: 0110 --> 0101. The result should be 9 .
3. Unfortunately, I’m a little rusty in math (it has been a while since college graduation) and I couldn't write down the roles for an odd and even integer of the sequence. I goggled the subject to find out that:
This sequence is a known sequence that was researched; it’s documented in the “On-Line Encyclopedia of Integer Sequences” created by Neil Sloane (see wiki about On-Line_Encyclopedia_of_Integer_Sequences).
The sequence is cataloged as oeis.org/A000120.
The roles I was looking for are given by the formula (see A000120):
a(0) = 0, a(2*n) = a(n), a(2*n+1) = a(n) + 1.
Or
a(0) = 0, a(2^i) = 1; otherwise if n = 2^i + j with 0 < j < 2^i, a(n) = a(j) + 1.

4. Notes:
– For N even (N=2*n), use: a(2*n) = a(n);
– For N odd(N=2*n+1), use: a(2*n+1) = a(n) + 1
– Weight calculation is a recursive function. Calculate weight of N given, keeping the weights calculated for further calculations, especially weight of N which will be used in searching the smallest integer greater than N. Seems that it wasn't a bad idea at all to have a look-up table (or cache).
– Calculate weight for the next K integers, to find the smallest integer greater than N that has the same weight as of N (from index N+1 to N+K). What is K? K says how far we need to test the next elements. If you look at the sequence (see A000120), it’s clear that as N is bigger, K is also bigger. I can guess that the iteration step is N+1+j where j is: 0 < j < 2^i. But, I didn't check if it's correct.

- Anonymous January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

STOP POSTING YOUR FUCKING HOMEWORK.

PEOPLE STOP ANSWERING!

- Anonymous December 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

I actually don't think this question is outside the realm of this website. It's a perfectly legitimate interview problem that falls within 30-45 min timeframe. As for whether I am helping someone do his homework, I actually don't care. Just want to practice on reasonable questions.

- Sunny December 10, 2013 | Flag
Comment hidden because of low score. Click to expand.


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