Google Interview Question


Country: India
Interview Type: In-Person




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

One can make the following observation:

printing for k

is equivalent to

print all combinations of length k with 0 ones
print all combinations of length k with 1 ones
...
print all combinations of length k with k ones

A second observation is:

print all combinations of length k with n ones

is equivalent to
print (prepend 0 to all combinations of length k-1 with n ones)
print (prepend 1 to all combinations of length k-1 with n-1 ones)

This way we get a recursive function where we can cache intermediary results.
This is obviously more space inefficient than just generating all bit combinations and sorting them in place. Can anyone help me out with runtime analysis and tell me if it's faster?

Python class:

class KBitGenerator:

    cache = {}

    def generate(self, k):
        result = []
        for i in range(k + 1):
            result += self.generate_for_num(k, i)
        return result

    def generate_for_num(self, length, num_ones):
        if (length, num_ones) in self.cache:
            return self.cache[(length, num_ones)]
        result = []
        if num_ones == 0:
            result = [[0] * length]
        elif length == num_ones:
            result = [[1] * length]
        else:
            for pattern in self.generate_for_num(length - 1, num_ones):
                result.append([0] + pattern)
            for pattern in self.generate_for_num(length - 1, num_ones - 1):
                result.append([1] + pattern)
        self.cache[(length, num_ones)] = result
        return result

- Johnie May 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

here is a simple solution in C++:

#include <iostream>
#include <vector>

int bitcount(int aArg) {
  int c = 0; // bit count
  for(; aArg; c++)
    aArg &= aArg -1; // clears the least significat bit

  return c;
}

void printBitCombinations(int K) {
  std::vector<int> A;

  for(int i = 0; i <= K; ++i) {
    for(int j = 0; j < 1 << K; ++j) {
      if(bitcount(j) == i)
        A.push_back(j);
    }   
  }

  for(auto& a : A) {
    std::cout << a << std::endl;
  }
}

int 
main() {
        
  printBitCombinations(4);

  return 0;
}

- fiska May 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First, I think that your sample output is inconsistent to your description of the problem. If two numbers with the same set bits are supposed to be sorted from low to high value, then it should be:

000, 001, 010, 100, 011, 101, 110, 111 (note that 011 should come before 101).

With that said, I took two approaches. The first, naive approach used the Cartesian product of '01' repeated k times. The resulting list is in ascending order. I then sorted it the list by the number of 1 bits in each number.

def bins_product(k):
    import itertools
    bits = [''.join(b) for b in itertools.product('01', repeat=k)]
    bits.sort(key = lambda x: x.count('1'))
    for x in bits: print x

But that's slow. I'm not even sure what the time complexity is of that code. So, my second sweep was to actually just count in binary up to the 2^k, and then perform the same sort:

def bins_count(k):
    bits = []
    b = 0
    while b < 2**k:
        bits.append(bin(b)[2:].zfill(k))
        b += 1
    bits.sort(key = lambda x: x.count('1'))
    for x in bits: print x

- Nate May 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is an O(1) per number algorithm that outputs these numbers in requested order.
If we can assume that k is <= 64, or we can use python long arithmetic, then we can use "gosper hack". This obviously works in O(1) per number, so the whole algorithm works in O(t) where t is number of items we want to print (e.g. 2^k to print everything)
The idea is in comments

def gosper(n):
    """return smallest number > n with the same number of bits set"""
    # group is first sequence of 1's in n starting from lowest bits
    # 000111110000
    #    ^---^ - this is "group"

    # the idea is simple - take the highest bit in group
    # and move it one position left
    # the rest of the group will go to the right
    # like this:

    # 000111110000
    # turns into
    # 001000001111
    # after another iteration this turns into
    # 001000010111
    # and so forth...

    # lowest_set_bit is the lowest 1 in that group
    # 000111110000
    #        ^ here it is
    lowest_set_bit = ((~n) + 1) & n

    # this points straight before the highest bit
    # 0001110000
    #   ^ here - to the 0
    new_group_head = (lowest_set_bit + n) & (~n)

    # now let's work with what was left on the left
    original_group = n & (new_group_head - 1)
    # remove group old head - it has migrated one bit left
    new_group = original_group ^ (new_group_head / 2)
    # move the tail to the beginning
    new_group /= lowest_set_bit

    # reassemble result
    result = n & ~original_group
    result |= new_group_head
    result |= new_group

    assert result > n
    assert bin(result).count('1') == bin(n).count('1')
    return result

def all_combinations(k):
    yield '0' * k
    mask = (1 << k) - 1
    for num_bits in xrange(1, k + 1):
        n = (1 << num_bits) - 1
        while True:
            yield bin(n)[2:].rjust(k, '0')
            n = gosper(n)
            if n > mask:
                break

k = 5
result = list(all_combinations(k))
print len(result)
assert len(result) == 2 ** k
assert result[-1] == '1' * k

for s in all_combinations(5):
    print s

Example output: ideone.com/FO329N

- emb May 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def getBits(n):
    lim = pow(2,n)
    opt = {}
    for i in range(0,lim):
        temp = bin(i)
        #print temp[temp.index('b')+ 1:]
        temp_int =  int(temp[temp.index('b') + 1:])
        #print y
        y = temp_int
        sum = 0
        while y > 0:
            sum += y % 10
            y = y / 10

        #print temp_int, sum
        val = []
        if sum in opt.keys():
            val = opt[sum]

        val.append(temp_int)
        opt[sum] = val

    for key in opt.keys():
        print key,
        for item in opt[key]:
            print item,
        print

getBits(5)

- Jeevan May 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void driver(int k) {
        for(int i = 0; i<=k;i++) {
            print1s(k,i,new StringBuilder());
        }
    }

    public static void print1s(int k, int ones, StringBuilder prefix) {
        if(ones == 0) {
            for(int i = 0; i<k; i++)prefix.append('0');
            System.out.println(prefix);

            prefix.delete(prefix.length()-k,prefix.length());
            return;
        }

        for(int i = k-ones; i>=0; i--) {
            for(int j = 0;j<i;j++)prefix.append('0');
            prefix.append('1');
            print1s(k-(i+1),ones-1,prefix);

            prefix.delete(prefix.length()-1-i,prefix.length());
        }

    }

- krbchd May 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.career.cup;

import java.util.Arrays;

public class BinaryCodeGenerator {



public static String binary(int data)
{
int r;
StringBuffer s=new StringBuffer();
while(data!=0)
{
r=data%2;
data=data/2;
s=s.append(r);


}

return s.reverse().toString();
}


public static void main(String[] args) {

int n=4;
int l=(int)Math.pow(2, n);
String[] container=new String[l];
String ss=binary(l-1);
int size=ss.length();
String k="";
for(int i=0;i<l;i++)
{
container[i]=BinaryCodeGenerator.binary(i);

if(container[i].length()<size)
{

for(int j=container[i].length();j<size;j++)
{
k=k+0;
}
k=k+container[i];
container[i]=k;
}
k="";
}

System.out.println(Arrays.toString(container));

}

}

- skd May 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.career.cup;

import java.util.Arrays;

public class BinaryCodeGenerator {
	
	
	
	public static String binary(int data)
	{
		int r;
		StringBuffer s=new StringBuffer();
		while(data!=0)
		{
			r=data%2;
			data=data/2;
			s=s.append(r);
			
		
		}
		
		return s.reverse().toString();
	}
	
	
	public static void main(String[] args) {

		int n=4;
		int l=(int)Math.pow(2, n);
		String[] container=new String[l];
		String ss=binary(l-1);
		int size=ss.length();
		String k="";
		for(int i=0;i<l;i++)
		{
			container[i]=BinaryCodeGenerator.binary(i);
			
			if(container[i].length()<size)
			{
				
				for(int j=container[i].length();j<size;j++)
				{
				k=k+0;	
				}
				k=k+container[i];
				container[i]=k;
			}
			k="";
		}
		
		System.out.println(Arrays.toString(container));
		
	}

}

- skd May 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple solution in C++

#include <iostream>
#include <vector>

int bitcount(int aArg) {
  int c = 0; // bit count
  for(; aArg; c++)
    aArg &= aArg -1; // clears the least significat bit

  return c;
}

void printBitCombinations(int K) {
  std::vector<int> A;

  for(int i = 0; i <= K; ++i) {
    for(int j = 0; j < 1 << K; ++j) {
      if(bitcount(j) == i)
        A.push_back(j);
    }   
  }

  for(auto& a : A) {
    std::cout << a << std::endl;
  }
}

int 
main() {
        
  printBitCombinations(4);

  return 0;
}

- fiska May 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CombinationNumberKBits {	
	public static void main(String[] args) {
		printCombinationsKBits(3);
	}

	public static void printCombinationsKBits(int k) {
		if (k <= 0) return;
		
		int pow = new Double(Math.pow(2, k)).intValue();
		int i = 0, j = 0;
		int num = 0;
		List<int[]> r = new ArrayList<>();
		int[] arr = null;		
		
		while (i < pow) {
			num = i;
			j = k-1;
			arr = new int[k];
			while(num > 0 && j >= 0) {
				if ((num & 1) > 0) {
					arr[j] = 1;
				}
				j--;
				num = num >> 1;
			}
			i++;
			r.add(arr);
		}
		
		for (int l = 0; l <= k && !r.isEmpty(); l++) {
			List<int[]> subset = findArraysWithKBits(r, l);						
			printArrays(subset);
			r.removeAll(subset);
		}		
			
	}
	private static List<int[]> findArraysWithKBits(List<int[]> arr, int k) {			
		List<int[]> r = new ArrayList<>();
		for (int[] is : arr) {
			if (countBits(is) == k) {
				r.add(is);
			}
		}
		return r;
	}
	
	public static int countBits(int[] arr) {
		int count = 0;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == 1) {
				count++;
			}
		}
		return count;
	}
	
	public static void printArrays(List<int[]> arr) {
		for (int[] is : arr) {
			System.out.println();
			for (int i = 0; i < is.length; i++) {
				System.out.print(is[i] + " ");	
			}
		}
	}		
}
// ouput:
/*
0 0 0 
0 0 1 
0 1 0 
1 0 0 
0 1 1 
1 0 1 
1 1 0 
1 1 1
*/

- guilhebl May 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A solution in C:

static unsigned
bits_set (unsigned v)
{
    unsigned c;
    for (c=0; v; c++)
        v &= (v-1);
    return c;
}

int
main (int argc, char **argv)
{
    unsigned k = atoi(argv[1]);
    unsigned sz = power(2, k);
    signed *heads = (signed*)malloc(sizeof(signed) * (k+1));
    signed *tails = (signed*)malloc(sizeof(signed) * (k+1));
    signed *nexts = (signed*)malloc(sizeof(signed) * sz);
    signed i, nbits;

    for(nbits=0; nbits<=k; nbits++)
        heads[nbits] = tails[nbits] = -1;

    for(i=1; i<sz; i++) {
        nbits = bits_set(i);
        if (tails[ nbits ] == -1) {
            heads[ nbits ] = i;
            tails[ nbits ] = i;
            nexts[ i ] = -1;
            continue;
        }
        nexts[ tails[nbits] ] = i;
        nexts[ i ] = -1;
        tails[ nbits ] = i;
    }

   for(nbits=1; nbits<=k; nbits++) {
        printf("%d bits: ", nbits);
        for(i=heads[nbits]; i>0; i=nexts[i])
            printf("%d ", i);
        printf("\n");
    }

    return 0;
}

- shauli May 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just a thought correct me if I am wrong.

Will take an example and try to explain, If input is 4

0 bits set elements : 0
only 1 bit set elements : 1 , 2 , 4 , 8 ( powers of 2 < pow(2,4))
only 2 bit set elements : 3, 5, 6 , 9, 10 , 12 (sum of 2 1 bit set numbers in the above list )
only 3 bit set elements : 7 , 11, 13, 14 ( sum of above list and power of 2 elements)
All bits set ( 4 in this case) elements : 15 ( pow(2,4) -1 )


not a program but just an approach dont really have a working code ready , will try and post it when it is done.

I suppose the worst case would be O(m^2) where m would be maximum elements in a m bits set element array.

- Shashi June 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test;

import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Scanner;

public class GoogleBinary {

	@SuppressWarnings("resource")
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
        int totalOfBites = in.nextInt();
        
        LinkedHashSet<String> arrayofBits = new LinkedHashSet<String>(); 
        
        solution (arrayofBits,  totalOfBites );
        
        //System.out.println("arrayofBites.size "+arrayofBites.size());
			
        Iterator<String> spacesofBits = arrayofBits.iterator();
        
    	while ( spacesofBits.hasNext()){
    		
    		String listIntegers= spacesofBits.next();
    		
    		System.out.println(listIntegers);
    		
    	}

	}
	
	private static void solution (LinkedHashSet<String> arrayofBits, int totalOfBits ){
		
		int numberofBitInternal = 0, lengthofNumberOfBits=0,
				counterIndexBite=totalOfBits;
		
		String binaryNumberofDecimal = new String();
		int totalofLines = (int) Math.pow(2, totalOfBits);
		
		while (numberofBitInternal <= (totalofLines-1) ){
			
			lengthofNumberOfBits = Integer.toBinaryString(numberofBitInternal).length();
			counterIndexBite = lengthofNumberOfBits;
			binaryNumberofDecimal = Integer.toBinaryString(numberofBitInternal);
			//System.out.println("toBinaryString "+ Integer.toBinaryString(numberofBitInternal));
			//System.out.println("numberofBiteInternal "+numberofBiteInternal);
			
			if (lengthofNumberOfBits == totalOfBits ){
				
				arrayofBits.add(binaryNumberofDecimal);
				
			}else{
				
				StringBuilder arrayWithBits = new StringBuilder();
				
				while (counterIndexBite < totalOfBits ){
					
						arrayWithBits.append(0);
						counterIndexBite++;
					
				}
				
				arrayWithBits.append(binaryNumberofDecimal);
				
				arrayofBits.add(arrayWithBits.toString());
				
			}
			
			numberofBitInternal++;
			
		}					
		
	}

}

- Israel Lopez June 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test;

import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Scanner;

public class GoogleBinary {

	@SuppressWarnings("resource")
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
        int totalOfBites = in.nextInt();
        
        LinkedHashSet<String> arrayofBits = new LinkedHashSet<String>(); 
        
        solution (arrayofBits,  totalOfBites );
        
        //System.out.println("arrayofBites.size "+arrayofBites.size());
			
        Iterator<String> spacesofBits = arrayofBits.iterator();
        
    	while ( spacesofBits.hasNext()){
    		
    		String listIntegers= spacesofBits.next();
    		
    		System.out.println(listIntegers);
    		
    	}

	}
	
	private static void solution (LinkedHashSet<String> arrayofBits, int totalOfBits ){
		
		int numberofBitInternal = 0, lengthofNumberOfBits=0,
				counterIndexBite=totalOfBits;
		
		String binaryNumberofDecimal = new String();
		int totalofLines = (int) Math.pow(2, totalOfBits);
		
		while (numberofBitInternal <= (totalofLines-1) ){
			
			lengthofNumberOfBits = Integer.toBinaryString(numberofBitInternal).length();
			counterIndexBite = lengthofNumberOfBits;
			binaryNumberofDecimal = Integer.toBinaryString(numberofBitInternal);
			//System.out.println("toBinaryString "+ Integer.toBinaryString(numberofBitInternal));
			//System.out.println("numberofBiteInternal "+numberofBiteInternal);
			
			if (lengthofNumberOfBits == totalOfBits ){
				
				arrayofBits.add(binaryNumberofDecimal);
				
			}else{
				
				StringBuilder arrayWithBits = new StringBuilder();
				
				while (counterIndexBite < totalOfBits ){
					
						arrayWithBits.append(0);
						counterIndexBite++;
					
				}
				
				arrayWithBits.append(binaryNumberofDecimal);
				
				arrayofBits.add(arrayWithBits.toString());
				
			}
			
			numberofBitInternal++;
			
		}					
		
	}

}

- Anonymous June 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void kbitGenerator(int[] arr, int k, int i) {
        if (i < k) {
            for (int m = 0; m <= 1; m++) {
                arr[i] = m;
                kbitGenerator(arr, k, i + 1);
            }
        } else {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(arr[j]);
            }
            System.out.println();
        }
    }

- Naresh June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void kbitGenerator(int[] arr, int k, int i) {
        if (i < k) {
            for (int m = 0; m <= 1; m++) {
                arr[i] = m;
                kbitGenerator(arr, k, i + 1);
            }
        } else {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(arr[j]);
            }
            System.out.println();
        }
    }

- Naresh June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void kbitGenerator(int[] arr, int k, int i) {
if (i < k) {
for (int m = 0; m <= 1; m++) {
arr[i] = m;
kbitGenerator(arr, k, i + 1);
}
} else {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[j]);
}
System.out.println();
}
}

- Naresh June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class MyArrayItem {
        public int data;
        public int next;

        public MyArrayItem(int numOfCombinations) {
                this.data = -1;
                this.next = numOfCombinations;
        }
}

MyArrayItem[] Arr;


public void printAllBitCombinations(int k) {
        final int numOfCombinations = (int)Math.pow(2.0,(double)k);

        Arr = new MyArrayItem[numOfCombinations];
        for(int i=0; i<numOfCombinations; i++)
                Arr[i] = new MyArrayItem(numOfCombinations);

        ArrayList<Integer> headlist = new ArrayList<Integer>();


        System.out.println("input "+ k + "  has " + numOfCombinations + "  combinations to show");
        int combinationsToShow = numOfCombinations;

        // Combination with All 0's is only 0
        Arr[0].data = 0;
        combinationsToShow--;
        headlist.add(0,0);

        System.out.println(" 0 bits set list ");
        int startIdxToShow = headlist.get(0);
        do {
                System.out.println(" " + Arr[startIdxToShow].data + " " );
        } while(Arr[startIdxToShow].next != numOfCombinations);



        // Combination with only 1 bit set are powers of 2 
        Arr[1].data = 1;
        headlist.add(1,1);

        int temp = 1;
        for (int i=1; i<k; i++) {
                int t = temp * 2;
                Arr[temp].next = t;
                Arr[t].data = t;
                temp = t;
        }

        System.out.println(" 1 bits set list ");
        startIdxToShow = headlist.get(1);
        do {
                System.out.println(" " + Arr[startIdxToShow].data + " " );
                startIdxToShow = Arr[startIdxToShow].next;
        } while(startIdxToShow != numOfCombinations);

       // Combination with 2 bits set is sum of 2 digits with 1 bit set
        int n=2;
        while(n<k) {
                int a = headlist.get(n-1); //previous list
                int b = headlist.get(1); // single bit list

                for (int i=0; i<k; i++) {
                        int t = a + b;
                        if (Arr[t].data == -1)
                                break;
                        b = Arr[b].next;
                }

                int head = sumIncreasing(a,b,numOfCombinations);
                headlist.add(n,head);

                System.out.println(n +" bits set list ");
                startIdxToShow = headlist.get(n);
                do {
                        System.out.println(" " + Arr[startIdxToShow].data + " " );
                        startIdxToShow = Arr[startIdxToShow].next;
                } while(startIdxToShow != numOfCombinations);

                n++;
        }

        // For All bits set 
        Arr[numOfCombinations-1].data = numOfCombinations - 1;
        headlist.add(k,numOfCombinations - 1);

        System.out.println(k +" bits set list ");
        System.out.println(" " + Arr[numOfCombinations-1].data + " " );

}

int sumIncreasing(int a, int b, int numOfCombinations) {
        int t = a + b;

        if (a == b)
                return numOfCombinations;

        if (Arr[t].data != -1)
                return numOfCombinations;

        int l1 =numOfCombinations, l2 =numOfCombinations;
        if ((Arr[b].next < numOfCombinations) && (a+Arr[b].next < numOfCombinations))
                l1 = sumIncreasing(a,Arr[b].next,numOfCombinations);
        if (b+Arr[a].next < numOfCombinations)
                l2 = sumIncreasing(Arr[a].next,b,numOfCombinations);

        Arr[t].data = t;
        if (l2 < l1) {
                Arr[t].next = l2;
                int temp = l2;
                while (Arr[temp].next != numOfCombinations) {
                        temp = Arr[temp].next;
                }
                Arr[temp].next = l1;
        } else if (l1 < l2) {
                Arr[t].next = l1;
                int temp = l1;
                while (Arr[temp].next != numOfCombinations) {
                        temp = Arr[temp].next;
                }
                Arr[temp].next = l2;
        }

        return t;
}

I am only printing the decimal numbers herewith increasing number of bits.
To print in binary format you would need a function to convert from decimal to binary string of fixed size

I am not sure of the exact complexity, think it is O(k^2).
Could someone confirm / correct me here. Also any suggestions would be great

- Anonymous June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class MyArrayItem {
        public int data;
        public int next;

        public MyArrayItem(int numOfCombinations) {
                this.data = -1;
                this.next = numOfCombinations;
        }
}

MyArrayItem[] Arr;


public void printAllBitCombinations(int k) {
        final int numOfCombinations = (int)Math.pow(2.0,(double)k);

        Arr = new MyArrayItem[numOfCombinations];
        for(int i=0; i<numOfCombinations; i++)
                Arr[i] = new MyArrayItem(numOfCombinations);

        ArrayList<Integer> headlist = new ArrayList<Integer>();


        System.out.println("input "+ k + "  has " + numOfCombinations + "  combinations to show");
        int combinationsToShow = numOfCombinations;

        // Combination with All 0's is only 0
        Arr[0].data = 0;
        combinationsToShow--;
        headlist.add(0,0);

        System.out.println(" 0 bits set list ");
        int startIdxToShow = headlist.get(0);
        do {
                System.out.println(" " + Arr[startIdxToShow].data + " " );
        } while(Arr[startIdxToShow].next != numOfCombinations);



        // Combination with only 1 bit set are powers of 2 
        Arr[1].data = 1;
        headlist.add(1,1);

        int temp = 1;
        for (int i=1; i<k; i++) {
                int t = temp * 2;
                Arr[temp].next = t;
                Arr[t].data = t;
                temp = t;
        }

        System.out.println(" 1 bits set list ");
        startIdxToShow = headlist.get(1);
        do {
                System.out.println(" " + Arr[startIdxToShow].data + " " );
                startIdxToShow = Arr[startIdxToShow].next;
        } while(startIdxToShow != numOfCombinations);

       // Combination with 2 bits set is sum of 2 digits with 1 bit set
        int n=2;
        while(n<k) {
                int a = headlist.get(n-1); //previous list
                int b = headlist.get(1); // single bit list

                for (int i=0; i<k; i++) {
                        int t = a + b;
                        if (Arr[t].data == -1)
                                break;
                        b = Arr[b].next;
                }

                int head = sumIncreasing(a,b,numOfCombinations);
                headlist.add(n,head);

                System.out.println(n +" bits set list ");
                startIdxToShow = headlist.get(n);
                do {
                        System.out.println(" " + Arr[startIdxToShow].data + " " );
                        startIdxToShow = Arr[startIdxToShow].next;
                } while(startIdxToShow != numOfCombinations);

                n++;
        }

        // For All bits set 
        Arr[numOfCombinations-1].data = numOfCombinations - 1;
        headlist.add(k,numOfCombinations - 1);

        System.out.println(k +" bits set list ");
        System.out.println(" " + Arr[numOfCombinations-1].data + " " );

}

int sumIncreasing(int a, int b, int numOfCombinations) {
        int t = a + b;

        if (a == b)
                return numOfCombinations;

        if (Arr[t].data != -1)
                return numOfCombinations;

        int l1 =numOfCombinations, l2 =numOfCombinations;
        if ((Arr[b].next < numOfCombinations) && (a+Arr[b].next < numOfCombinations))
                l1 = sumIncreasing(a,Arr[b].next,numOfCombinations);
        if (b+Arr[a].next < numOfCombinations)
                l2 = sumIncreasing(Arr[a].next,b,numOfCombinations);

        Arr[t].data = t;
        if (l2 < l1) {
                Arr[t].next = l2;
                int temp = l2;
                while (Arr[temp].next != numOfCombinations) {
                        temp = Arr[temp].next;
                }
                Arr[temp].next = l1;
        } else if (l1 < l2) {
                Arr[t].next = l1;
                int temp = l1;
                while (Arr[temp].next != numOfCombinations) {
                        temp = Arr[temp].next;
                }
                Arr[temp].next = l2;
        }

        return t;
}

I am only printing the decimal numbers here.
To print in binary format you would need a function to convert from decimal to binary string of fixed size

Also not sure of complexity, think it is O(k^2) . Please confirm / correct me here.

- Anonymous June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class MyArrayItem {
        public int data;
        public int next;

        public MyArrayItem(int numOfCombinations) {
                this.data = -1;
                this.next = numOfCombinations;
        }
}

MyArrayItem[] Arr;


public void printAllBitCombinations(int k) {
        final int numOfCombinations = (int)Math.pow(2.0,(double)k);

        Arr = new MyArrayItem[numOfCombinations];
        for(int i=0; i<numOfCombinations; i++)
                Arr[i] = new MyArrayItem(numOfCombinations);

        ArrayList<Integer> headlist = new ArrayList<Integer>();


        System.out.println("input "+ k + "  has " + numOfCombinations + "  combinations to show");
        int combinationsToShow = numOfCombinations;

        // Combination with All 0's is only 0
        Arr[0].data = 0;
        combinationsToShow--;
        headlist.add(0,0);

        System.out.println(" 0 bits set list ");
        int startIdxToShow = headlist.get(0);
        do {
                System.out.println(" " + Arr[startIdxToShow].data + " " );
        } while(Arr[startIdxToShow].next != numOfCombinations);



        // Combination with only 1 bit set are powers of 2 
        Arr[1].data = 1;
        headlist.add(1,1);

        int temp = 1;
        for (int i=1; i<k; i++) {
                int t = temp * 2;
                Arr[temp].next = t;
                Arr[t].data = t;
                temp = t;
        }

        System.out.println(" 1 bits set list ");
        startIdxToShow = headlist.get(1);
        do {
                System.out.println(" " + Arr[startIdxToShow].data + " " );
                startIdxToShow = Arr[startIdxToShow].next;
        } while(startIdxToShow != numOfCombinations);

       // Combination with 2 bits set is sum of 2 digits with 1 bit set
        int n=2;
        while(n<k) {
                int a = headlist.get(n-1); //previous list
                int b = headlist.get(1); // single bit list

                for (int i=0; i<k; i++) {
                        int t = a + b;
                        if (Arr[t].data == -1)
                                break;
                        b = Arr[b].next;
                }

                int head = sumIncreasing(a,b,numOfCombinations);
                headlist.add(n,head);

                System.out.println(n +" bits set list ");
                startIdxToShow = headlist.get(n);
                do {
                        System.out.println(" " + Arr[startIdxToShow].data + " " );
                        startIdxToShow = Arr[startIdxToShow].next;
                } while(startIdxToShow != numOfCombinations);

                n++;
        }

        // For All bits set 
        Arr[numOfCombinations-1].data = numOfCombinations - 1;
        headlist.add(k,numOfCombinations - 1);

        System.out.println(k +" bits set list ");
        System.out.println(" " + Arr[numOfCombinations-1].data + " " );

}

int sumIncreasing(int a, int b, int numOfCombinations) {
        int t = a + b;

        if (a == b)
                return numOfCombinations;

        if (Arr[t].data != -1)
                return numOfCombinations;

        int l1 =numOfCombinations, l2 =numOfCombinations;
        if ((Arr[b].next < numOfCombinations) && (a+Arr[b].next < numOfCombinations))
                l1 = sumIncreasing(a,Arr[b].next,numOfCombinations);
        if (b+Arr[a].next < numOfCombinations)
                l2 = sumIncreasing(Arr[a].next,b,numOfCombinations);

        Arr[t].data = t;
        if (l2 < l1) {
                Arr[t].next = l2;
                int temp = l2;
                while (Arr[temp].next != numOfCombinations) {
                        temp = Arr[temp].next;
                }
                Arr[temp].next = l1;
        } else if (l1 < l2) {
                Arr[t].next = l1;
                int temp = l1;
                while (Arr[temp].next != numOfCombinations) {
                        temp = Arr[temp].next;
                }
                Arr[temp].next = l2;
        }

        return t;
}


I am only printing the decimal numbers here. 
To print in binary format you would need a function to convert from decimal to binary string of fixed size

Also not sure of complexity, think it is O(k^2) .  Please confirm / correct me here.

- Anonymous June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple recursive solution:

void print_nums(int n) {
	for(q = 0; q < n; q++)
		print_intern(0, 0, 0, q, n);
}

void print_intern(int x, int next_pos, int bits, int cur_len, int total_len) {
	if (bits >= cur_len) {
		printf("%d\n", x);
		return;
	}

	for(j = next_pos; j < total_len; j++) {
		y = set_bit(x, j);
		print_intern(y, j + 1, bits + 1, cur_len, total_len);
	}
}

- Mukesh June 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Python >= 2.6 itertools has a handy combinations method that'll emit r-length subsequences in lexicographic sort order. Using itertools.chain by increasing the number of bits sets creates a space-constant generator.

Arrays are indexed 0 from the left, bits indexed 0 from the right, so we call reversed().

from itertools import chain
from itertools import combinations

def BitsSet(k):
    return chain.from_iterable(combinations(range(k), count) for count in range(k+1))

def PrintBits(k):
    for bits in BitsSet(k):
        print(''.join(reversed('1' if idx in bits else '0' for idx in range(k)))

- Anonymous June 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void setBits(int k) {
		int n = 0, t = 0, l = k;
		while (n < Math.pow(2, k) - 1) {
			for (int i = 0; i < l; i++) {
				t = n | 1 << i;
				System.out.println(t);
			}
			l--;
			n = t;
		}
	}

- Anonymous June 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You are correct with the thought. For getting the number of elements with only ! bit set is similar to knowing the number of ways we can pick one box out of k boxes. This gives us the following formula: (n be the num of set bits)
k! / (n! * (k-n)!)
Thus, if k=4, n=0 => 1 element
if k=4, n=1 => 4!/3!*1! = 4 elements
if k=4, n=2 => 4!/2!*2! = 6 elements
if k=4, n=3 => 4!1!*3! = 4 elements
if k=4, n=4 => 4!/4!*0! = 1 element

That way I think we can get the total number of elements for every set bit reserve space accordingly.

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

#include "stdafx.h"
#include <vector>

void shiftBits(unsigned long number, int shiftStartIndex, int shiftEndIndex) {
    if(shiftStartIndex < 0){
        return;
    }
    if (( (1 << shiftStartIndex) && number )== 0){
        return;
    }
    for(int i = shiftStartIndex; i < shiftEndIndex - 1; ++i) {
        unsigned long mask = ~(1 << i);
        number = number & mask;
        number = number | ( 1 << (i + 1) );
        printf("%d ", number);
        shiftBits(number, shiftStartIndex - 1, i + 1);
    }
}

void insertBits(int bitCount){
    unsigned long number = 0;
    printf("%d ", number);
    for(int i = 0; i< bitCount;++i) {
        number = number | (1 << i);
        printf("%d ", number);
        shiftBits(number, i, bitCount);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
	int bits;
	scanf_s("%d", &bits);
	insertBits(bits);
	getchar();
	getchar();
	return 0;
}

- Sunil June 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class EnumKBitSet {
	char[] ch=null;
	public void enumKBitSet(int K)
	{
		ch = new char[K];
		for (int i=0; i < ch.length; i++) ch[i]='0';
		for (int k =0; k <= ch.length ; k++)
			enumKBit(k, ch, ch.length);
	}
	private void enumKBit(int k, char[] ch, int pos)
	{
		int n = ch.length-1;
		if (k==0) 
		{
			System.out.print(new String(ch)+" ");
			return;
		}  
		for (int p=n-(k-1); p > n-pos; p--)
		{
			ch[p]='1';
			enumKBit(k-1, ch, n-p);
			ch[p]='0';
		}
	}
	public static void main(String argv[])
	{
		EnumKBitSet ekbs = new EnumKBitSet();
		ekbs.enumKBitSet(4);
	}
}
// k = 3
// 000, 001, 010, 100, 011, 101, 110, 
// k = 4
// 0000 0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111

- Robert June 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class BitSet {

    public static void main(String[] args) {
	BitSet b = new BitSet();
	b.generateBit(3);
    }

    public void generateBit(int k) {
	for (int i = 0; i <= k; i++) {
	    generateBitSet(k, i, "");
	}
    }

    public void generateBitSet(int size, int d, String suffix) {
	if (d < 0) {
	    return;
	}
	if (size <= 0) {
	    System.out.println(suffix);
	} else if (size == d) {
	    generateBitSet(size - 1, d - 1, "1" + suffix);
	} else {
	    generateBitSet(size - 1, d - 1, "1" + suffix);
	    generateBitSet(size - 1, d, "0" + suffix);
	}
    }

}

- darklight July 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Stack<Integer> stack = new Stack<>();
stack.push(0);
while(!stack.isEmpty()) {
Stack newStack = new Stack<>();
while(!stack.isEmpty()) {
int c = stack.pop();
for(int i = 0; i < n; i++) {
int toAdd = (c | (1 << i));
if(toAdd != c) {
newStack.push(toAdd);
System.out.println(Integer.toBinaryString(toAdd));
} else {
break;
}
}
}
stack = newStack;
}

- Kirito July 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Solution {

public static void main(String [] args) {

printK(4);

System.out.println();

printK(5);

}

public static void printK(int k) {
for (int i = 0; i <= k; i++) {
printPrefix("", i, k);
}
}

public static void printPrefix(String prefix, int one, int length) {

if (one == 0) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("0");
}
System.out.println();
} else if (one == length) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("1");
}
System.out.println();
} else if (length > one) {
String newPrefix = prefix + "0";
printPrefix(newPrefix, one, length-1);

newPrefix = prefix + "1";
printPrefix(newPrefix, one-1, length-1);
}

}

}

- ugurdonmez87 July 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Solution {

    public static void main(String [] args) {

        printK(4);

        System.out.println();

        printK(5);

    }

    public static void printK(int k) {
        for (int i = 0; i <= k; i++) {
            printPrefix("", i, k);
        }
    }

    public static void printPrefix(String prefix, int one, int length) {

        if (one == 0) {
            System.out.print(prefix);
            for (int i = 0; i < length; i++) {
                System.out.print("0");
            }
            System.out.println();
        } else if (one == length) {
            System.out.print(prefix);
            for (int i = 0; i < length; i++) {
                System.out.print("1");
            }
            System.out.println();
        } else if (length > one) {
            String newPrefix = prefix + "0";
            printPrefix(newPrefix, one, length-1);

            newPrefix = prefix + "1";
            printPrefix(newPrefix, one-1, length-1);
        }

    }

}

- ugurdonmez87 July 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Code in Java. Complexity of the solution is k * 2 ^ k.

public static void main(String[] args) {
		int k = 4;
		for (int i = 0; i <= k; i++)
			Func(k, 0, "", i);
	}
	
	public static void Func(int k, int ones, String prefix, int max_ones)
	{
		if (prefix.length() == k)
		{
			if (ones == max_ones)
				System.out.println(prefix);
		}
		else {
				Func(k, ones, prefix + "0", max_ones);
				if (ones < max_ones)
				{
					Func(k, ones + 1, prefix + "1", max_ones);
				}
		}
	}

- Akash Singh August 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Solution {

    public static void main(String [] args) {

        printK(4);

        System.out.println();

        printK(5);

    }

    public static void printK(int k) {
        for (int i = 0; i <= k; i++) {
            printPrefix("", i, k);
        }
    }

    public static void printPrefix(String prefix, int one, int length) {

        if (one == 0) {
            System.out.print(prefix);
            for (int i = 0; i < length; i++) {
                System.out.print("0");
            }
            System.out.println();
        } else if (one == length) {
            System.out.print(prefix);
            for (int i = 0; i < length; i++) {
                System.out.print("1");
            }
            System.out.println();
        } else if (length > one) {
            String newPrefix = prefix + "0";
            printPrefix(newPrefix, one, length-1);

            newPrefix = prefix + "1";
            printPrefix(newPrefix, one-1, length-1);
        }
    }
}

- ugurdonmez87 August 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution

public void printK(int k) {
        int N = (int) Math.pow(2,k);
        for(int i = 0; i < N; ++i) {
            String s = "";
            for(int j = 0; j < k; ++j) {
                s = String.valueOf(i >> j & 0x1) + s;
            }
            System.out.println(s);
        }
    }

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

Basically this is the same as printing out all of the binary representation of numbers from 0 to 2^k.

public void printK(int k) {
        int N = (int) Math.pow(2,k);
        for(int i = 0; i < N; ++i) {
            String s = "";
            for(int j = 0; j < k; ++j) {
                s = String.valueOf(i >> j & 0x1) + s;
            }
            System.out.println(s);
        }
    }

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

import java.util.*;

public class BitSetSorter {

    public static void getAllBitSets(int k) {
	Set<Integer> currBitSet = new HashSet<>();
	currBitSet.add(0);
	printBitSet(currBitSet, k);
	currBitSet.remove(0);
	int num = 1;
	for (int i = 0; i < k; i++) {
	    currBitSet.add(num);
	    num <<= 1;
	}
	for (int i = 2; i <= k; i++) {
	    printBitSet(currBitSet, k);
	    Set<Integer> nextBitSet = new HashSet<>();
	    for (int n : currBitSet) {
		for (int m : currBitSet) {
		    if (n != m) {
			nextBitSet.add(n | m);
		    }
		}
	    }
	    currBitSet = nextBitSet;
	}
    }

    public static void printBitSet(Set<Integer> bitset, int len) {
	for (int n : bitset) {
	    System.out.println(String.format("%" + len + "s",
					     Integer.toBinaryString(n))
			       .replace(' ', '0'));
	}
    }

    public static void main(String[] args) {
	getAllBitSets(4);
    }
    
}

- Al Dab October 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this problem not same as just printing integers from 0 to 2^(k+1) - 1 ? 0 will have zero 1 bits and 2^(k+1) - 1 will have k 1 bits ?

- Anonymous November 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def print_padded_binaries(n):
    format_str = "{0:{fill}" + str(n) + "b}"
    for i in xrange(2**n):
        print format_str.format(i, fill='0')

print_padded_binaries(3)

- Nitish Garg January 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def convert_num_to_binary(num):
k=0
s=[]
if num==0:
return '000'
while num>0:
rem=num%2
s.append(rem)
num=num/2
str1=''
for i in range(len(s)-1,-1,-1):
str1+=str(s[i])
return str1

def set_k_bits(k):
limit=2**k
num_list=[]
for i in range(limit):
bits_req = 0
binary_num = convert_num_to_binary(i)
if len(binary_num)<k:
bits_req=k-len(binary_num)
num_list.append('0'*bits_req+binary_num)
if binary_num.count('1')==k:
break;
return ','.join(num_list)

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

In Python:

def convert_num_to_binary(num):
k=0
s=[]
if num==0:
return '000'
while num>0:
rem=num%2
s.append(rem)
num=num/2
str1=''
for i in range(len(s)-1,-1,-1):
str1+=str(s[i])
return str1

def set_k_bits(k):
limit=2**k
num_list=[]
for i in range(limit):
bits_req = 0
binary_num = convert_num_to_binary(i)
if len(binary_num)<k:
bits_req=k-len(binary_num)
num_list.append('0'*bits_req+binary_num)
if binary_num.count('1')==k:
break;
return ','.join(num_list)

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

void printBin(int i) {
    if(i <= 0) {
        cout << 0 << endl;
    }

    while(i) {
        cout << (i & 1);
        i >>= 1;
    }
    cout << endl;
}

void print(int i) {
    if(i == 0) {
        cout << i << endl;
        return;
    }

    print(i - 1);
    printBin(i);
}

int main() {

    int K = 3;
    int res = (1 << K) - 1; // for K = 3, res == 1000 - 1 == 111;

    print(res);

    return 0;
}

- Ololoshka May 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

In Java

public static void printBinaryKBits(int k) {
		int length = (int) Math.pow(2, k);
		
		for(int i = 0; i < length; i++) {
			System.out.println(Integer.toBinaryString(i));
		}
	}

- Anonymous May 30, 2016 | 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