Goldman Sachs
3.7 of 5 1,591 reviews
www.goldmansachs.com New York, NY 5000+ Employees

Goldman Sachs Summer Analyst Interview Question

I interviewed in New York, NY and was asked:
"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
Add Tags [?]
Answer Flag Question

Part of a Summer Analyst Interview Review - one of 1,556 Goldman Sachs Interview Reviews

Answers & Comments

0
of 0
votes
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 Flag Response
0
of 0
votes
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 Flag Response
0
of 0
votes
@thexesus

Bucket sort has space complexity of N. Swap answer works.
- GS on Feb 17, 2013 Flag Response

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


Goldman Sachs – Why Work for Us?

We bring together people, capital and ideas to produce solutions and results for our clients by playing a number of roles: financial advisor, lender, investor and asset manager. A commitment to integrity, team work and… Full Overview

Provided by employer [?]

Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Goldman Sachs interview questions and advice. All interview reviews posted anonymously by Goldman Sachs employees and interview candidates.