How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Can board states be transformed? | Google Coding Question

Quick Overview

This question evaluates reasoning about constrained piece movement, string transformation, and invariant-based correctness in the Coding & Algorithms domain, testing skills in string manipulation and combinatorial reasoning while examining both conceptual properties and practical algorithmic implementation.

Loading coding console...

Explanation: The `L` would need to move right and the `R` would need to move left, which are both illegal.

Input: ("R_L|", "LR_|")

Expected Output: False

Explanation: In the first segment, the piece order would change from `RL` to `LR`, which cannot happen.

Input: ("", "")

Expected Output: True

Explanation: Two empty boards already match.

Hints

First check what must be identical no matter what moves are made: think about the wall positions.
Between two walls, the problem becomes the classic no-wall version: compare the non-underscore pieces and their allowed movement directions.

Part 2: Can the Board Be Transformed Without Walls?

You are given two strings, `start` and `target`, of equal length representing a one-dimensional board with no walls. Each character is one of: - `L`: a piece that may move only to the left - `R`: a piece that may move only to the right - `_`: an empty cell In one move, a piece may slide into an adjacent empty cell in its allowed direction. Determine whether `start` can be transformed into `target` using any number of valid moves. This is the simpler version of the wall problem: because there are no walls, the entire board is just one segment.

Constraints

`0 <= len(start) == len(target) <= 200000`
`start` and `target` contain only `L`, `R`, and `_`
`L` pieces can never move right
`R` pieces can never move left

Examples

Input: ("_L__R__R_", "L_____RR_")

Expected Output: True

Explanation: The piece order is the same, `L` moves left, and each `R` moves right or stays in place.

Input: ("R_L_", "__LR")

Expected Output: False

Explanation: Ignoring underscores gives `RL` in `start` but `LR` in `target`, so the pieces would have to pass through each other.

Input: ("_R", "R_")

Expected Output: False

Explanation: The `R` would need to move left, which is not allowed.

Input: ("", "")

Expected Output: True

Explanation: Two empty boards already match.

Input: ("L", "L")

Expected Output: True

Explanation: A single-piece board already matches the target.

Hints

If you remove all underscores, can the relative order of `L` and `R` ever change?
Use two pointers to compare the next piece in `start` and `target`, then check whether its movement direction is legal.

Last updated: Apr 19, 2026

Quick Overview