Leetcode discuss: 98. Validate Binary Search Tree

 Feb. 27, 2022

Here is the link. 

C# | Mock interview practice | Interviewer with MSFT, Amazon, Oracle, Meta | 2022 Feb. 23

Feb. 24, 2022
Introduction
I booked a few mock interviews after two year break starting from Dec. 2020. I had chance to work on this algorithm in the mock interview, and I wrote the code and tested all cases. The interviewer gave me 10 minutes review. I learned a few things. I did practice this algorithm near 10 times last few years, but this time I had mock interview and then I got invitation to get connected after the performance. It is worthy of time to share the experience.

The definition of binary search tree | Interviewer shared
A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

The advice from interviewer
Great Job! You solved the problem correctly and answered additional question.
Some suggestions:

• Try to have a plan (intro, idea explanation, pseudocode solution (if you choose to do it), solution, test cases, edge cases discussions, complexity
• Time yourself for each part of plan, try to finish within 20 mins (especially for Meta and Google)
• In many cases you first write code with issues and then correct yourself, try to be right from the first attempt, it will save you time and also will not let impatient interviewer to log negative signal

My notes after mock interview
The interviewer asked me to write a function to check if a binary tree is a binary search tree. I wrote the code, and then he helped me to test the code, make sure that all test cases are covered. And also the interviewer gave me 15 minutes talk and demonstration to help me improve my performance, presentation and avoid giving false negative signals in advance.

1. Initial implementation wrong, correct yourself; Cons, interviewer may interrupt you as an interviewee, not patient;
2. Pay attention to detail
3. Interviewer may intervene -> negative signal, how to avoid making first writing mistakes
4. Timing, 20 minutes an algorithm; Mata - two algorithms in 45 minutes
5. Drive interview, saying let me do the coding, be proactive, cautious of time
6. Presentation, illustration, draw a tree, and then use cursor to help, go over a few test cases, 3(root), 1(left), 4(right), it is BST, why, do a few test cases; this makes good presentation
   Time, presentation, in general interviwee should drive interview, more driving. Mindful practice on leetcode. A lot of good advice, thank you for being my interviewer.

Test cases
I wrote C# code to run the test cases.

static void Main(string[] args)
        {
            /*
            var root2 = new TreeNode(2);
            root2.left = new TreeNode(1);
            root2.right = new TreeNode(3);
            var test = new Solution();
            */

            var root3 = new TreeNode(3);
            root3.left = new TreeNode(1);
            root3.left.right = new TreeNode(2);
            root3.left.right.left = new TreeNode(4);

            //root3.right = new TreeNode(int.MaxValue);
            var test = new Solution();

            Console.WriteLine("result is ");

            var result = test.IsValidBST(root3);

            var output = result == true ? "true" : "false";
           
            Console.WriteLine("result is " + output);            
        }

Test cases:

1. BST, three nodes, 2(root), 1(Left), 3(right)
2. Not BST, failed test case, the above item1 BST, add left subtree with a node value bigger than root value
3. Try to apply int.MaxValue in the tree node value, make sure that it is working, BST
4. Interviewer suggested me to draw a tree by typing the words, and then change the value and make good presentation on discussion of BST test cases.

Annotations (shared later) | quick sharing
I like to share quickly annotations I got after I wrote the code, starting from 21 minutes in mock interview.

1. communication (Green) 21:02 clarification
2. communication (Red) 21:30 illustrate your speech
3. problem solving (Green) 22:17 good iteration on problem
4. problem solving (Green) 22:32 long/int edge case
5. technical skills (red) 28:01 C3: ref instead of return, default prams, order of operation, etc.
6. problem solving (Green) 33:47 [hint]captured equal values
7. other (green) 36:42 time complexity
8. other (red) 37:43 Space complexity O(h)

The interviewer did not choose a hard level algorithm, instead he chose the medium level, and he likes to see the production ready code.

The following C# code passes online judge.

		// Time complexity: O(N), N is total number of nodes in binary tree
        // space complexity: O(1) - 
        // recusive: stack space - O(lgN), worst O(N) | Should be 0(h), h is height of tree, not logN (From mock interviewer)
        public bool IsValidBST(TreeNode root)
        {
            if (root == null)
            {
                return true;
            }

            // 
            var found = false;
            runPreorder(root, long.MaxValue, long.MinValue, ref found);

            return !found;
        }
        
        private void runPreorder(TreeNode root, long upperBound, long lowerBound, ref bool foundException)
        {
            if (root == null)
                return;

            if (root.val >= upperBound || root.val <= lowerBound)
            {
                foundException = true;
                return;
            }

            runPreorder(root.left, root.val, lowerBound, ref foundException);

            runPreorder(root.right, upperBound, root.val, ref foundException);
        }