## Microsoft Interview Question

• 3

Country: India
Interview Type: In-Person

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

Bucketize numbers based on the number of bits set on them. Then sort each of the buckets individually in normal sorting fashion and then just print them with 0-32 bucket. This avoid repeated computation of the set bits in numbers and also potentially reduces sorting time as each bucket could be as small as initial set /32, but of course not in place.

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

Replace number n by (number_of_bits(n), n). Now do a lexicographic sort using the tuples.

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

Righto! And you probably don't need the replacement.

You can do it in-place with quicksort, and change the compare function to compute the tuple on the fly.

Of course, that would cause a hit on the time (repeatedly computing number_of_bits for the same number), but the space consumption would be lower.

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

One interesting thing that can be done is having a hashmap inside the compare function. Then we can memoize the results and avoid repeated computation. Although it does require more space.

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

1. traverse through the number, for each number, reset the lowest bit using n & (n - 1), if the number becomes zero, append it to the result list.
2. And then traverse through the number again, if the number is not zero, do the same operation.
3. repeat 2 until the result list length equals to n

``````def sort_by_bits2(n):
array = [x + 1 for x in range(n)]
result = []
while len(result) != n:
for i in range(len(array)):
if array[i] != 0:
array[i] &= (array[i] - 1)
if array[i] == 0:
result.append(i + 1)
return result``````

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

by gnahzy

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

Good Solution. But I am still wondering is there possibility to optimize it further.

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

This is O(number of 1's in the range). Asymptotically, it can't be better than this, but yea, a bit of code tuning can happen.

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

it will take O(n*log(n)*log(d)) time, and can't be done in less number of operation, you apply any sort : heap sort, merge sort, quick sort, etc., you always have to compare two element, not two element are not of single length, their length can be up to log(d), so every comparison will take log(d) operation, and all comparison sort take O(n*log(n)) comparison, now you can calculate the complexity

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

Traverse the numbers from 1 to n... whenever you see a number that is a power of 2 (including 2^0 = 1), output it... now traverse again, and print all the numbers that are not powers of 2, in the same order...

for example, if n = 8, the output would be 1, 2, 4, 8, 3, 5, 6, 7

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

consider n=10. So according to output should be:
1,2,4,8,3,5,6,7,9,10 which is incorrect.
In this Case, Output should be
1,2,3,4,3,5,6,9,10,7

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

hmmm... you mean 1, 2, 4, 8, 3, 5, 6 , 9, 10, 7

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

Yes, my mistake.
Output should be:
1, 2, 4, 8, 3, 5, 6 , 9, 10, 7

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

your approach may be wrong. let n=16. 12 has 2 set bits and 11 has 3.

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

``````def sort_by_bits(n):
array = sorted([(get_bit_number(x + 1), x + 1) for x in range(n)])
return [x for x in array]

def get_bit_number(n):
result = 0
while n != 0:
n = n & (n - 1)
result += 1
return result``````

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

int maxNumOfBits=-1
for i=1 to n
maxNumOfBits=max(maxNumOfBits,numOfBits(num[i]));
//create an array of linkedLists, the size will for the list is maxNumOfBits
for i=1 to n
list[numOfBits(num[i])].appendToTheEnd(num[i]);

for n=1 to n
print list[n];

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

int maxNumOfBits=-1
for i=1 to n
maxNumOfBits=max(maxNumOfBits,numOfBits(num[i]));
//create an array of linkedLists, the size will for the list is maxNumOfBits
for i=1 to n
list[numOfBits(num[i])].appendToTheEnd(num[i]);

for m=maxNumOfBits to 1
print list[m];

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

Could be done effectively and easily with the use of heaps.
Rule should be to use # of bits and if bits are equal, then base 10 value.

First heapify and then dismantle heap. All done.

O(nlog(n).

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

n(log n) solution due to heapsort.

``````public class SortBits {

public static void main(String args[]) {
SortBits t = new SortBits();
t.sort(5);
}

void sort(int n) {
Heap heap = new Heap(n);
for(int i = 1; i <= n; i++) {
Num num = new Num();
num.value = i;
num.numBits = getNumBits(i);
heap.insert(num);
}
for(int i = 1; i <= n; i++) {
Num num = heap.extractMin();
System.out.println(num.numBits+", "+num.value);
}
}
int getNumBits(int n) {
int count = 0;
while(n>0) {
if(n%2==1)
count++;
n = n/2;
}
return count;
}
}

class Num {
public int numBits;
public int value;
}

class Heap {
int s;
int size;
Num[] array;

public Heap(int size) {
this.size = size;
s = 0;
array = new Num[size];
}

public void insert(Num num) {
array[s] = num;
s++;
bubbleUp(s-1);
}

public Num extractMin() {
Num num = array;
s--;
array = array[s];
bubbleDown(0);
return num;
}

void bubbleUp(int i) {
if(i<=0)
return;
if(i>=s)
return;
if(isSmaller(i, getParent(i))) {
swap(i, getParent(i));
bubbleUp(getParent(i));
}
}
void swap(int i, int j) {
Num temp = array[i];
array[i] = array[j];
array[j] = temp;
}
int getParent(int i) {
return i/2;
}
int getYoungChild(int i) {
return 2*i+1;
}
void bubbleDown(int i) {
if(i<0)
return;
if(i>=s)
return;
int c1 = getYoungChild(i);
int c2 = c1+1;
int minIndex = 0;
if(c1>=s)
return;
if(c1==s-1)
minIndex = c1;
else {
if(isSmaller(c1, c2))
minIndex = c1;
else
minIndex = c2;
}

if(isSmaller(minIndex, i)) {
swap(minIndex, i);
bubbleDown(minIndex);
}

}
boolean isSmaller(int i, int j) {
if(array[i].numBits < array[j].numBits)
return true;
else if(array[i].numBits > array[j].numBits)
return false;
else if(array[i].value <= array[j].value)
return true;
else
return false;
}
}``````

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

for i = 1 to n:
put i into a bucket_(#bits_in_i) (a queue that you would add i to )
then result = read bucket_1, bucket_2,...bucket_(ceiling of log_2 (n))

bucket_(#bits_in_i) is a queue that has those numbers i that have #bits_in_i set bits
I think that this is O(n)

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

generate the numbers with i set bits not greater than n from 2 ^ i - 1

ideone.com/qajp85

``````public int[] sort(int n)
{
int[] a = new int[n];
int k = 0;
for(int i = 1; i <= n; i = ((i + 1) << 1) - 1)
for(int j = i; j <= n; j = next(j))
a[k++] = j;
return a;
}

private int next(int n)
{
//n       1 0001 1100
//s       0 0000 0100 n & (-n)
//r       1 0010 0000 n + s
//ones    0 0011 1100 n ^ r
//ones    0 0000 0011 (ones >> 2) / s
//return  1 0010 0011 r + ones
int smallest = n & (-n);
int ripple = n + smallest;
int ones = n ^ ripple;
ones = (ones >> 2) / smallest;
return ripple + ones;
}``````

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

Below is a linear algorithm

``````void sortOnBits(int N) {
int maxBits = ceil(log N);
for (int i=1; i<=maxBits; i++) {
while(temp<N) {
cout << temp;
temp=temp<<1;
}
}
}``````

Logic:
- Print all numbers that have one bit set, then two bits and so on
- To get the numbers in increasing order which have the same number of bits set, we start by initializing the least significant bits, and then keep shifting right until N

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

Please ignore this solution, I just realized my mistake.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.