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.