Goldman Sachs

  www.goldmansachs.com
  www.goldmansachs.com

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, Sign In or Sign Up.