Train insane or remain the same - Get recursive function training one more time!
Maze algorithm
Given an array, there is only one item is value of 9, all others are 0 or 1. 0 stands for the exit is not availabe, 1 is ok to continue. Make a judgement if starting from (0,0), 4 directions: upper, down, left and right, and see if there is path to find 9.
Plan to study the code written in Java first. The code is here.
Practices
Using queue, the C# code is here.
Using queue, but four directions are written more clearly, C# code is here.
After 90 mocking interviews, Julia knows that it is important to write a short version solution in less than 5 minutes, without any bug. So she decided to write a recursive solution using depth first search, she ran into stack overflow issue. It took her over 10 minutes to figure out the issue, mark the node visited on line 46.
Here is the C# version code using recursive function. The goal is to write in less than five minutes, and pass the test case in less than 10 minutes.
In order to shorten the time to write code, Julia spent hundreds of hours to learn recursive function. One of her most lesson learned through mocking interview is the bug she found, documented in the blog called Leetcode 10: regular expression match.
Ask a vote?
Which version of code you will choose to write? Julia learned the lessons through years, she learned from 90 mocking interviews, she still could not nail down the most important solution using recursive solution in less than 5 minutes, today, July 18, 2017.
Just like a song, Julia you have to memorize the lyrics, you only have 4 sentences to remember. First one is to return false, second one is to return true, third one is to set to 0 as marking visited, and then fourth one is to call recursive function for 4 possible neighbors. In other words, here is the transcript to remember:
Line 8 return false
Line 13 return true
Line 18 maze[row][col] = 0
Line 21 - 24 four recursive function calls concatenated by || operator
No comments:
Post a Comment