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

Interview Answer

4 Answers

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.