Google Interview Question for Interns


Team: Android
Country: United States
Interview Type: In-Person




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

Please check "Next higher number with same number of set bits" on geeksforgeeks

- lgylym February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simply count the number of 1-bits in the word. Let their number be n. The highest integer would be the one with n 1s in the more significant positions and the lowest integer would have n 1s in the less significant positions.

bit_count = 0;
 
while (n) {
bit_count++
n = n & (n-1)
}
 
largest_int = 0;
bit_count1 = bit_count;

while(bit_count1--) {
largest_int = largest_int>>>1 | 2^word_size
}

smallest_int = 0
while(bit_count--) {
smallest_int = smallest_int <<1 | 1
}

- Murali Mohan January 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You didnt solve the problem as asked.
You need to find the next highest integer, not THE highest integer...

- Philip January 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

My approach would be, in order to get the next higher int, to switch the lowest '1' with the next higher '0'

Here the c# code for writing the next higher int:

private static void PrintNextHigherInteger(int i)
        {
            bool found = false;

            int bitmask = Convert.ToInt32("1", 2);
            int higher = i;
            int counter = 0;
            //in order to get the next higher int, switch the lowest '1' with the next higher '0'
            while (true)
            {
                int k = higher & bitmask;
                if ((higher & bitmask) != 0 && !found)
                {
                    found = true;
                    higher = higher - (int) Math.Pow(2, counter);
                }
                else if(found)
                {
                    //test if current bit is '0'
                    int test = higher << counter;
                    if (test % 2 == 0)
                    {
                        higher += (int) Math.Pow(2, counter);
                        break;
                    }
                }
                bitmask = bitmask << 1;
                counter++;
            }
            Console.WriteLine("middle {0} - higher {1}", i, higher);
        }

the next lowest int can be printed the same way. you just have to switch the lowest '1' with the next higher '0'

- Philip January 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

I don't think it is correct, for example the next higher integer for 11 (3) is 101 and not 110 like you suggest. The right heuristic is to look for the first 01 (starting from the LSB) and switch.

111010001011
                    ^ ^
111010001101

- Joky January 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

The next lowest isn't as simple. I believe you have to find the most significant position of 10, change it to 01. However, you then have to move all remIning 1s to the right as left as possible. For example:

110 011 first becomes 101 011, but the last 011 needs to be shifted to become 110, giving 101 110.

- Anonymous January 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For the next highest, you should find the first zero from LSB with the first one that appears *after* the selected zero. If not found, no solution. Similarly for the next lowest, find the first zero from LSB and swap it with the first one that appears *after* the selected one. e.g. 110011 -> next highest: 110101, next lowest: 100111

- Anon July 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's some code

Wrote for next larger number, sure you can do the something similar for next smaller, didn't write it yet.

package com.interview.bits;

public class NextHigherBitDecimalEqual1 {
    
    
    
    public static void main(String[] args) {
        int a = 455;
        
        String bits = changeBaseToStringBits(a,2);
        System.out.println("a is " + a + " in bits:" + bits);
        
        int nextHighestWithSameOnes = getNextHighestWithSameOnes(a);
        
        String bits2 = changeBaseToStringBits(nextHighestWithSameOnes, 2);
        System.out.println(nextHighestWithSameOnes + " in bits is: " + bits2);
    }

    private static int getNextHighestWithSameOnes(int a) {
        String bits = changeBaseToStringBits(a,2);
        
        // look for one on whose left we have zero, if found swap it. cosolidate all the ones on the right of it to the extreme right, bubbling up the ones.
        // if we reach end, then add extra character:=> 1xxx=> 10xxx, corresponds to 111 => 1011, 1110 => 10011
        
        int i = bits.length()-1;
        int numberOfOnesEncountered = 0;
        while(i >=0 ) {
            if(i > 0 && bits.charAt(i)=='1' && bits.charAt(i-1) == '0') {
                // swap i and i-1
                if(i != bits.length()-1)
                    bits = bits.substring(0,i-1) + "10" + bits.substring(i+1);
                else
                    bits = bits.substring(0,i-1) + "10";
                break;
            }
            // all 1111's
            // or 1 at the end like: 111000
            // transform to 111 => 1011 and 111000 ==> 1011000
            if(i == 0 && bits.charAt(i) == '1') {
                bits = "10"+ bits.substring(1);
                i = 1; 
                break;
            }
            if(bits.charAt(i) == '1') numberOfOnesEncountered++;
            i--;
        }
        // 101100 => 110100 ==> 110001
        // so basically move the i back and determine how many 1's you encounter.
        int numberOfZeroesNeeded =  ( bits.length()-i) - numberOfOnesEncountered;   // 100110 => 101010  6 - 3 - 1 = 2
        
        // now recreate bis add zeroes and ones as needed.
        bits = bits.substring(0,i);
        // add zeroes
        for(; numberOfZeroesNeeded > 0 ; numberOfZeroesNeeded--, bits +="0");
        for(; numberOfOnesEncountered > 0; numberOfOnesEncountered--,bits+="1");
        
        int newNumber = convertBitStringToNum(bits);
        return newNumber;
    }

    private static int convertBitStringToNum(String bits) {
        int newNumber = 0;
        int base = 1;
        for(int i = bits.length()-1; i >=0; i--,base*=2) {
            if(bits.charAt(i) == '1') {
                newNumber += base;
            }
        }
        return newNumber;
    }

    private static String changeBaseToStringBits(int a,int base) {
        String bits = "";
        while(a > 0) {
            bits = a%base + bits;
            a = a/base;
        }
        return bits;
    }

}

- suketukvakharia January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is some code for nextSmallest integer with the same number of set bits

int nextSmallest(int n) {
    
    int scanner = 0;
    
    // find the first set bit in n
    while ( !((n >> scanner)&1) ) {
        scanner++;
    }
    
    // now skip block of consequtive 1's
    while ( (n >> scanner)&1 ) {
        scanner++;
    }
    // position to the MSB of the block of 1's
    scanner--;
    
    // reset the bit
    n &= ~(1 << scanner++);
    
    // now find the first clear bit in n
    while ( (n >> scanner)&1 ) {
        scanner++;
    }
    
    // set the bit
    n |= (1 << scanner);
    
    return n;
}

- n.j.joshi January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What language is that?

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

Few observations:
1) A number and two times of this number have the same number of 1's (multiplying shifts bit pattern by a position towards left)
2) By point 1, half of a number will also be having same number of 1's (except for those patterns which are all 1's)
3) For numbers whose bit pattern is all 1's no solution possible for "lesser than" case

A simple approach is (a) for highest number, loop over numbers from N to 2*N. Get bit representation of each number in the loop, compare number of 1's. Stop at the first match. (b) for lowest number, loop over numbers from N to N/2, get bit representation for each, compare number of 1's. Stop at the first match.

Complexity will be O(N*logN) : loop will iterate atmost N times, fetching bit representation is O(logN), comparing counts of 1's also O(logN).

- DevGuy January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//with overflow error
unsigned long long next_largest(unsigned long long n)
{	
	unsigned long long m = n, x = 0;
	
	while(true)
	{
		if( !(n&2) && (n&1) )					
			return (m & ~(3<<x)) | (2<<x);				
		n >>= 1;
		x++;
	}
} 

//with underflow error
unsigned long long next_smallest(unsigned long long n)
{
	unsigned long long m = n, x = 0;
	
	while(true)
	{
		if( (n&2) && !(n&1) )		
			return (m & ~(3<<x)) | (1<<x);		
		n >>= 1;
		x++;
	}
}

- lasthope January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why not do simple logic
1. Find out number of 1 bits in number
2. test each number for number of 1 bits if same as original check with min max so far, update if more than max and lower than min

am i missing something here doesn't look me supper complicated as kind of solutions i am seeing

- Anonymous January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"test each number"... how many numbers are tested here?
For example, if you start testing from 1<<20 and test each consecutive number for having one bit set, it would take another 1<<20 numbers till you hit 1<<21 .

- Anonymous January 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

only have culculated the nearest high,
public static int getLowestNear(int a){
String binary = Integer.toBinaryString(a);
//add 0 at the left of the string
binary = "0"+binary;
int result = 0;
//if it is odd, then find the first 0 from the right most, position as i,
// then the nearest low is 2^i-2^(i-1)=2^(i-1),i start from 0
//if it is even, then find the first 0 after 1 from the right most, position as i.
// then the nearest low: if has 1 of 1s, 2^i-2^(i-1)=2^(i-1) ;
// if has 2 of 1s, 2^i-2^(i-1)-2^(i-2)+1=2^(i-2)+1 ;
// else 2^(i-1)+1.
if(a<=0) return 0;
if(a%2==1){
for(int i=0;i<binary.length();i++){
int index = binary.length()-i-1;
if(binary.charAt(index)=='0') {
result = a+ ((Double)(Math.pow(2,i-1))).intValue();
break;
}
}
}else{
int count=0;
int has1count = 0;
for(int i=0;i<binary.length();i++){
int index = binary.length()-i-1;
if(binary.charAt(index)=='0') {
if(has1count>0)count++;
if(count==1) {
if(has1count==1) {
result = a+ ((Double)(Math.pow(2,i-1))).intValue();
}else if(has1count==2){
result = a+ ((Double)(Math.pow(2,i-2)+1)).intValue();
}else{
result = a+ ((Double)(Math.pow(2,i-1)+1)).intValue();
}
break;
}
} else{
has1count ++;
}
}
}
return result;
}

- Anonymous January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

wrong solution

- Anonymous January 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static int getHighNear(int a){
String binary = Integer.toBinaryString(a);
//add 0 at the left of the string
binary = "0"+binary;
int result = 0;
//if it is odd, then find the first 0 from the right most, position as i,
// then the nearest low is 2^i-2^(i-1)=2^(i-1),i start from 0
//if it is even, then find the first 0 after 1 from the right most, position as i.
// then the nearest low: 2^i-2^(i-1)-...-2^(i-n)+2^(n-1)+ ...+2^0.
// result = a+ 2^(i-min) + 2^(min-1)-1; min is min of 1s and 0s, on the right
if(a<=0) return 0;
if(a%2==1){
for(int i=0;i<binary.length();i++){
int index = binary.length()-i-1;
if(binary.charAt(index)=='0') {
result = a+ ((Double)(Math.pow(2,i-1))).intValue();
break;
}
}
}else{
int count=0;
int has0count =0;
int has1count = 0;
for(int i=0;i<binary.length();i++){
int index = binary.length()-i-1;
if(binary.charAt(index)=='0') {
if(has1count>0)count++;
has0count++;
if(count==1) {
int min = Math.min(has0count,has1count);
result = a+ ((Double)(Math.pow(2,i-min))).intValue()
+ ((Double)(Math.pow(2,min-1))).intValue()-1;
}
} else{
has1count ++;
}
}
}
return result;
}

- Anonymous January 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static int getLowNear(int a){
        String binary  = Integer.toBinaryString(a);
        //add 0 at the left of the string
        binary = "0"+binary;
        int result = 0;
        //if it is odd, then find the first 1 from the right most, position as i,
        // then the nearest low is 2^i-2^(i-1)=2^(i-1),i start from 0
        //if it is even, then find the first 1 after 0 from the right most, position as i.
        // then the nearest low:  2^i-2^(i-1)-...-2^(i-n)+2^(n-1)+ ...+2^0.
        //  result = a- 2^(i-min) - 2^(min-1)+1; min is min of 1s and 0s, on the right
        if(a<=0) return 0;
        if(a%2==0){
            for(int i=0;i<binary.length();i++){
                int index = binary.length()-i-1;
                if(binary.charAt(index)=='1') {
                    result = a - ((Double)(Math.pow(2,i-1))).intValue();
                    break;
                }
            }
        }else{
            int count=0;
            int has0count =0;
            int has1count = 0;
            for(int i=0;i<binary.length();i++){
                int index = binary.length()-i-1;
                if(binary.charAt(index)=='1') {
                    if(has0count>0)count++;
                    has1count++;
                    if(count==1) {
                        int min = Math.min(has0count,has1count);
                        result = a- ((Double)(Math.pow(2,i-min))).intValue()
                                - ((Double)(Math.pow(2,min-1))).intValue()+1;
                    }
                } else{
                    has0count ++;
                }
            }
            if(has0count==1) return a;
        }
        return result;

}

- Anonymous January 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

find number of set bit. move all at least significant bit for lowest and most significant bit for highest number

void findLowHigh(int num) {
		int setbits = __builtin_popcount(num);
		int lowest = 0;
		int highest = 0;
		for(int i=0; i<setbits; ++i) {
			lowest += (1<<i);
			highest += (1<<(31-i));
		}
		cout << lowest << endl;
		cout << highest << endl;
	}

- jitendra.theta January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation :

unsigned int t = (v | (v - 1)) + 1;  
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

- Anonymous January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A solution for the next lower permutation:

int
main(int argc, char **argv)
{
    unsigned v =  atoi(argv[1]);
    unsigned wout_trail1 = v;
    unsigned trail1_marker=0, next1_marker=0;
    unsigned trail1_shifted=0, next1_shifted=0;
    unsigned trail1=0, trail1_shift_factor=0;

    if (!v // are there any bits set
        || (v & (v+1)) == 0) { // are all the bits set
        printf("no lower perm\n");
        return 0;
    }

   // find the group of trailing 1's
    if (v & 0x1) {
        trail1_marker = ~v & (v + 1);
        trail1 = trail1_marker - 1;
        // clear the trailing 1's
        wout_trail1 = v - trail1;
    }

    // find the next 1 bit (after clearing trailing 1's if any)
    next1_marker = wout_trail1 & -wout_trail1;
    // clear it
    next1_shifted = wout_trail1 & ~next1_marker;
    // now shift it one place right
    next1_marker >>= 1;
    // and put it back in the new position
    // for example: 0011000 -> 0010100
    next1_shifted |= next1_marker;

    // shift the trailing 1's to sit right next to the "next1" bit
    // for example: 001100111 -> 001111100
    if (v & 0x1) {
        trail1_shift_factor = next1_marker / trail1_marker;
        trail1_shifted = trail1 * trail1_shift_factor;
    }
    // combine both parts to form the next lower permutation
    v = trail1_shifted | next1_shifted;
    print ("next lower: %d\n", v);
    return 0;
}

- shin January 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is the algorithm

switch means making 0 to 1 and 1 to zero

for next highest
------------------------
switch the lowest bit with value 0 (let it be position n) and the lowest 1 on the right side of the switched 0.
then just minimize the rest of the bits after position n.

for next  lowest
---------------------
switch the highest 0 (let the position be n) and the left 1. now maximize all the bits after nth position.

minimize
---------------
switch the highest 1 (let it be position n) and lowest 0. continue to do so after n until no such is possible.

maximize
-------------
switch the highest 0 (let it be position n) and lowest 1. continue to do so after n until no such is possible.

can anyone put an efficient c or java code with this algorithm?


if we convert it to some binary string we can manipulate string easily.
just like

Integer.toBinaryString(int i)

but if anyone knows to do it by bit maniulation please share.

- hirajhil January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In this problem, we don't have to care about higher digits over the lowest 0, 1 sequence when adding 1 (or smaller numbers) to the number. For example,
11010100 --> 1101 0100 (the lowest 0,1 sequence happens in LSB+3 digit)
all we have to do is to find the next highest integer of 0100, and add 1101 on top of it.
It is because 01xx pattern can be increased to 10xx pattern and it is guaranteed that we can find 10xx pattern which has the same number of 1's as that of 01xx pattern.
(In other words, if we add too big number so that 1101 part is changed, it shouldn't be the next highest number)
For example, 0110 --> 1001, 0101 --> 1001.

Notice that we cannot use 01abcd --> 10abcd, as shown in the case 0110 --> 1001.
It is because that if we push a sequence of 1s to LSB side, we can get lower number.
For example, 011100 --> 101100 (but is this the lowest? No. push 11 to LSB) --> 100011 (now it is the lowest among all 6 digit number starting with 10 and having 3 1s)

Getting the next lowest number is similar. Just 1 and 0 exchanged.

My code is as follows:

public class JE2 {
	public static void main(String[] args) {
		int[] input = {0x23, // 0100 0011
					   0x84, // 0111 0100
					   0x5A, // 0101 1010
					   0x01, // 0000 0001
					   0x7FFFFFFE  // 0111 1111 1111 1111 1111 1111 1111 110
					   };
		
		for(int i : input) {
			int low = getNextLowest(i);
			int high = getNextHighest(i);	
			System.out.println((low != -1 ? Integer.toBinaryString(getNextLowest(i)) : "Not available") 
					+ " --> " + Integer.toBinaryString(i)
					+ " --> " + (high != -1 ? Integer.toBinaryString(getNextHighest(i)) : "Not available"));
		}
	}
	
	public static int getNextHighest(int n) {
		if(n <= 0) return -1; // Assuming I'm dealing with only positive integer. Zero also excluded as it has no 1.
		// read from LSB, ignore first 0 sequence, pass through 1's until finding 0.
		int count0 = 0, count1 = 0;
		while(n%2 == 0) {
			n >>= 1;
			count0++;
		}
		while(n%2 == 1) {
			n >>= 1;
			count1++;
		}
		if(count0 + count1 == 31) // assuming 32 bit integer, ignoring the sign bit
			return -1;
		n += 1; // change 0 to 1
		n <<= 1 + count0; // append 1 + count0 0s
		for(int i=0; i<count1-1; i++) { // append (count1 - 1) 1s
			n <<= 1;
			n += 1;
		}
		
		return n;
	}
	
	public static int getNextLowest(int n) {
		if(n <= 0) return -1; // Assuming I'm dealing with only positive integer. Zero also excluded as it has no 1.
		// read from LSB, ignore first 1 sequence, pass through 0's until finding 1.
		int count0 = 0, count1 = 0;
		while(n%2 == 1) {
			n >>= 1;
			count1++;
		}
		if(n == 0) return -1; // if there is no 1 any more, can't find the next lowest number with the same number of 1's
		while(n%2 == 0) {
			n >>= 1;
			count0++;
		}
		n -= 1; // change 1 to 0
		for(int i=0; i<count1+1; i++) { // append (count1 + 1) 1s
			n <<= 1;
			n += 1;
		}
		n <<= count0 - 1; // append count0 - 1 0s
		
		return n;		
	}
}

Output is

11100 --> 100011 --> 100101
10000010 --> 10000100 --> 10001000
1011001 --> 1011010 --> 1011100
Not available --> 1 --> 10
1111111111111111111111111111101 --> 1111111111111111111111111111110 --> Not available

- Mark January 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**************************************************************
**
**  Auto-generated to help solve interview questions.
**
**  Question : 
    Given an integer, find the next highest and next lowest integers, with
equal number of 1s in their binary representation as the original
number. 
**  Carreercup Link:
    careercup.com/question?id=5747769461440512

***************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <unistd.h>

int next(int x, int high)
{
  int n = x, step=0, count=0, lookfor;
  if(high)
      lookfor = 1;
  else
      lookfor = 0;
  while (n )
  {
      if( n % 2 == lookfor)
          step =1;
      else if ( step == 1)
      {
          break;
      }
      n = n / 2;
      count ++;
  }
  if (high)
    n = x | ( 1 << count--);
  else
    n = x & (~( 1 << count--));

  if(high)
    n = n & (~( 1 << count));
  else
    n = n | ( 1 << count);
  return n;
}


int main()
{
  int i;
  
  for(i = 1; i <= 100; i++ )
  {
      printf(" value : Next =  %d  : %d \n", i , next(i, 0));
  }
  return 0;
}

- mohan February 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from math import floor, ceil, log2

def lower_higher(n):
    '''
    Return the closest integers less/greater than i that have the same number of 1s as i (in binary representation)
    '''
    
    # location of the 1 in each of the following patterns
    i10 = 1 # rightmost
    i01 = floor(log2(n)) # leftmost
    
    # find the location of the rightmost '10'
    while not (~(n & (2**i10-1)) and (n & (2**(i10)))):
        i10 += 1

    # find the location of the leftmost '01'
    while not (not (n & (2**i01)) and (n & (2**(i01-1)))):
        i01 -= 1
    
    # lower is simply the rightmost '10' swapped with '01'
    lower = (n - (2**i10)) + 2**(i10-1)
    
    # higher is more complicated: first swap the leftmost '10' with '01'
    higher = (n + (2**i01)) - 2**(i01-1)
    
    # count the number of ones to the left of the 10 first found
    n_ones = 0
    for i in range(0, i01):
        if (higher >> i) & 1:
            n_ones += 1
    
    # make all those ones least significant
    if n_ones > 0:
        higher = (higher & ((2**ceil(log2(higher)) - 1) - (2**(i01) - 1))) | (2**(n_ones) - 1)
    
    return lower, higher

def test_lower_higher():

    assert lower_higher(5) == (3, 6)
    assert lower_higher(46) == (45, 51)
    assert lower_higher(0b1101101) == (0b1101011, 0b1110011)
    assert lower_higher(0b1101100) == (0b1101010, 0b1110001)
    assert lower_higher(0b1101000) == (0b1100100, 0b1110000)

if __name__ == '__main__':
    test_lower_higher()

- Anonymous June 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This worked for test cases I could think of. It seems like there would be elegant solution to this problem, but I'm not seeing it.

- Anonymous June 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int setBit(int n, int index, boolean setBit)
	{
		if (setBit)
		{
			return (n | (1 << index));
		}
		else
		{
			int mask = ~(1 << index);
			return n & mask;
		}
	}

	public static boolean getBit(int n, int index)
	{
		return ((n & (1 << index)) > 0);
	}

	public static int getNextHigherWithSameBitString(int n)
	{
		int index = 0;
		int ones = 0;

		// find first one
		while (!getBit(n, index))
		{
			index++;
		}

		// find first zero after that
		while (getBit(n, index))
		{
			index++;
			ones++;
		}

		// set this bit
		n = setBit(n, index, true);

		// unset previous bit
		index--;
		n = setBit(n, index, false);

		ones--;

		// unset prevous bits equal to number ones
		for (int i = index - 1; i >= ones; i--)
		{
			n = setBit(n, i, false);
		}

		for (int i = ones - 1; i >= 0; i--)
		{
			n = setBit(n, i, true);
		}
		return n;
	}

- Anonymous August 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Okay, here is simple logic:
1) change the given input to binary number.
2) do the following:

def next_highest(num):

bin = dec_to_bin(num)

i = len(bin) - 1

found = False

while ( i > 0):

if bin[i] > bin[i-1]:

found = True

answer = bin[0:i-1] + bin[i] + sorted([ bin[i-1] + bin[i+1:]])

break

return bin_to_dec(answer) if found else -1

- Kevin April 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Assuming a long int here. I excluded the highest and the lowest bit (boundaries). For the rest, a simple bit shift will work I guess. Am I missing something here?

public void getNum (long num) {
		long mask1 = 0x1L;
		long mask2 = 1 << 63;
		if ( ((num & mask1) == 0x1) || ((num & mask2) == 0x1) ) {
			System.err.println ("Reached a boundary condition");
			return;
		} else {
			System.out.println("Next higher number with same number of 1s in binary form = " + (num << 0x1));
			System.out.println("Next lower number with same number of 1s in binary form = " + (num >> 0x1));
		}
	}

- Ajith January 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Sorry for typing the 1st thing that came to mind. This does not work for a bulk of the cases.

- Ajith January 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Number Properties Approach for Next Number
Observations:
»»If we “turn on” a 0, we need to “turn off” a 1
»»If we turn on a 0 at bit i and turn off a 1 at bit j, the number changes by 2^i - 2^j.
»»If we want to get a bigger number with the same number of 1s and 0s, i must be bigger than j.

Solution:
1. Traverse from right to left. Once we’ve passed a 1, turn on the next 0. We’ve now increased the number by 2^i. Yikes! Example: xxxxx011100 becomes xxxxx111100
2. Turn off the one that’s just to the right side of that. We’re now bigger by 2^i - 2^(i-1) Example: xxxxx111100 becomes xxxxx101100
3. Make the number as small as possible by rearranging all the 1s to be as far right as possible: Example: xxxxx101100 becomes xxxxx100011
To get the previous number, we do the reverse.
1. Traverse from right to left. Once we’ve passed a zero, turn off the next 1. Example: xxxxx100011 becomes xxxxx000011.
2. Turn on the 0 that is directly to the right. Example: xxxxx000011 becomes xxxxx010011.
3. Make the number as big as possible by shifting all the ones as far to the left as possible. Example: xxxxx010011 becomes xxxxx011100

public class Practice48 {

	public static void main(String args[]){
		int a = 48;
		
		System.out.println("Next high is :: "+getNextHigh(a));
		System.out.println("Next Low is :: "+getPrevLow(a));
	}
	

	public static int getNextHigh(int a){
		int num = a;
		int bit = num & 1;
		int count = 0;
		int flag = 1;
		while(num > 0 && (bit == 1 || flag == 1)){
			if(bit == 1)
				flag = 0;
			count++;
			num = num >> 1;
			bit = num & 1;
		}
		if(bit == 0){
			int xor = (int) (Math.pow(2, count-1) + Math.pow(2, count));
			a = a ^ xor;
		}
		
		num = a;
		int b = 0,c = ~0;
		int var = 0;
	
		for(int i=0;i<count-1;i++){
			if((num & 1) == 1){
				b = b + (int)Math.pow(2, i);
			}else{
				var++;
			}	
			num = num >> 1;
			c = c << 1;	
		}
		
		while(var > 0){
			b = b >> 1;
			var--;
		}
		
		return (a & c) | b; 
	}
	
	public static int getPrevLow(int a){
		int num = a;
		int bit = num & 1;
		int count = 0;
		int flag = 1;
		while(num > 0 && (bit == 0 || flag == 1)){
			if(bit == 0)
				flag = 0;
			count++;
			num = num >> 1;
			bit = num & 1;
		}
		if(bit == 1){
			int xor = (int) (Math.pow(2, count-1) + Math.pow(2, count));
			a = a ^ xor;
		}
		
		num = a;
		int b = 0,c = ~0;
		int var = 0;
		for(int i=0;i<count-1;i++){
			if((num & 1) == 1){
				b = b + (int)Math.pow(2, i);
			}else{
				b = b << 1;
			}	
			num = num >> 1;
			c = c << 1;	
		}
		
		
		return (a & c) | b; 
	}
}

- Coder January 14, 2014 | 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