Round 1
Questions: Pretty standard problem asked Closest Leaf in a Binary Tree. Instead of the closest leaf, we needed to return the value.
Follow-up Questions:
- Why do you need to store the path? Why can't you do it while traversing?
- Why are you doing this with 3 functions? This can be done in 10 lines.
- Continuous questioning about line numbers and potential errors in the code.
Candidate's Approach
- Constructed a path from root to node.
- Reverse iterated the path and for each node:
- Checked the whole subtree for a matching node.
- Otherwise, checked the closest leaf in the alternate direction compared to the child direction for each parent node.
The candidate attempted to write the following code:
public class Linkedin { List<TreeNode> path; public int FindClosestLeaf(TreeNode root, int k) { GetPath(root, k, new List<TreeNode>()); int minLeafDistance = 1001; minLeafDistance = Math.Min(minLeafDistance, getClosestLeafDist(path.Last())); for(int i=path.Count-2; i >= 0; i--){ TreeNode current = path[i]; TreeNode next = path[i+1]; int dist = 1001; if(next == current.left && current.right != null){ dist = getClosestLeafDist(current.right) + 1; } else if(next == current.right && current.left != null){ dist = getClosestLeafDist(current.left) + 1; } minLeafDistance = Math.Min(minLeafDistance, dist + (path.Count-i-1)); } return minLeafDistance; } private void GetPath(TreeNode root, int k, List<TreeNode> pth){ if(root == null){ return; } pth.Add(root); if(root.val == k){ this.path = new List<TreeNode>(pth); return; } GetPath(root.left,k,pth); GetPath(root.right,k,pth); pth.RemoveAt(pth.Count-1); } private int getClosestLeafDist(TreeNode root){ if(root == null || (root.left == null && root.right == null)){ return 0; } if(root.left == null){ return 1 + getClosestLeafDist(root.right); } if(root.right == null){ return 1 + getClosestLeafDist(root.left); } return Math.Min(getClosestLeafDist(root.left), getClosestLeafDist(root.right)) + 1; } }
Interviewer's Feedback
The interviewer continuously pinpointed issues with the candidate's code, questioning the use of DFS over BFS, and highlighting potential null pointer exceptions. The candidate felt that the interviewer did not allow them to complete their reasoning and created an environment of stress with constant interruptions.