Decide string transform with directional tokens and walls

Q: Decide string transform with directional tokens and walls

This question evaluates skill in string manipulation, reasoning about movement constraints, invariant formulation, and linear-time constant-space algorithm design for token movement problems.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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: (

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'. (
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'. (
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(
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).

Decide string transform with directional tokens and walls

Overview

Comments (0)