Google SDE-3 Interview | 95Lakhs CTC
Summary
I attended an offline interview for a Google SDE-3 role in Bangalore and was asked a matrix walk problem.
Full Experience
Had offline interview round in BLR. This was one of the questions asked :-
You are standing at a particular position in a matrix of size N*M - Some cells are free , but some cells have obstacles in them which you cannot visit. It is guaranteed that you are initially standing on a free cell. Find a valid walk of size exactly “k” such that you start from your starting position - walk “k” steps and reach back your original position after “k” steps. Output that path. If there are multiple possible paths of size “k” - output the path which is lexicographically minimal string consisting of possible characters from the set - (“L”,”R”,”U”,”D”)
Free cell - ‘.’ Start position - ‘x’ Obstacle - ‘#’
Interview Questions (1)
Lexicographically Minimal Walk of Length k Returning to Start
You are standing at a particular position in a matrix of size N*M. Some cells are free, but some cells have obstacles in them which you cannot visit. It is guaranteed that you are initially standing on a free cell. Find a valid walk of size exactly "k" such that you start from your starting position, walk "k" steps and reach back to your original position after "k" steps. Output that path. If there are multiple possible paths of size "k", output the path which is the lexicographically minimal string consisting of characters from the set {"L", "R", "U", "D"}.
Free cell: '.' Start position: 'x' Obstacle: '#'