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

3 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

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up