Introduction
It is the classical recursive algorithm. I had 4:00 pm mock interview and then I had to write H-tree algorithm. It took me exactly 30 minutes to finish the analysis and also coding. I made a mistake in the writing first, draw one H tree first, and then call recursive tree four times for each corners of H-tree.
Code review
Here is the code.
Compared to last practice
Here is my practice in Dec. 2017. The code is almost exactly same. Only difference is that this time I work on the analysis of the algorithm, write down given constraints, and problem to solve. Write down the solution first before I write the code.
I need to work on the structure of recursive function, base case, inductive step. Please write down those steps in analysis first.
if depth == 0
return
// draw one H-tree
draw horizontal line
draw vertical left line
draw vertical right line
// inductive step
4 recursive function call for each corner of H-tree
left top
right top
right bottom
left bottom
Because my first writing in mock interview today has wrong logic like the following:
if depth == 0
return
if(depth == 1)
{
// draw one H-tree
draw horizontal line
draw vertical left line
draw vertical right line
return;
}
// inductive step
4 recursive function call for each corner of H-tree
left top
right top
right bottom
left bottom
I found the bug in whiteboard testing and then I fixed it. But I should understand base case 100% before I write the code.
No comments:
Post a Comment