Google·Software Engineer·Onsite - Coding / Algorithms·Senior

Senior

Apr 2026

Summary

Google SWE coding round, one problem the whole session. It was a variant of a problem I thought I knew, which made it worse somehow.

Questions Asked (1)

Given a circular board with pieces labeled 'L' and 'R' separated by dots, determine whether a start configuration can be transformed into a target configuration. 'L' and 'R' pieces wrap around the ends of the board and still cannot cross each other.

Algorithms & Data Structures

Author's notes

I knew LC 777 cold so I thought this was a gift.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the board as a circular string and recognize that pieces cannot cross, so their relative order is invariant. Check if the sequences of L and R pieces (ignoring dots) are identical in both configurations, and verify that each piece can move to its target position without violating the no-crossing constraint.

Pro tip: Clarify with the interviewer whether the board is circular and whether pieces can move simultaneously or one at a time; this affects the solution. Also, consider edge cases like empty boards or boards with only one type of piece.

1. Understand the problem

Restate the problem to ensure clarity: pieces L and R on a circular board, dots are empty spaces, pieces cannot cross. Determine if start can become target.

2. Identify invariants

Note that the relative order of L and R pieces is invariant because they cannot cross. Also, the number of L and R pieces must be the same in both configurations.

3. Check necessary conditions

Verify that the sequences of L and R (ignoring dots) are identical in start and target. If not, transformation is impossible.

4. Verify sufficiency

If the sequences match, argue that pieces can be moved one by one to their target positions without crossing, using empty spaces as buffers. Consider circular wrapping.

5. Handle edge cases

Consider cases with no pieces, only L or only R, and boards where start equals target. Also, consider if the board is circular and pieces can wrap around.

Key Points to Mention

Invariant: relative order of L and R pieces cannot change.
Count of L and R pieces must be equal in start and target.
The sequence of L and R (ignoring dots) must be identical.
Circular nature allows wrapping, but pieces still cannot cross.
Empty spaces (dots) allow movement, but may be limited.
Edge cases: empty board, single piece, already matching configurations.

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