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

Intermediate

Apr 2026

Summary

Google SWE coding round, one problem, classic puzzle-style. The question was trickier than it looked on the surface and I spent way too long second-guessing an observation that turned out to be the whole key.

Questions Asked (1)

You have a 1-D board represented as a string of 'L', 'R', and '.' characters. 'L' pieces can only slide left into empty spaces, 'R' pieces can only slide right into empty spaces, and pieces can never cross each other. Given a start configuration and a target configuration of the same length, determine if the start can be legally transformed into the target.

Algorithms & Data Structures

Author's notes

I kept trying to simulate the actual moves, which was a dead end.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, recognize that pieces cannot cross, so the relative order of pieces must be identical in both configurations. Then, for each piece, verify that it can only move in its allowed direction (L left, R right) and that the target position is reachable without crossing other pieces. This reduces to checking that the i-th piece in start matches the i-th piece in target, and that L pieces don't move right and R pieces don't move left.

Pro tip: Mention that this problem is equivalent to checking if the start configuration can be transformed into the target by sliding pieces, which is a common interview question at Google. Emphasize the importance of edge cases like empty boards or boards with only one type of piece.

1. Check piece order

Extract the sequence of pieces (ignoring dots) from both start and target. If they differ, return false immediately because pieces cannot cross.

2. Verify movement constraints

For each corresponding piece, ensure that L pieces in start are at positions >= their positions in target (since they move left), and R pieces are at positions <= their positions in target (since they move right).

3. Handle edge cases

Consider cases where there are no pieces, or where pieces are already in the correct position. Also, ensure that the lengths of start and target are equal.

4. Implement and test

Write a function that iterates through both strings simultaneously, skipping dots, and applies the checks. Test with provided examples and additional edge cases.

Key Points to Mention

Relative order of pieces must be preserved.
L pieces can only move left, so their target index must be <= start index.
R pieces can only move right, so their target index must be >= start index.
Dots represent empty spaces and can be ignored when comparing piece sequences.
Time complexity is O(n) with a single pass through the strings.
Space complexity is O(1) if we use two pointers instead of extracting sequences.

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