Lexicographically Smallest K-Step Return Walk
Reported by candidates from Google's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The mistake that sinks a first attempt on this Google OA, reported September 2026, is greedy walking. You pick the smallest legal move each step, burn k moves, and end up stranded far from 'x'. This is lexicographically smallest walk construction on a grid, tagged simulation, but the simulation only works if you know the distance to the start from every cell. Examples 2 and 3 show it: a move has to be legal and still leave a way home. If you blank on that during the live OA, StealthCoder sits invisible on your screen as a safety net.
The problem
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 = 2 return = "DU" DU moves down and then back up. It is smaller than the other two-step return RL. Example 2 grid = ["..#","x..","..."] k = 4 return = "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 = 2 return = "-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
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is BFS from 'x' first. That gives dist[cell], the shortest path back to the start through free cells. Then build the answer step by step. At step i you have k - i moves left. Try moves in order D, L, R, U. Take the first neighbor that is free and where dist[neighbor] <= remaining - 1 and the parity matches. On a grid, parity is automatic, since every move flips color, so a walk of length k can only return if k is even. If k is odd, return -1 right away. Also, if dist is unreachable, skip the cell. Extra moves can always be burned by stepping back and forth, which is why shortest distance is enough. The pitfall is plain greedy with no distance check, and the other is rebuilding the string with concatenation, which is slow. Use a list. Total work is O(cells + k). If the live OA freezes you, StealthCoder can hand you this structure.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Lexicographically Smallest K-Step Return Walk cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Google's OA.
Google reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Lexicographically Smallest K-Step Return Walk FAQ
What's the trick in the Google Lexicographically Smallest K-Step Return Walk problem?+
Run BFS from the start to get the shortest distance home for every free cell. Then build the walk greedily, trying D, L, R, U in order, and only accept a move if the new cell's distance fits in the remaining moves. That check keeps the walk returnable.
Why does plain greedy fail here?+
Taking the smallest legal move each step can walk you away from 'x' with too few moves left to return. You need the distance-to-start check at every step. Without it, you'll produce walks of length k that don't end at the start.
When is the answer -1?+
If k is odd, no closed walk exists on a grid, since each move flips cell parity. It's also -1 when the start has no free neighbor and k is positive. For k = 0 return the empty string, not -1.
What's the time complexity I should aim for?+
O(R*C + k). BFS visits each cell once, and the construction does at most four neighbor checks per step. With up to 2 * 10^5 cells and moves, anything slower than linear-ish risks being too slow. Build the result in a list and join once.
How do I prepare for this in 48 hours?+
Practice BFS distance maps on grids and the idea of building a lexicographic answer with a feasibility check per choice. Write this one from scratch once, testing the three examples. Focus on the remaining-moves condition and the odd-k early exit.