Find a path with minimum maximum value in the matrix

July 14, 2018

Introduction

It is the extended algorithm and binary search algorithm can be applied. The most important is to lower down the time complexity to be controllable. I took the major hint from the mock interviewer and then we had discussion of time complexity. I did learn a lot from this mock interview.

Algorithm discussion

Here is the discussion transcript.

Actionable items

The peer gave me a few advice. Read two books, one is cracking code interview. One is elements of programming interview. And also we discuss how efficient we can do to have mock interview together, how often we can meet. The peer is in Asian country, I am in Canada.

The second advice is to get Leetcode subscription by month, $30/ month. There are a lot of similar algorithms discussed in those paid subscription.

We had discussion about Leetcode algorithm practice. The peer completed around 500 algorithms. But I have around 100 algorithms so far only.

Another discussion is to give each other 10 Leetcode hard level algorithms you have worked on since last meeting. And ask the peer to work on the hard level algorithm one by one in 5 minutes, and then give hint to help if the peer cannot solve. The peer said that it will not work for him.

Lessons learned

When I search the solution, I have to try to find the optimal time complexity as soon as possible. Please have an open discussion with the peer as early as possible. 

What is the brute force solution and time complexity? Can we lower the upper bound of algorithm?

For the algorithm to find minimum maximum value in the path, we have to find the range of value of matrix first, and use it to measure the time complexity of the algorithm. 

Statistics

Meeting time July 14, 2018 9:00 AM PST - 11:10 AM PST

First the peer worked on the infix expression to binary expression tree, and then I worked on the two algorithms, discussion of "Find a path with minimum maximum value in the matrix".

Being an interviwee: Root of a number

April 21, 2018

Introduction

It is 12:00 PM mock interview. I have experience to work on the algorithm root of a number over 10 ten times, 5 for interviewer, 5 for interviewee. The peer has strong talent with 1st place twitter big data hackathon. The peer worked on decrypt the message algorithm first, I rated him top 5 - 10% in all over 200 peers I worked last 12 months.

Mock interview

I like to write a binary search and also apply some technique I saw recently using integer to count the numbers.

The peer challenged me about the termination base case, 0.001 is the error range, how I assert that two values are equal using 0.001?

Here is my C# code.

Being an interviewer: Root of a number

March 28, 2018

Introduction

It is a binary search algorithm called root of a number. The hint I gave in the mock interview as an interviewer is to explain how many numbers to search for x = 8, n = 3, it is from 0, incremented by 0.001 to 8, total is 8000 numbers to search.

Binary search algorithm

Here is the binary search algorithm I reviewed written by the peer. The algorithm still has issues to pass a few test cases. I like to look into as well.

I like to get organized and review all my past practice.

Code review

Actually the code should be updated in two places:
1. Line 44 and 45, return (double) m/ 1000;
2. Line 56, return (double) s/ 1000;

The argument is that when s == e on line 37, the return value should be s, not -1 or 0.0.

Incremental value 

It is better to change the design, and use 0.0001 as a different number to apply binary search. Here is C# code.

Given the example x = 8, n = 3, instead of search 8000 numbers, we choose to search 80,000 using binary search. Incremental value is 0.0001 instead of 0.001.

Being an interviewer, it takes some time to figure out how to guide the peer to lead the optimal solution and pass all test cases.

Binary search practice

Sept. 22, 2017

Introduction

I had a mocking at 10:00 pm and then I was told to write the program to find a number using binary search. I failed 5 out of 6 test cases, index out of range, and then I was told to comment out the code of binary search function, and then nail down the bug related to implicit typing "var" on line 47.

Algorithm practice 

My binary search practice is here.

Coding with style 

I spent almost 40 minutes to chat with the peer about coding. I really like the conversation between two programmers. I advised the peer to write self-documented code, in other words, do not write variable name l, h which l stands for low and h stands for high. Express the intent, define a meaningful explanation variable. And also I advised the peer to do whiteboard testing, and showed him an example, run the code line by line and execute the code with the result calculated by myself.

Write simple and clean code

The peer asked me how I can have so much time to play hackerrank contest, ask code review algorithm questions, and then write blogs.

I shared a few things:

1. The blog I did code review for myself, the triangle algorithm.

2. Edit distance dynamic programming post on quora.com. The link is here.

Thoughts after mocking

I think that writing coding blog is easier compared to write code at work. To ask a question on code review website is also easy compared to solve problems at work. I think that the experience of writing blogs is very rewarding experience, my blog is becoming my best reading library.

Leetcode 33: Search in Rotated Sorted Array

Sept. 16, 2017

Introduction

It is the wonderful learning opportunity for me to practice the algorithm again last night at 10:00 pm. I chose to write the idea I thought about and read about, but I had not written it before. The experience told me that binary search basically is also like a depth first search, the most important is to work on base case.

The more detail is like this, I spent first 15 minutes to exchange ideas with the peer, and then only 13 minutes left, I need to write some code, and I chose to write a binary search combining normal binary search in sorted array and shift array binary search. My argument is that the normal one is just special case of shifted array binary search. The iterative solution is hard to avoid duplicate logic and coding. I just could not believe that I made it the first writing without any bug or grammar error.


Leetcode 33 is a medium algorithm, I wrote down the algorithm in less than 13 minutes, and most important thing I did is to move base case "middle value" (line 29 - 32) to the first thing inside the while loop, moved those 4 lines out of if block from line 36 to 46.

Tip to share 

I got the complaint about my practice of binary search tree. The peer told me that the most important part is to work on middle value in the binary search tree. Focus on middle value, do not consider start value at all.

Algorithm practice 

C# code practice is here. 

Binary search

Sept. 6, 2017

Introduction

It is so interesting to write a binary search algorithm. First 5 writing I found out the issue every time, edge cases like middle value expression to avoid overflow, less and equal case. This time I found out a new issue, verbose code. How can I solve the issue?

Algorithm practice

C# practice is here.

binary search - a blog written in Chinese

March 18, 2017

Introduction

Sometimes Julia likes to read a blog written in Chinese, this binary search article is well-written by a facebook engineer, graduated from Syracuse university. Julia tried to learn more about tail recursion, and a few other things discussed in the article.

Learning is fun, specially in Chinese. Julia will try to choose a few topics in the article and continue to do some research.

Study of binary search 

binary search in "Rotated Sorted Array"

Limitation of array operation, O(1) to look up but O(n) for deletion and insertion

binary search -> work on sorted array -> binary search tree -> self-balanced binary search tree

Statistics 

Time to read a blog written in Chinese- binary search - 30 minutes  ( ended at 1:03pm)
Read the article back and forth 3 times

20 minutes to read self-balanced binary search tree  (start:   end: )

Actionable Item

Read one more blog about management and leadership.

Hackerrank - woman codesprint #3 - Hackathon shirts

March 12, 2017

Problem statement

C# code submission in the contest, score maximum score 40.

She spent a few hours on Hackathon Shirts. She thought about test cases she should choose more carefully. Two algorithms are involved, one is merging interval algorithm, the other is binary search algorithm. Very good workout.

Facts to share

Julia still made a bug in her writing after 4 - 5 times to practice merging intervals as an algorithm. Why? Because she depends on her memory of the algorithm, do not start from the beginning of analysis, what test cases she should cover when she finishes the coding. She missed the previous interval end value, she should check maximum of two values instead.

Julia,
rely on your past practices,
it is not to test how good your memorize the algorithm.
But always,

always start with 

the reasoning, 

test cases. 

Learn from your sinking sand lessons.

Leetcode 15: 3 sum ( II)

Dec. 26, 2016

Problem statement:
https://leetcode.com/problems/3sum/

Review the algorithm:

Previous work:
http://juliachencoding.blogspot.ca/2016/05/leetcode-17-3-sum.html

Array.BinarySearch

Code review:
http://codereview.stackexchange.com/questions/37922/given-an-array-find-any-three-numbers-which-sum-to-zero?rq=1

The idea used in the above code review, time complexity is O(n*n*logn), time limit exceed.

Here is C# written by Julia:

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

Highlights of improvement:

1. Use Array.ToList() API;  2. Write a function PrepareKey()
https://gist.github.com/jianminchen/d17ad71a561193984e75ab4e7fb91073

2. Comment out the statement:
//int[] searchArray = nums.Skip(j + 1).ToArray();  // O(n) -> make algorithm O(n*n*n)
https://gist.github.com/jianminchen/cbc62795cc5eca621c395a7a5dc3f6bd

Two pointers technique 

Best solution is to use two pointers, therefore, time complexity is O(n*n) instead.

May, 2016
http://juliachencoding.blogspot.ca/2016/05/leetcode-17-3-sum.html

Code review and improve C# implementation on Dec. 26, 2016:
https://gist.github.com/jianminchen/9c62e27297ff94052320160b6967a61c

Stackexchange.com code review link:
http://codereview.stackexchange.com/q/150920/123986

Good news! win Best Question badge (over 10 up-votes) on stackexchange.com, gain 55 reputation on this 3 sum question. Less than 24 hours after publishing.

Two versions of code from code review:
1. From the code review:
http://codereview.stackexchange.com/a/150938/123986
C# code:
https://gist.github.com/jianminchen/dfebe273c5beca0fbbb52981f3934ded

2. From code review:
http://codereview.stackexchange.com/a/150952/123986

C# code:
https://gist.github.com/jianminchen/9ba704a49e740abad0cef99b4d760b69

HackerRank: Bear And Steady Gene - binary search algorithm (VI)

April 28, 2016

Previous blog on binary search on Bear and Gene algorithm:

http://juliachencoding.blogspot.ca/2016/03/hackerrank-bear-and-steady-gene-binary.html

Come back to the problem on binary search solution, figure out the design:

Problem statement:

https://www.hackerrank.com/contests/hourrank-6/challenges/bear-and-steady-gene  

A gene is represented as a string of length n (where n is divisible by 4), composed of the letters A, C, T, and G. It is considered to be steady if each of the four letters occurs exactly n4 times. For example, GACT and AAGTGCCTare both steady genes.

Study code using binary search:

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

https://gist.github.com/jianminchen/395eb9e76fe19cc9338f

Comment:
Binary search is better than linear search using two pointers.

Brute force O(n^2) -> linear search O(n) -> Binary search O(logn) <- Not True!

Java code:
https://gist.github.com/jianminchen/d01faa03ca9b06696db3
C# code
https://gist.github.com/jianminchen/76dffc51880a80279f25

First, go through two test cases: "GTTCCAAA" and "GAAATTCC"

1. "GTTCCAAA",

Binary search is doing this way:
Biggest value of search string length is 8.
First, divide range from 0 to 8 into half, 4
Find first string with length 4,
one is "GTTC", one is "CAAA",
and then, remove count of first half, rest string (two parts, seperated) "CAAA", since A is repeated 3 times, not in the range;
instead of stopping, wrongly conclude that 4 is not high value, go through all the possible substring with length 4, by sliding window of search string: "GTTC" forward from left to right, but keep the same window size
"GTTC" -> "TTCC"->"TCCA"->stop here, since "TCCA" is removed from counting of GENES="ACGT", fit into the requirement.

Next, low=0, high=4, mid = 2,

Because both test cases with one 'A' to replace, Julia figured out through the debugging:

The slide window of fixed length technique,
How to slide?
Which direction to slide?

Kind of clever in design.
Time complexity analysis: length search using binary search, n - length of string, O(log n) times; each search for length m, go over each string once, since using calculated counting array, only do add one/ remove one at a time, one char only does the work once. So, it is O(n) on this.

Total time complexity: O(n logn)
Conclusion: this binary search is not better than linear search is previous blog (IV). 

Leetcode 33: Search in sorted rotated array

March 23, 2016

understand the algorithm - good analysis graph in the following blog:
http://fisherlei.blogspot.ca/2013/01/leetcode-search-in-rotated-sorted-array.html


using this analysis in the blog:
First, Julia, you have to find out which half is sorted; only one of them;
Second, use sorted half to determine if the search is in the sorted half or not;
Then, you go to sorted half/ unsorted half.

Code can be optimized, if it is in sorted half, then, go to normal binary search
otherwise, go to unsorted - modified binary search - use recursive to write a solution first.

http://bangbingsyb.blogspot.ca/2014/11/leetcode-search-in-rotated-sorted-array.html


Julia, in your practice, you discuss that the middle point is a peak element/ valley element or not; and then, both halves are sorted, which is the special case.

Lesson learned:

1. In your analysis, you have to make the test case as simple as possible, as you see in the above blog:
use 0 -7,
原数组：0 1 2 4 5 6 7
情况1：  6 7 0 1 2 4 5    起始元素0在中间元素的左边
情况2：  2 4 5 6 7 0 1    起始元素0在中间元素的右边

2. And then, you have to be careful, how many cases are then discussed. The above, two cases, using 0 as search element

3. 两种情况都有半边是完全sorted的。根据这半边，当target != A[mid]时，可以分情况判断：
Actually, you should add one more restriction, search half is sorted in ascending order. 

because the half of 6 7 0 1, 6 > 1, in the descending half, it must include going up and then going down. but, 
in the ascending half, 1 2 4 5, just pure ascending. <- you can argue that, it is a fact! 

HackerRank: Bear And Steady Gene - Binary Search (II)

March 6, 2016

Problem statement:

https://www.hackerrank.com/contests/hourrank-6/challenges/bear-and-steady-gene  

A gene is represented as a string of length n (where n is divisible by 4), composed of the letters A, C, T, and G. It is considered to be steady if each of the four letters occurs exactly n4 times. For example, GACT and AAGTGCCTare both steady genes.

Study code using binary search:

cannot figure out the design - confused!
https://gist.github.com/jianminchen/d01faa03ca9b06696db3

This one is easy to follow
https://gist.github.com/jianminchen/395eb9e76fe19cc9338f

Julia's C# practice code:
https://gist.github.com/jianminchen/af1b3c064c523444463f

Algorithm talk:
Work on test case GAAATAAA, let me explain the idea using binary search.

            A1 = Math.Max(0, A1 - n / 4);  // test case: GAAATAAA, A1 = 4 
            C1 = Math.Max(0, C1 - n / 4);  // C1 = 0 
            G1 = Math.Max(0, G1 - n / 4);  // G1 = 0
            T1 = Math.Max(0, T1 - n / 4);   // T1 = 0

            if (A1 == 0 && C1 == 0 && G1 == 0 && T1 == 0)
            {
                return 0;   //
            }

            int ans = n;   // default value is maximum value - string length
            for (int i = 0; i < n; i++)  // go through a loop, start from 0 to n-1. 
            {
                if (A[n] - A[i] < A1 || C[n] - C[i] < C1 || G[n] - G[i] < G1 || T[n] - T[i] < T1) // substring position from i to n, check the count of A, C, G, T
                    break;

                int l = i + 1, r = n;  // left, right two pointer
                while (l < r)
                {
                    int mid = (l + r - 1) / 2;
                    if (A[mid] - A[i] < A1 || C[mid] - C[i] < C1 || G[mid] - G[i] < G1 || T[mid] - T[i] < T1) // not enough
                        l = mid + 1;   // set left pointer to mid + 1
                    else
                        r = mid;      
                }

                ans = Math.Min(ans, l - i);   // substring is from i to l,
            }

            return ans;

In other words, GAAATAAA,

i = 0, l = 1, r = 8,
find ans = Math.Min(ans, l-i)   <-  ans = 6, l = 6

i = 1,
find ans = Math.Min(ans, l-i)  <- ans = 5, l = 6, i=1

i = 2,
find ans = Math.Min(ans, l-i)  <- ans = 5, l = 7, i=2

i =3; 
find ans = Math.Min(ans, l-i)  <- ans = 5, l = 8, i=3

i=4
break the for loop
if (A[n] - A[i] < A1 || C[n] - C[i] < C1 || G[n] - G[i] < G1 || T[n] - T[i] < T1)

                    break;
since A[n] - A[i]  =  3 < A1 = 4, TAAA, we need the substring at least 4 of A

comment:
This algorithm uses extra space for ACGT count for each i from 0 to n-1, total space is less than 1MB. 

int[] A = new int[500500]; int[] C = new int[500500]; int[] G = new int[500500]; int[] T = new int[500500]; 4 bytes for int, then 500K x 4 x 4 = 8M bytes