Goldman Sachs Interview Question: Given an array with only bina... | Glassdoor

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.
technical, analytical, algorithm, sort

Interview Answer

4 Answers


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

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


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

GS on Feb 17, 2013

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;

Complexity is N and only two integers used

Anonymous on Jan 29, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.