Google·Software Engineer·Onsite - Coding / Algorithms·Senior

SeniorPrefer not to say

Jun 2026Bangalore

Summary

Offline onsite round at Google in Bangalore for a senior engineering role. One algorithmic question on grid traversal, the kind that looks straightforward but has a bunch of edge cases hiding underneath.

Questions Asked (1)

Given an N*M grid where some cells are free, some are obstacles, and you start at a marked cell, find a walk of exactly k steps that returns you to your starting position. If multiple valid paths exist, return the lexicographically smallest one using directions L, R, U, D.

Algorithms & Data Structures

Author's notes

The backtracking part clicked for me pretty quickly but the lexicographic ordering tripped me up for a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding a path of length k from start to start in a graph where vertices are cells and edges are moves. Use BFS with state (cell, steps mod 2) to find the shortest path to each cell with parity, then extend to exactly k steps by adding back-and-forth moves. To get the lexicographically smallest path, perform BFS in lexicographic order of directions and reconstruct the path.

Pro tip: Mention that if k is odd, it's impossible because any closed walk in a bipartite graph must have even length. Also, emphasize that lexicographic order requires careful BFS ordering and possibly storing parent pointers.

1. Understand the problem and constraints

Clarify that you need a walk (not necessarily simple) of exactly k steps returning to start, and if multiple, return the lexicographically smallest string of moves. Note that the grid is bipartite, so k must be even.

2. Model as graph and check feasibility

Represent each free cell as a vertex, with edges to adjacent free cells. Check if k is even and if there exists any cycle reachable from start; if not, return empty.

3. Find shortest paths with parity

Run BFS from start to compute the shortest distance to each cell for even and odd number of steps. This helps determine if a cell can be reached in exactly k steps.

4. Construct lexicographically smallest path

Use BFS that explores neighbors in lexicographic order (D, L, R, U) to find the lexicographically smallest path of length k. Alternatively, use DP or greedy construction with feasibility checks.

5. Handle edge cases and return result

If no path exists, return empty string. Otherwise, return the constructed path. Discuss time and space complexity.

Key Points to Mention

Bipartite nature of grid implies k must be even for a closed walk.
Use BFS with state (cell, parity) to find shortest paths and check reachability within k steps.
Lexicographic order: define order of directions (e.g., D < L < R < U) and ensure BFS explores in that order.
Reconstruction of path using parent pointers or by storing the path string.
Time complexity: O(N*M) for BFS, but careful with k up to large values; use parity to avoid O(k) states.
Edge cases: start cell blocked, no free adjacent cells, k=0, k odd, k too large but possible via back-and-forth.

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