Array segregation, merging, probability, and puzzle
Filed under Goldman Sachs
Free read 1 of 3Use a two-pointer technique to segregate 0s and 1s in a single pass. For merging sorted arrays, use backward pointers to merge in-place if space permits, or standard two-pointer merging.
The question
Cover multiple foundational tasks: segregate 0s and 1s in an array, merge two sorted arrays, simulate a fair coin toss from a biased function, and solve the classic three ants on a triangle puzzle.
Constraints
- Array manipulations should target optimal O(n) time and O(1) space where applicable.
- Probability simulation requires logical decoupling of biased outcomes.
Examples
- Input
- array = [1, 0, 1, 0, 0, 1]
- Output
- [0, 0, 0, 1, 1, 1]
- Why
- Segregate all zeros to the left and ones to the right using a two-pointer approach.
Approach
Use a two-pointer technique to segregate 0s and 1s in a single pass. For merging sorted arrays, use backward pointers to merge in-place if space permits, or standard two-pointer merging.
To get 1/2 probability from a biased function (returns true with probability p), call the function twice. If outcomes are (True, False), return Heads; if (False, True), return Tails; otherwise retry.
Three ants start at the corners of an equilateral triangle and move along the edges in random directions. The probability they do not collide is 1/4, because the only non-collision configurations are when all move clockwise or all counter-clockwise out of 8 total possibilities.
Tips
- What they are testing: Evaluates algorithmic efficiency with arrays and lateral thinking in probability and puzzle-solving.
- Common mistake: Using extra space for merging sorted arrays or segregating bits instead of in-place two-pointer scans.
Related Goldman Sachs questions
Collected from public candidate posts and coding forums. Updated Nov 2026.