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.

Decide string transform with directional tokens and walls

Quick Overview

Decide string transform with directional tokens and walls evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given two equal-length strings start and target of length n, each consisting only of the characters 'L', 'R', '.', and 'X'. A dot '.' represents an empty slot; 'X' represents an immovable wall; 'L' and 'R' are tokens that may move across empty slots subject to these rules: ( 1) An 'L' token may move any number of positions left into '.', but may never move right, pass through another token, or pass through an 'X'. ( 2) An 'R' token may move any number of positions right into '.', but may never move left, pass through another token, or pass through an 'X'. ( 3) Only one token can occupy a position at any time. Determine whether target can be obtained from start by a sequence of valid moves. If yes, return true; otherwise, return false. Design an algorithm that runs in O(n) time and O( 1) extra space beyond a few pointers/counters. Explain your invariants, prove correctness informally, analyze time and space complexity, and walk through a few tricky edge cases (e.g., mismatched wall layouts, blocks separated by walls, consecutive tokens with no gaps).

Quick Answer: Decide string transform with directional tokens and walls evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given two equal-length strings `start` and `target` of length n, each consisting only of the characters 'L', 'R', '.', and 'X'. - '.' is an empty slot. - 'X' is an immovable wall. - 'L' is a token that may move any number of positions **left** into '.' cells, but may never move right, pass through another token, or pass through an 'X'. - 'R' is a token that may move any number of positions **right** into '.' cells, but may never move left, pass through another token, or pass through an 'X'. - At most one token can occupy a position at any time. Return `true` if `target` can be obtained from `start` by a sequence of valid moves, otherwise `false`. **Key observations** 1. Removing every '.', the remaining sequence of non-dot characters (the 'L'/'R' tokens and the 'X' walls) must be identical in `start` and `target`, in the same order — moves can neither create/destroy tokens nor reorder them past one another or past a wall. 2. For each matched 'L', its index in `start` must be `>=` its index in `target` (it can only slide left). 3. For each matched 'R', its index in `start` must be `<=` its index in `target` (it can only slide right). 4. For each matched 'X' wall, its index must be identical in `start` and `target` (walls never move). A single left-to-right two-pointer scan that skips dots and compares the k-th non-dot character of each string enforces all of the above in O(n) time and O(1) extra space.

Constraints

1 <= n <= 10^5 (n may also be 0 for the empty-string edge case)
len(start) == len(target)
start and target consist only of the characters 'L', 'R', '.', and 'X'
Required: O(n) time and O(1) extra space

Examples

Input: ('R...L', 'RL...')

Expected Output: True

Explanation: Non-dot sequences both 'RL'. R stays at index 0 (0<=0). L moves left from index 4 to index 1 (4>=1). All moves valid.

Input: ('R.L', 'R..L')

Expected Output: False

Explanation: Different lengths (3 vs 4) — immediately false.

Input: ('_L__R__R_', '_L______R')

Expected Output: False

Explanation: Underscores are not '.', 'L', 'R', or 'X'; start has tokens L,R,R but target has L,R, so the non-dot sequences differ in count/order -> false.

Input: ('.R.L.', '..RL.')

Expected Output: True

Explanation: Both reduce to 'RL'. R moves right (1<=2), L stays/moves left (3>=3). Valid.

Input: ('L.X.R', 'LX..R')

Expected Output: False

Explanation: Wall X is at start index 2 but target index 1; walls cannot move -> false.

Input: ('LX.R', 'L.XR')

Expected Output: False

Explanation: Wall X moves from index 1 to index 2; immovable wall -> false.

Input: ('X.RL', 'XR.L')

Expected Output: False

Explanation: Matched tokens X,R,L. R would need to move from index 2 to index 1 (left), which 'R' cannot do -> false.

Input: ('.R.X.L.', 'R..X..L')

Expected Output: False

Explanation: R must move from start index 1 to target index 0, i.e. leftward, which 'R' cannot do -> false (the wall X is consistent at index 3).

Input: ('', '')

Expected Output: True

Explanation: Empty strings trivially match.

Input: ('.', '.')

Expected Output: True

Explanation: Single empty slot, no tokens -> reachable.

Input: ('LR', 'RL')

Expected Output: False

Explanation: Adjacent tokens with no gap. Non-dot sequence 'LR' vs 'RL' differs in order; tokens cannot pass through each other -> false.

Input: ('R.', '.R')

Expected Output: True

Explanation: R moves right from index 0 to index 1.

Input: ('.L', 'L.')

Expected Output: True

Explanation: L moves left from index 1 to index 0.

Input: ('X', '.')

Expected Output: False

Explanation: A wall cannot vanish or turn into an empty slot; non-dot sequences differ -> false.

Hints

Strip the dots conceptually: the ordered sequence of non-dot characters (tokens and walls) must be identical in both strings — moves can never reorder them or change the count.
Use two pointers, one per string, each skipping '.' cells, and compare the k-th non-dot character of start against the k-th of target.
Direction constraints become index comparisons: an 'L' may only move left so its start index must be >= its target index; an 'R' may only move right so start index must be <= target index; an 'X' wall must keep the exact same index.

Quick Overview