rotate array

April 12, 2016

Rotate array one element to right or down, clockwise.

For example:
1 2 3
8 9 4
7 6 5

After rotation, the matrix is the following:
8 1 2
7 9 3
6 5 4

Practice: (Time spent: 1 hour)
https://gist.github.com/jianminchen/24d77970e9a58a7850f2add10dfe7c4f

Failed test case:
1 2
4 3

output should be:
4 1
3 2

but my result:
3 2
4 1

Bug fix: (Time spent: 20+ minutes)
https://gist.github.com/jianminchen/6eb6244fbb1912e3a06e672f604f87e0

        /*
         * Do it in place
         */
        public static bool rotateArray(int[][] arr, int k)
        {
            if (arr == null) return false;
            int n = arr.Length;  // row
            int m = arr[0].Length; // column

            if (n != m) return false;
            if (n != k) return false;

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

            while (start <= end && start < k / 2)
            {
                // for left column
                swap(arr, start, start, start, start + 1, k);
                for (int i = start + 1; i <= end; i++)
                {
                    swap(arr, i, start, i - 1, start, k);
                }

                // for down row - swap
                for (int i = start; i < end; i++)
                {
                    swap(arr, end, i, end, i + 1, k);
                }
                // for right column
               // for (int i = end; i > start; i--)  // bug 001  if there are only two rows, exception
                for (int i = end; i > start && (end-start) > 1; i--)  // bug001 fix - do not swap if there are two rows
                {
                    swap(arr, i, end, i - 1, end, k);
                }
                // for up row              
                for (int i = end; i > start + 2; i--)
                {
                    swap(arr, start, i, start, i - 1, k);
                }
                start++;
                end--;
            }
            return true;
        }

Action item:
Base case 1x1,  2x2, and then 3X3, you cannot skip 2x2. It doesn't t matter what test case is given. Think about basics.

Also, think about how many swaps are needed for
1 2
4 3
only 3 swaps:
First one,
1 and 2
1 2
second one:
2 and 4
2
4
third one:
2 and 3
2 3

<- and then, need to filter out last 2 swaps in the while loop.

Relax, take more practice:
Smart to use debugger:
https://www.quora.com/Does-using-debugger-help-a-lot-in-competitive-programming

https://www.quora.com/What-are-the-best-competitive-programming-debugging-tips

April 15, 2016
Better design is to save arr[0][0] value, and then shift array value to left on top row. Make corner case much easy to handle.
So, good ritual is to come out more than 1 idea, and then, compare which one is better. Ask why!

Swap value cannot beat the array shift, much simpler the later one.

Divide and Conquer: Preorder traversal of ternary tree

January 6, 2016 重温一道关于树遍历的题目, 在新年开始的第一个星期, 鼓励自己, 加油! 多写代码, 多练习. Be humble, learn from her mistakes in 2015. Julia is learning how to solve "divide and conquer" - write a perfect recursive function - without bug in base case - recursive calls.  Her lessons for recursive function design, divide and conquer solution in 2014, 2015: 1. Do the work for root node, but do not do the work for its children; In other words, a subproblem can be handled by a recursive call.  2. Do not repeat base case 'if' clause - a checking afterwards in the recursive function call. Not necessary, except trying to use less stack.  Julia, recursive function design is like dealing with a family - single parent with children; show the work how to handle root node, that is almost done. Let recursive function to take care of children, do not do the work for children nodes. For example, binary tree, 2 children, call recursive function twice; Ternary tree, 3 children, and then, use 3 recursive calls.  Once again, "Do not do the work for children directly".  Action items: 1. Work on Leetcode questions again and start with simple questions. Binary Tree Preorder traversal of ternary tree

https://github.com/jianminchen/TreeAlgorithms/blob/master/ternaryTreeTraversal.cs   Binary Tree Inorder traversal: https://github.com/jianminchen/TreeAlgorithms/blob/master/TreeInorderTraversal.cs   Binary Tree Post order traversal https://github.com/jianminchen/TreeAlgorithms/blob/master/TreePostOrderTraversal.cs   Preorder traversal  https://github.com/jianminchen/TreeAlgorithms/blob/master/TreePreOrderTraversalB.cs

More reading about ternary tree:
  https://en.wikipedia.org/wiki/Ternary_search_tree

  https://en.wikipedia.org/wiki/Divide_and_conquer_algorithms

  http://www.drdobbs.com/database/ternary-search-trees/184410528

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.