Case study: mock interview on algorithm post order iterative solution

Dec. 8, 2018

Introduction

It is another mock interview. Recently I was so surprising to work so well with a Facebook intern, an Amazon intern, and a few engineers preparing for Google onsite and other very well. Since I learned after I got feedback with complaint from a San Diego master degree student on Oct.1 5, 2018. I like to case study the mock interview I had with a young graduate with 2 years working experience, and he learned the programming by himself.

Case study

I like to give the interviewee options at the very beginning so I can test his confidence level, and what I should adapt to the interviewee, and help him/ her to learn together with me on the algorithm.

So I asked him about his junior experience, and he told me that he had only two years working experience.

I asked him to choose to work on hard level algorithm or starting from easy one to a hard level one. He chose the hard level one.

I asked him to choose one hard level one, I used the algorithm over 10 times to interview others. I have a lot of experience on the one. Or choose one hard level one, I did not use the algorithm to interview others, this the first time, and I had the one in one phone screen from big four software companies in 2017 February. He chose later one.

So I gave him Leetcode algorithm I just worked on last week, post order iterative solution.

145. Binary Tree Postorder Traversal

Give out major hint

It is time for me to give out the hint after first 20 minutes discussion. I asked the interviewee to work on finding the first one in the post order traversal. I did also give out hint to work on a few test cases, and ask what is difference to find the first one.

Test case 1:

Input: [1,null,2,3]
   1
  / \
 2   3


hint: how to find the first node in post order traversal
 
    2 is the first one

Test case 2: 
   1
  / \
 2   3
  \
   4
hint: should be 4 -> first node
    how do find the firs one, what is difference?
    4 should be the first one

Test case 3:
 
   1
  / \
 2   3
  \
   4
   /
   5
 
Test case 4: 
  1
  / \
 2   3
  \
   4
    \
    5

Ask the interviewee to code

I asked the interviewee to code, just code to find the first element in post order traversal. Once you find the first one, the rest is easy since you can repeat the same process.

Continue

I talked based on my practice how I handled to find the second element in the post order traversal, I chose to use hashset to make visited nodes, so I can find 3 in the simple test case
   1
  / \
 2   3

Because the first element is 2, and then go back to stack, peek the top element with value 1, and then check its left node 2 which is already visited. But the interviewee told me that he was thinking to do something different. He also explained to me later using an example how it works. Basic idea is to break edge after it is visited.

For example, node 1 is visited, and node 1's left child node is visited, then 1's left child set to null.

Analysis based on facts

I also learn how to work with young generation, and my main weakness right now is willing to help, how to guide them break through to find the solution first.

Actually the interviewee has strong problem solving skills compared to me. I usually do not think based on the analysis, I choose to base on my experience. But actually there are so many solutions, the interviewee thinks carefully.

How to find the first element in post order iteratively?

From root node, go left, if there is no left child, then go right; continue until a node is met without left and right child.

Here is the code written in the mock interview by the interviewee:

Replay is good time to learn things

Dec. 8, 2018 1:52 PM
I replayed the video and learned a few things to work on.

The interviewee solved over 400 Leetcode algorithms so far, and he only spent 8 months to work on.

He worked way up from the easy ones first.

I replayed the video and reviewed the chat we had after the mock interview. I need to figure out how to handle conversation better.

38:00 - 41:36/1:14
The interviewee went over the example of tree using example of tree with node 1, 2, 3
   1
 /   \
2    3

stack = [1, 3
res = [2, 3, 1]

What do you think?

41:50 - 46:06
I asked him to work on the tree with 1, 2, 3, 4, 5.

The interviewee went over the example of tree using example of tree with node 1, 2, 3, 4, 5

   1
  /  \
 2   3
  \
   4
   /
  5

stack = [1
res = [5, 4, 2, 3, 1]

The interviewee worked on the solution to find the first node without any children. Each time the node is visited, the tree structure is change to remove the relationship parent/ child relationship, set it's left child to null or right child to null.

stack = [1, 2

   1
     \
2    3
 \
  4
 /
5

put node 4 into stack, stack = [1, 2, 4

   1
     \
2    3

  4
 /
5

put node 5 into stack, stack = [1, 2, 4, 5

   1
     \
2    3

  4

5

Now peek the top element in the stack, no children, put 5 into result

result = [5, 4, 2,

peek node 1's right child 3, put 3 into stack, set the 1's right child to null

1

   3
Now it is time to put 3 into result list.

Actionable Items

I also spent time to write a discuss post. Here is the link.

Actionable Items

I also spent time to write a discuss post. Here is the link.

I learn how to behave much better in the algorithm interview. I need to improve my communication skills, and express myself better.

I also got connected on linkedin, so I can follow up later on how the interviewee makes progress in the job search.

My feedback as an interviewer

Feedback from the interviewee