How should I practice Lexicographically Smallest K-Step Return Walk?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Lexicographically Smallest K-Step Return Walk associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Lexicographically Smallest K-Step Return Walk

Google● HardFULLTIMEONSITE INTERVIEW

Problem statement

You are given a nonempty rectangular grid grid and an integer k. Every cell is one of:

'.', a free cell;
'#', an obstacle that cannot be entered; or
'x', the unique free cell where the walk starts.

A move goes one cell down, left, right, or up without leaving the grid or entering an obstacle. Represent those moves with D, L, R, and U.

Return a valid walk of exactly k moves that ends back at 'x'. If several walks exist, return the lexicographically smallest one under D < L < R < U. If no such walk exists, return "-1". When k = 0, return the empty string.

Function

findReturnWalk(grid: String[], k: int) → String

Examples

Example 1

grid = ["x.",".."]k = 2return = "DU"

DU moves down and then back up. It is smaller than the other two-step return RL.

Example 2

grid = ["..#","x..","..."]k = 4return = "DRLU"

The walk DRLU returns to 'x' in four moves. After the first D, choosing R is the smallest next move that still permits an exact-length return.

Example 3

grid = ["x#","##"]k = 2return = "-1"

The start has no free neighbor, so no positive-length walk is possible.

Constraints

1 <= grid.length, grid[i].length <= 500
1 <= grid.length * grid[i].length <= 2 * 10^5
Every row has the same length and contains only '.', '#', or 'x'.
grid contains exactly one 'x'.
0 <= k <= 2 * 10^5