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.

Algorithm, Rotate matrix nxm clockwise 90 degree

April 5, 2016

  Write an algorithm to rotate matrix nxm clockwise 90 degree.

  Use no compiler, no Ctrl+C, and then, time complexity analysis:

Here is the code Julia wrote, she thought about the swapping strategies:
1. swap multiple times
2. leave four corners as is, swap four corners seperately.

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

/*
April 5, 2016

NO ctrl+C copy

matrix nxm rotate clockwise 90 degree

do it in place
*/

 public static bool rotateInplace90ClockWise(int[][] arr)
        {
            if (arr == null || arr.Length == 0 || arr[0].Length == 0) return false;
            int n = arr.Length;      // row
            int m = arr[0].Length;   // column

            if (n != m) return false;

            // we need to start loops

            int start = 0;
            int end = n - 1;

            while (start < end && start < n / 2 && end < n / 2)
            {

                // top with right swap - left the terminal point untouched
                // left to right <- row
                // top to down   <- column
                for (int i = start + 1; i < end - 1; i++)
                {
                    int currx = start;
                    int curry = i;

                    int currx_col = i;
                    int curry_col = end;

                    swap(arr, currx, curry, currx_col, curry_col);
                }

                // now, top down, we need to cross swap

                for (int i = start + 1; i < end - 1; i++)
                {
                    int currx = start;
                    int curry = i;

                    int currx_down = end;
                    int curry_down = end - i;

                    swap(arr, currx, curry, currx_down, curry_down);
                }

                // left and top swap
                for (int i = start + 1; i < end - 1; i++)
                {
                    // left part
                    int currx = end - 1 - i;
                    int curry = start;

                    int currx_top = start;
                    int curry_top = i;

                    swap(arr, currx, curry, currx_top, curry_top);
                }

                // and then, rotate four corners
                // 1, 2
                // 4  3
                swap(arr, start, start, start, end);
                swap(arr, end, end, start, start);
                swap(arr, start, start, end, start);

                start++;
                end--;
            }
            return true;
        }
 
       private static void swap(int[][] arr, int x, int y, int x2, int y2)
       {
           int tmp     = arr[x][y];
           arr[x][y]   = arr[x2][y2];
           arr[x2][y2] = tmp;
       }

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

time complexity: since every node in the matrix at most swaps twice, so the count of swap is O(n^2)

Leetcode 54: Spiral Matrix | Code review | 2015 - 2023 | Long journey

June 11, 2015

Problem Statement

Recursive solution

The first study code is here. The second is here.

Iterative solution

The first study code is here. The second one is here. 

C# code to pass Leetcode online judge:

Julia's C# code practice in 2015

Follow up 

May 23, 2017

C# practice passes all test case. The code is here. Put one row and one column checking inside the for loop statement. Code is here.

Feb. 13, 2018

It is the early day I started to write coding blog to document my code practice. At that time, I was so shy and also afraid to write down my thinking process. I do not know myself even it is just three years ago.

I just wrote down two sentences, even the sentence is not complete. I chose to study two solutions and then I practiced one of them.

One thing I can tell now is that I did not pay attention to myself, how I think as a programmer, most likely I thought that coding is more important and also challenge.

The blogs I chose in 2015

Those algorithm blogs are well-written. I am surprised that I did not practice one by one in 2015.

The recursive solution is saved in the gist. Here is the link.
The solution based on directions is saved in the gist. Here is the link.
The solution based on directions and range is here.

Follow up 

July 4, 2023

I am so lucky to have chance to prepare for another phone screen from Meta in short future. I have chance to review my work history on this algorithm.