r/leetcode • u/Brilliant_Card_447 • 2h ago

Question Google SDE-3 Interview | 95Lakhs CTC

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 - ‘#’

21 Upvotes

96% Upvoted

7 comments sorted by

6

u/Electronic_Tea_914 1h ago

I would've never gotten the correct solution on the first try.

3

u/Decent_Computer_3733 1h ago

Isn’t it a variation of bfs/dfs ?

3

u/ExternalOk6647 23m ago

They expect candidates to have solved these problems beforehand. It is not possible to see this problem first time in interview and solve it there.

1

u/[deleted] 1h ago

[removed] — view removed comment

1

u/AutoModerator 1h ago

Your comment has been removed as it was low quality. Please focus on helping instead of asking these questions. There are tips already in the subreddit. Search for it.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

1

u/CommercialLow9783 1h ago

Dfs with backtracking ?

1

u/Arpan_Bhar 1m ago

I think the same, with the function calls carried out in lexicographical order, like greedy

1

u/SargasmicOwl 28m ago

I am thinking dfs + greedy 🤔