Julia's crafting skills - Lowest common ancestor

April 30, 2020

Introduction

I may put myself in danger position since I stop practicing coding using C# last two months. I was busy with stock market and learn how to control my psychology as an investor, and learn a few things how to understand market swings and economy. Good thing is that I still work as a volunteer as an mock interviewer, I keep myself open to top talent in the world. I just learn one thing a time, one crafting skills a time. 43 minutes a mock interview session really helps me to go back to practice. What I did is to practice the algorithm after the mock interview, I like to learn from the mock interviewee and try to write a C# solution using the same idea.

My crafting skills

Here is the post.


C# post order traversal and return p or q in recursive function

May 1, 2020

It is optimal solution I learned from mock interview on April 30, 2020 at 10:00 PM from the mock interviewee. He is ex-facebook engineer, and he wrote the code and tested, it took him less than 25 minutes. Here is the blog to document the practice.

I spent over 30 minutes to practice using C#. Here are my highlights:

1. Apply postorder traversal, bottom up, count nodes found and return Lowest Common Ancestor (LCA);
2. Think about C# data structure, using strong typing data structure Tuple;
3. Choose data structure Tuple<TreeNode, int> instead of ArrayList; Spend 10 minutes to warm up, find Item1 property usage;
4. More on step 2, two tips learned from failed test case, [3,5,1,6,2,0,8, null, null, 7, 4], 5, 4, return should be 5. Move ternary experession to the end, and add two parentheses to avoid grammar error. Need to work on C# basics.
5. Play with ternary expression and avoid ambiguity;
6. Remember if LCA is not found then Tuple.Item1 is null.

Add my practice to my collection of solutions written in 2019. Here is the post with various practice starting from May 2019.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _236_lowest_common_ancestor
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        public class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }

        /// <summary>
        /// May 1, 2020
        /// Use bottom up approach, and also return number of nodes found and LCA
        /// </summary>
        /// <param name="root"></param>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
        {
            var tuple = postOrderTraversal(root, p, q);
            return tuple.Item1; 
        }

        /// <summary>
        /// return LCA and count of nodes found
        /// </summary>
        /// <param name="root"></param>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        private static Tuple<TreeNode, int> postOrderTraversal(TreeNode root, TreeNode p, TreeNode q)
        {
            if (root == null)
            {
                return new Tuple<TreeNode, int>(null, 0);
            }

            var left = postOrderTraversal(root.left, p, q);
            if (left.Item1 != null)
            {
                return left;
            }

            var right = postOrderTraversal(root.right, p, q);
            if(right.Item1 != null)
            {
                return right; 
            }

            int count = left.Item2 + right.Item2 + ((root == p || root == q) ? 1 : 0);
            if (count == 2)
            {
                return new Tuple<TreeNode, int>(root, 2); 
            }

            return new Tuple<TreeNode, int>(null, count); 
        }
    }
}

Actionable Items

I should be more creative after the mock interview. One thing I can think about is to learn how to communicate better through mock interview. One time I did not show confidence in the first three minutes, the interviewee just terminated the interview.

I also think about how to contribute better as an interviewer. Being an interviewer, the interviewee demonstrates super good performance; To me it reminded me to work hard, and also I like to push myself continue to practice algorithm. The problem solving thinking process is such problem area for me to improve, and I need to compare myself often and then I learn from the experience.

I like to add some voice recording, and I like to explain the idea using my understanding. It will help me to track my progress as well.