Goldman Sachs

www.goldmansachs.com
Engaged Employer

## Interview Question

Summer Analyst Interview New York, NY

# Given an array with only binary numbers, ex

. 110110101, sort it in better than NlogN. You have two integers or pointers, and that is all that's allowed for space complexity.
Tags:

0

Easy question asked from the two managers. Pointer to start and end of array. If P1 = 1 & P2 = 0, swap the two, and progress both pointers towards the center. Runs in N time.

Interview Candidate on Feb 16, 2013
0

I would just use stl container like deque to push front 0 and back 1. Or one can simply count number of 1 and 0 and create array like that. I don't understand how the swap algorithm presented by above would work.

thexesus on Feb 17, 2013
0

@thexesus

Bucket sort has space complexity of N. Swap answer works.

GS on Feb 17, 2013
0

int x = 0;
for(int y = 0; y < array.length; y++) {

if( array[y] ==0 ) {

array[x] = array[x] ^ 0;
array[y] = array[y] ^ 0;
x++;
}
}

Complexity is N and only two integers used

Anonymous on Jan 29, 2015