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.

Can board states be transformed?

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given two strings, `start` and `target`, of equal length representing a one-dimensional board. 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 - `|`: a wall Rules: - In one move, a piece may slide into an adjacent empty cell in its allowed direction. - `L` pieces can never move right. - `R` pieces can never move left. - Walls `|` are fixed, cannot move, and no piece may cross a wall. Determine whether `start` can be transformed into `target` using any number of valid moves. Also explain how the simpler version changes when there are no walls and the strings contain only `L`, `R`, and `_`.

Quick Answer: 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.

Part 1: Can the Board Be Transformed With Walls?

You are given two strings, `start` and `target`, of equal length representing a one-dimensional board. 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 - `|`: a wall In one move, a piece may slide into an adjacent empty cell in its allowed direction. Walls are fixed, cannot move, and no piece may cross a wall. Determine whether `start` can be transformed into `target` using any number of valid moves. A strong solution should recognize that walls split the board into independent segments.

Constraints

`0 <= len(start) == len(target) <= 200000`
`start` and `target` contain only `L`, `R`, `_`, and `|`
Walls are fixed, so a valid transformation requires walls to remain in the same positions
A piece moves one cell at a time into an adjacent `_` in its allowed direction

Examples

Input: ("R_L|__L", "_RL|L__")

Expected Output: True

Explanation: Walls are aligned. In the left segment, `R` moves right; in the right segment, `L` moves left.

Input: ("L_|R", "L|_R")

Expected Output: False

Explanation: The wall positions differ, but walls cannot move.

Input: ("L_|_R", "_L|R_")

Expected Output: False

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.

Quick Overview