Linear scan the array

Dec. 25, 2017

Introduction

I had a mock interview at 12:00 PM. I wrote a linear scan algorithm and finished the algorithm in 22 minutes. The peer asked me if I solved the problem before, and then I explained to the peer that I solved similar algorithm, there are two famous algorithms related to linear scan algorithm, test how good you can write a for/ while loop. One is called Leetcode can plant flower, one is called hackerrank Bear and gene.

Code review

The C# code is here.

Special case of Leetcode 230: Kth Smallest Element in a BST

Nov. 6, 2017

Introduction

It is the hard level algorithm called Kth smallest element in BST. When k value is one, the problem can be called to find largest smaller element in a binary search tree given the number.

It is very good discussion with the peer how to write an iterative solution. I did write down the code using C# and then I have to figure out how to get good rating from the peer.

Here is the C# practice code. I added main function after the mock interview.

Code review 

Here is the evaluation I got. I need to learn how to work with the peer, and follow the hint better.

Follow up 

Nov. 7, 2017
I found a bug in my code, the null pointer exception on line 35:
while(currentNode.right.key < num)


Here is the fix, C# code is here. currentNode.right == null is added to line 41. ( * bug fix No. 1*)

Nov. 10, 2017 11:44 PM

I finally figured out the thing I did wrong in my last mock interview. The code I wrote in Nov. 6 is wrong, and also the fix of bug on Nov. 7 ( * bug fix No. 1*) is also wrong. I finally understood that I was too stubborn and did not take the advice in mock interview.


Also the above code will not work for the following binary search tree:

Given the value 11, largest smaller BST key's value should be 10, but the solution will return 8 instead. Also the above code has null pointer run time exception on line 36, currentNode's right child may be null pointer, need to put a guard clause to check currentNode.right != null.


Nov. 10, 2017
11:19 PM
I had 10:00 pm mock interview, the peer worked on the algorithm. I had chance to find my problem based on the following test case. Great thanks for the peer, who is very patient, and think about the test case carefully.

Given number 11, the largest smaller BST key is 10. How to find node with value 10?   

First, start from root node with value 19, 19 is bigger than 10, so go to its left child. Left child value is 8 and it is smaller than 11, then set the value to look for (denote as LargestValue) as 8. And go to its right child to search. The node's value is 11 which is not smaller than 11, then go to left child 10, and set LargestValue = 10. Node 10 is leaf node without any child. 10 is the answer. 

In other words, find smaller one, go right; find bigger one, then go left. Until the traverse reaches the leaf node. Left, right, left. 

Leetcode 329: Longest increasing path in matrix

June  20, 2016

problem statement:

Given an integer matrix, find the length of the longest increasing path.From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

329. Longest Increasing Path in a matrix

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Study the code written in Java:

http://blog.csdn.net/sbitswc/article/details/50707203

1st practice using C#: 

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

Question and answer:

1. How is the practice? 

The study was very good. DFS - using recursive call, and then, tricky part is to use memorization to 

avoid duplicated calculation. 

2. Talk more with an easy example, therefore, next time you will not forget the problem after 

a few months. 

Answer: Will write something here. 

1. Talk about node row = 2, col =1, value is 1, denoted as start1,  3 neigbors, left (value 2), right (value 1), up(value 6)

2. Try to avoid loops - base case checking, always go to the node value >= current value >= start node '1'

3. Also, if neighbour node left (value 2) has maximum increasing path in matrix n, then, what we can know:

   value 1 < value 2, then, start1's longest path at least 1 + value2's longest increasing path. Need to check other 2 

  neighbors to see if it is larger value

    left neighbor (value 2)'s longest increasing path in matrix 2->6->9, length is 3;

    right neighbor (value 1)'s longest increasing path in matrix 1->8, length is 2; 

    upper neighbor (value 6)'s longest increasing path in matrix (actually 2 of them, 6->9 or 6->8), length is 2. 

4. DFS algorithm can be set up using recursive function; also, there are total 3*3 = 9 nodes in the above matrix, 

    each node's increasing path in matrix should not count more than once. 

    For example, nums[0,0] = 9, is maximum value of matrix, so the longest path = 1. 

    Let us put a sentence together. How about the following:

    Be greedy, check your neighbors (at most 4), and find maximum one with longest increasing path in matrix, and then use the path

to build your own. The value is 1 + that neighbor's problem, where the recursive function is constructed. 

5. The design of algorithm - brute force solution - how many paths in the matrix - n^4 = n x n x n x n; filter out non-

increasing path, then find maximum value - not efficient

6. For each node in matrix, find its longest increasing path in matrix, nxn nodes, each node, DFS algorithm is applied. 

    at most nxn node is checked about increasing order. <- try to reason the time complexity -> ...

    Will be less than n^4. 

7. Prepare a check list for the design:

    1. Run time issue - index out of range - array - boundary check 

        loops - always go to bigger value - no loop 

    2. time complexity - nxn node, each one does DFS; each DFS, at most 4 n^2 comparison of value. 

    3. space complexity - use extra array nxn to store bool value - memorization  

    4. value is bigger/ smaller / 0, 0 - not possible, at least 1, miss count - recursive, should be easy. 

    5. Brute force solution and its issues - more time consuming etc., duplication calculation    

Most important discussion: 

find the idea to store in extra array: 

1. Extra array to store the length of "longest increasing path in matrix" for each node in the array - (working idea)

2. Extra array to mark the node is visited or not -  (not enough for calculation!)

 denote DFS function to calculate the longest increasing path in matrix, then starting from start1, the function will be

left->left->up->up, in other words, from 1->2->6->9, and then, 

up->right,    1->6->8   

up-> up,       1->6->9, 

the visiting order of neighbors is left, down, right, up.

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

anti-clockwise, left, down, right, up  - line 116 - 120

So, the cache value of (2, 1) is 4, longest path is 4 (1->2->6->9); and 6 nodes in matrix are calculated and saved with 

cache value - 2 matrix(2,0), 6(1,0), 9(0,0), 6(1,1), 8(1,2), 9(0,1), the order of saving is 

9(0,0),          - 0 neighbor

6(1,0),          - 1 neighbor

2 matrix(2,0) - 1neighbor, value 1

6(1,1)

8(1,2)            

9(0,1)

6(1,1)   - 2 neighbors, comparison 1 vs 1 

1(2,1)   - 2 neighbors, comparison 3 vs 2

Use stack to help to track the order: 

start1 node, 2 neighbors

go to left neighbor first, 

      push to stack, 2, 6, 9

no down neighbor, skip right

then go to up neighbour, 

     ...

Statistics: 

Time to work out order of calculation cache value in the above list takes more than 10 minutes. 

Two motivations to work on reasoning and analysis:

1. Leetcode 329 is hard

2. Being able to write down bug free, executable code in 20 minutes. 

  3. Study more solutions from others, and then, practice it using C#. Study one using C++. 

C++ solution:

http://gaocegege.com/Blog/algorithm/leetcode329

http://codingmelon.com/2016/01/20/longest-increasing-path-in-a-matrix-leetcode-329/

To be continued. 

HackerRank: string algorithm - Reverse Shuffle Merge - Stack, backtracking techniques

May 26, 2016

Reverse Shuffle Merge - Problem statement:

https://www.hackerrank.com/challenges/reverse-shuffle-merge

Algorithm analysis:

Use test case: "abcacb" to explain the solution: 

int[] add = new int[26], 

int[] skip = new int[26]

a - 0, b - 1, c -2 

add[0] = 1, add[1] = 1, add[2] = 1, 

skip[0] = 1, skip[1] = 1, skip[1] =1, 

Find smallest lexical string. 

reverse input char one by one:

push b into stack, 

'c' > ''b', then, push c into stack

stack:

c

b

Now, a is scanned, 'a' < stack.peek() = 'c', skip[2] = 1 > 0, 

backtracking, pop c out of stack, skip[2] = 0

Now, 'a' < stack.peek() = 'b', skip[1] = 1 > 0, 

backtracking, pop b out of stack, then adjust skip[1] = 0

add[0] >  0, push a into stack, add[0] = 0, 

next, c is scanned, cannot skip, push into stack, 

next, b is scanned, cannot skip, push into stack, 

next, a is scanned, skip a. 

stack.ToArray(), keep stack iterator order, "bca", 

Array.Reverse(stack.ToArray()) -> "acb"

Lexical smallest string. 

previous blog: 

http://juliachencoding.blogspot.ca/2016/04/april-3-2016-httpsgist.html

warmup practice:

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

Second practice:

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

so many bugs in second practice:

1. confused on skip, add array --, ++; line 71, line 80 did the opposite.

2. string reverse, char[], string, Array.Reverse etc. lookup

3. add one more test case: "abcacb",

    b in stack, c in stack, then, run into a, pop up c, and pop up b, let 'a' in the stack. Two in row pop up in stack. While loop is tested on line 64 - 67.

4. while statement from line 64 - 67, fix compile error.

   both are ok to compile:

(char)stack.Peek() > runner)

(char)stack.Peek() - runner > 0)

Third practice:
The code passes HackerRank online test cases as well.

A few good changes:
1. add comment from line 67 - line 72, test case: "abcacb", 
use test case, stack top -'c' is removed, help to ensure the code is correct.
2. line 73, avoid bug to overwrite the variable runner, create a new variable called backTracked.

https://gist.github.com/jianminchen/8e2c28262dd3d13c4db856feaed5603e

Fourth practice:

1. create a new function getIndex - on line 100 - 103
2. after reading through the code, still missed a bug in writing - on line 55; debug the code and find
the result of first test case "abcacb" should be "acb", but it was "bca".

Julia examined line by line, but still missed the bug on line 55.

https://gist.github.com/jianminchen/7572e92ea48211d3d05c557d97601dbf

Read C# string constructor char[]: spend 10 - 20 minutes to read all constructors of string in C#.
https://msdn.microsoft.com/en-us/library/aa331865(v=vs.71).aspx

Binary Tree Preorder Traversal - Iterative Solution - Warm up Practice

May 25, 2016

Review blogs - Leetcode binary tree preorder traversal

C# practice:

use stack, and also know the order to push child nodes: right child first, and then left child next.

Code is here.

Question and Answer:
1. How is the practice?

Julia first thought about using queue to implement the solution, left child first, and then right child next. But, it does not work, since left child's left child should go to traversal first before right child. So, she had to stop.

Then, she tried to look into iterative solutions in general through Google, and also checked her previous practice.

Next time, go through a test case, do some analysis on the test case. Draw some diagram, help yourself to analyze, at least behaves like a teacher.

2. Things to work on through the practice?
queue -> stack -> opposite order to push into stack

3. Can you describe the process using your own words, a few of drawings to help the thinking process?

First, read the wiki article about stack.

Let us work on a simple test case:

The preorder traversal of tree: 1 2 3 4 5 6 7
When the root node 1 is visited, 2 and 5 should be added to some data structure, 3 and 4 will be added after 5, but output of 3 and 4 should be before 5.
In other words, the data structure should accommodate last in first out feature. So, it is stack!
Once stack is chosen to use, then work out the simple tree first with 3 nodes:

preorder traversal: 1 2 5
so, push 1 into stack, and then, pop out. 5 is pushed in stack first, and then it is turn of 2.

Next, work on the test case: tree - preorder traversal 1 2 3 4 5 6 7
1 is pushed into stack,
1 is on the top of stack, 1 is popped out,

1's right child 5 is pushed into stack,
1's left  child 2 is pushed into stack,

2 is popped out from stack,

2's  right child 4 is pushed into stack,
2's  left  child 3 is pushed into stack,

3 is popped out from stack,
4 is popped out from stack,

5 is popped out from stack,

5's right child 7 is pushed into stack,
5's left  child 6 is pushed into stack.

6 is popped out from stack,
7 is popped out from stack.

3. Most favorite problem solving using stack?

HackerRank: string algorithm - Reverse Shuffle Merge (IV)

warmup practice - C# practice code

Second practice:

C# code

so many bugs in second practice:
1. confused on skip, add array --, ++; line 71, line 80 did the opposite.
2. string reverse, char[], string, Array.Reverse etc. lookup
3. add one more test case: "abcacb",
    b in stack, c in stack, then, run into a, pop up c, and pop up b, let 'a' in the stack. Two in row pop up in stack. While loop is tested on line 64 - 67.
4. while statement from line 64 - 67, fix compile error.
   both are ok to compile:

(char)stack.Peek() > runner)
(char)stack.Peek() - runner > 0)

Third practice:

The code passes HackerRank online test cases as well.

A few good changes:
1. add comment from line 67 - line 72, test case: "abcacb",
use test case, stack top -'c' is removed, help to ensure the code is correct.
2. line 73, avoid bug to overwrite the variable runner, create a new variable called backTracked.

C# practice

August 8, 2016

Work on facebook code lab, preorder iterative solution. Chicken out! Forget to enforce the rule, right child goes to stack first, and then, left child goes to stack afterwards. And then, instead, nervousness kicked in, gave up in 5 minutes, looked up blogs.

Need more practice!

3 smart choices to ask myself: 

stack vs queue ->
left, right who goes first ->
enforce rule, null pointer will not go into stack, save time ->

one node ->
3 node tree - complete binary tree ->
7 node tree - complete binary tree

Leetcode: Maximum product subarray

August 10, 2015

Find the contiguous subarray within an array (containing at least one number)
which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Two approaches, one is dynamic programming DP implementation, another is the greedy method.

DP solution:

https://github.com/jianminchen/MaximumProductSubarray/blob/master/MaximumProductSubarray1.cs

Greedy algorithm:
read the blog first,
http://fmarss.blogspot.ca/2014/10/leetcode-solution-maximum-product.html

and then, convert it to C# programming language, 

https://github.com/jianminchen/MaximumProductSubarray/blob/master/MaximumProductSubarray2.cs

Leetcode: Jump Game

June 29, 2015

Problem statement:

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Spent some time to go over the blogs, and found this one with good illustration. So, write some c# code and then get first hand experience. 目标是会写代码, 不一定是最优. 加强C#练习. 把C++, Java的代码改为C#. 从最笨的方法开始.


http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html

Go through the code practice using C#:
https://github.com/jianminchen/jumpGame/blob/master/Program.cs