K Index algorithm

April 12, 2016

An array, to search if there is duplicate in k steps distance

First practice, two bugs (Time spent: 1 hour):
https://gist.github.com/jianminchen/1fec656b154a70acb30b5f6d7ad509ab

 private static bool DFS(int[][] arr, int oriX, int oriY, int row, int col, int kIndex, int search, int MaxRow, bool[][] searchedA)
        {
            if (!isValid(row, MaxRow) || !isValid(col, MaxRow) || kIndex < 0)
                return false;

            if (Math.Abs(oriX - row) + Math.Abs(oriY - col) > 0 && !searchedA[row][col])
            {
                if (arr[oriX][oriY] == arr[row][col])
                    return true;
                //bug 001 - Julia, you need to continue do DFS here
            }
            else
            {
                searchedA[row][col] = true;

                // bug 002 - all those DFS search, you need to check search result! 
                DFS(arr, oriX, oriY, row - 1, col, kIndex - 1, search, MaxRow, searchedA);
                DFS(arr, oriX, oriY, row + 1, col, kIndex - 1, search, MaxRow, searchedA);
                DFS(arr, oriX, oriY, row, col + 1, kIndex - 1, search, MaxRow, searchedA);
                DFS(arr, oriX, oriY, row, col - 1, kIndex - 1, search, MaxRow, searchedA);

            }

            return false;
        }

Fix two bugs (Time spent: 20+ minutes):

https://gist.github.com/jianminchen/ce7ccfa5db5b57c36d6742b622e9153e

function after bugs are fixed:
 private static bool DFS(int[][] arr, int oriX, int oriY, int row, int col, int kIndex, int search, int MaxRow, bool[][] searchedA)
        {
            if (!isValid(row, MaxRow) || !isValid(col, MaxRow) || kIndex < 0)
                return false;
         
            if (Math.Abs(oriX - row) + Math.Abs(oriY - col) > 0 &&  !searchedA[row][col] )
            {
                if (arr[oriX][oriY] == arr[row][col])
                    return true;                            
            }
         
            searchedA[row][col] = true;  // Bug001 - check condition is wrong 

            if (DFS(arr, oriX, oriY, row - 1, col, kIndex - 1, search, MaxRow, searchedA) ||
            DFS(arr, oriX, oriY, row + 1, col, kIndex - 1, search, MaxRow, searchedA) ||
            DFS(arr, oriX, oriY, row, col + 1, kIndex - 1, search, MaxRow, searchedA) ||
            DFS(arr, oriX, oriY, row, col - 1, kIndex - 1, search, MaxRow, searchedA))
                return true; // bug002 - any of conditions are ok, then, return true

            return false;
        }

Actionable item:
1. Julia, you have to build up skills to do code static analysis. Debugging takes time, you should check your logic, run your code through yourself by thinking, criticize your code by thinking about the test case, go through virtually first.

April 18, 2016
Julia, you should have more than 1 idea to solve this kind of problem - thinking about using Queue to solve it.

Microsoft phone screen | Binary Tree: Write a function to return count of nodes in binary tree which has only one child.

June 8, 2015

我最喜欢的一道算法题目, 我写了七八行.　你准备了几行?　

去年我才知道这道题可以用二行代码. 2014年七月, 第一次世界上最强的算法高手耐心地开导我, 教会我如何优化代码的, argue, change, using logic reasoning and try to make it minimal. 假想代码bug, 开始改; 然后, 试图解释清楚, 自己的想法.

讨论的要点:
1. Local variable in each recursive function
2. Redundancy code
3. If statement, how many if statement in the function
4. How to argue that the code will not have bugs? Can you simplify the code?
5. Make the code simple as possible, no way to hide any bugs
6. Base case discussion
7. Discussion if null checking is needed to call the function.
8. Use a global variable to store the count.
9. Function arguments - what arguments are needed.

2015年初, 决定从Java Script 学习, 转到算法, C#, Leetcode;  先练习最基本的问题.

Github for source code:

https://github.com/jianminchen/BinaryTreeOneChild/blob/master/Program.cs

只有一个孩子, 可以表示为一句话:　 (node.left!=null) != (node.right!=null)

Follow up

Feb. 15, 2019
Here is the link of my practice.

Follow up 

Nov. 1, 2023

I remembered that I had a phone screen from Microsoft. The interviewer was a principle engineer from Microsoft, and he coached me through the phone screen interview how to write an elegant solution using two lines of code. 

Actually I spent near 30 minutes to work with him, and I tried to write a broken solution.