Recursive function design talk

July 16, 2017

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.

	public static bool checkMaze(int[][] maze, int row, int col)
	{
	if (maze == null || maze.Length == 0 || maze[0].Length == 0 ||
	row < 0 || row >= maze.Length ||
	col < 0 || col >= maze[0].Length ||
	maze[row][col] == 0 )
	{
	return false;
	}
	if (maze[row][col] == 9)
	{
	return true;
	}
	// mark as visited, Julia forget to set it, ran into stack overflow.
	// It took her 10 minute to figure out the issue.
	maze[row][col] = 0;
	// depth first search, go over each recursive branch if need.
	return checkMaze(maze, row + 1, col) ||
	checkMaze(maze, row - 1, col) ||
	checkMaze(maze, row, col + 1) ||
	checkMaze(maze, row, col - 1);
	}

view raw maze_recursiveSolution.cs hosted with ❤ by GitHub

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