SoFi·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Coding round at SoFi for a software engineer role. One algorithmic problem, fairly meaty, and the naive solution is easy to see but the efficient one takes some real thought.

Questions Asked (1)

You have a binary string of '0's and '1's. Every second, every adjacent '01' pair swaps simultaneously to '10'. How many seconds until the string stabilizes into all 1s before all 0s? Can you do better than a naive O(n²) simulation?

Algorithms & Data Structures

Author's notes

I got the brute-force simulation pretty fast, just model each step and count.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem and confirm understanding with examples. Then, derive an O(n) solution by observing that each '1' moves right past zeros, and the time for a '1' to reach its final position depends on the number of zeros to its left and the time for the previous '1' to settle. Finally, implement the O(n) algorithm and discuss its efficiency compared to naive simulation.

Pro tip: Walk through a small example (e.g., '1001') to illustrate the pattern and validate your formula. This demonstrates clarity and helps catch off-by-one errors.

1. Understand the problem and clarify

Restate the problem in your own words and confirm with the interviewer. Ask about edge cases (e.g., empty string, all zeros, all ones) and constraints (e.g., input size).

2. Analyze the movement pattern

Observe that each '1' moves right by one position per second if there is a '0' immediately to its right. The final state has all '1's before all '0's. The time for a '1' to settle depends on the number of zeros to its left and the settling time of the previous '1'.

3. Derive an O(n) formula

Iterate through the string, counting zeros. For each '1', compute its settling time as max(zeros_so_far, previous_settling_time + 1). The answer is the maximum settling time over all '1's.

4. Implement and test

Write code for the O(n) algorithm. Test with examples like '0110101' and edge cases. Compare with a naive simulation for small inputs to verify correctness.

5. Discuss complexity and trade-offs

Explain that the O(n) solution is optimal since any algorithm must read the input. Mention that the naive simulation is O(n^2) and impractical for large n.

Key Points to Mention

The problem is equivalent to moving all '1's to the left while preserving their relative order.
Each '1' can only move right when there is a '0' immediately to its right; simultaneous swaps mean multiple '1's can move in the same second.
The settling time for a '1' is the maximum of the number of zeros before it and the settling time of the previous '1' plus one.
The overall time is the maximum settling time among all '1's.
The O(n) solution uses a single pass, tracking zeros count and previous settling time.
Edge cases: no '1's (time 0), no '0's (time 0), alternating patterns.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.