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 - ‘#’
Comments (6)