Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Google SWE coding round, one main problem with a follow-up bolted on. The base problem was a known LeetCode variant dressed up in chess clothing, which I appreciated more than a straight 'here's the problem number' situation. The follow-up with walls was where things got genuinely interesting.

Questions Asked (2)

Given two strings of equal length over the characters R, L, and underscore, where R can only slide right into empty squares and L can only slide left into empty squares, determine whether some sequence of moves can transform the first string into the second.

Algorithms & Data Structures

Author's notes

The chess framing threw me for about thirty seconds before I realized what was actually being asked.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, verify that the sequences of non-underscore characters in both strings are identical, as moves cannot change the relative order of R's and L's. Then, for each R, ensure it only moves right (target index >= source index), and for each L, ensure it only moves left (target index <= source index). If all conditions hold, a valid sequence exists.

Pro tip: Mention that the problem reduces to checking invariants rather than simulating moves, which is O(n) and avoids exponential search. This shows you can identify the underlying structure quickly.

1. Extract and compare non-underscore sequences

Remove all underscores from both strings and check if the resulting sequences of R's and L's are identical. If not, transformation is impossible.

2. Map positions of each non-underscore character

Record the indices of each R and L in both the start and target strings, preserving order.

3. Check movement constraints for R's

For each R, ensure its target index is greater than or equal to its start index, because R can only move right.

4. Check movement constraints for L's

For each L, ensure its target index is less than or equal to its start index, because L can only move left.

5. Conclude feasibility

If all checks pass, return true; otherwise, return false. Explain that these conditions are necessary and sufficient.

Key Points to Mention

Relative order of non-underscore characters is invariant.
R can only move right, so its target position must be >= its start position.
L can only move left, so its target position must be <= its start position.
Underscores act as empty spaces that allow sliding.
The conditions are necessary and sufficient; no simulation needed.
Time complexity is O(n) with O(1) extra space if done in one pass.

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

Extend your solution to handle a new immovable wall character. Walls cannot be crossed by any piece, never move themselves, and must appear at identical positions in both strings. The reachability check now applies independently within each segment between walls.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is where I actually had fun.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, validate that walls appear at identical indices in both strings; if not, return false immediately. Then split both strings into segments at wall positions and run the original reachability check independently on each segment. Finally, combine the results—all segments must be reachable for the overall transformation to be possible.

Pro tip: Mention that walls act as natural partition points, so the problem decomposes into independent subproblems, which is a common pattern in string transformation problems. Also note that early validation of wall positions can save unnecessary computation.

1. Validate wall positions

Check that every wall character appears at the same index in both the start and target strings. If any mismatch exists, return false immediately.

2. Split into segments

Use the wall positions as delimiters to split both strings into corresponding segments. Each segment is a substring between consecutive walls (or string boundaries).

3. Apply reachability check per segment

For each pair of corresponding segments, run the original reachability algorithm (e.g., two-pointer or BFS) to determine if the start segment can be transformed into the target segment without crossing walls.

4. Combine results

If all segment pairs are reachable, return true; otherwise, return false. The overall transformation is possible only if every independent segment is reachable.

5. Analyze complexity and edge cases

Discuss time and space complexity, noting that splitting adds O(n) overhead but the core check remains the same per segment. Mention edge cases like adjacent walls (empty segments) and walls at boundaries.

Key Points to Mention

Walls are immovable and cannot be crossed, so they partition the problem into independent subproblems.
Identical wall positions in both strings are a necessary condition; if violated, the answer is immediately false.
The original reachability check must be adapted to operate within each segment, ignoring walls.
Empty segments (e.g., consecutive walls) are trivially reachable and should be handled correctly.
Time complexity remains O(n) overall because each character is processed a constant number of times across segments.
This approach demonstrates decomposition and reuse of existing logic, which is valuable in technical interviews.

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