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

Leetcode 16 - 3 sum closest

May 17, 2016

Julia likes to write some code after she reads the blog:

http://www.cnblogs.com/TenosDoIt/p/3649607.html

Write C# practice on Leetcode 16 - 3 sum closest solution:

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

First practice on Leetcode 16 - 3 sum closest solution on 

https://github.com/jianminchen/Leetcode_C-/blob/master/3sumCloset.cs

Previous blog:

http://juliachencoding.blogspot.ca/2016/01/leetcode-1-15-15-two-sum-3-sum-3-sum.html

Question and Answer:

1. What do you learn through the practice this time?

Julia learns the importance to do static analysis on the code. Do not rush, make sure every variable/ name is making sense, every line of code is best she can present, every executable path should be examined. Every scope of variable is close to minimum as possible. Walk through the examination steps loudly. 

2. What common steps Julia likes to build a ritual after her first writing - C# code - after she failed to present a two sum algorithm on May 4, 2016? 

Answer:

1. Julia likes to examine every line of code, see if she can improve the presentation; 

2. Check every variable, scope, meaningful name

3. Check every executable path, make sure that no bug

4. What test case will be executed on the line. 

5. Avoid early return error, other common errors. 

6. Read the code, speak out what she is doing on reviewing of each line, each variable. Talk about the change she likes to make, thing found needs to be taken care of.   

3. What is most important to solve the problem? 

Using two sum problem solving technique, extend the method to solve the 3 sum closest one. 

The idea is most important and also know how to do time complexity analysis - O(n^2) solution - best one. 

Since O(n^2) is the best time complexity we can solve the problem, sorting takes less than O(n^2); certainly, array can be sorted first. 

So, here is the analysis Julia does for the problem - 3 sum closest. 

Idea:

* 1. Sorting takes O(nlogn) for an array

* 2. And then, choose (i, j, k), assuming i<j<k, iterate on variable i,

*   we need to find two sum problem for each i, new target = target - nums[i]

*   since the array is sorted, two pointer solution can be used. One is the beginning

*   of array, another one is the end of the array.

*

*   So, this step 2 process takes O(n^2) time

*

* Overall, the algorithm will take O(n^2) time complexity

*

*

*   read the C# Array API - 10 minutes

*   https://msdn.microsoft.com/en-us/library/6tf1f0bc(v=vs.110).aspx

HackerRank: Bear and Steady Gene algorithm (III)

March 5, 2016

Problem statement: 

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 AAGTGCCT are both steady genes.

Practice 

Julia's 1st practice:

Code is here. 

Score 15 out of 50, there are 2 run time error, failed a few of test cases.

The algorithm ends up in time complexity O(n²), close to brute force solution.

Code study 

C# code implementation to study:

Study code is here. 

Work on two pointers, sliding window, so time complexity is O(n).

Let us go over two pointers algorithm here using example:

Test case string "GAAATAAA", gene string "ACTG". 
Go over C# program a few lines of statements here:

Line 40: 
var a = ReadToken().Select(ch=>"ACTG".IndexOf(ch)).ToArray();

so the array a = [3, 0, 0, 0, 2, 0, 0, 0] is representing the sample string "GAAATAAA", since 'G' is the index of 3 in the string "ACTG", 'A' is 0, 'C' is 1, 'T' is 2. 

Line 44 - 45:
for(int i = 0; i < 4; i++)
   target[i] = Math.Max(0, a.Count(aa => aa == i) - n / 4); 

So the Target[] = [4, 0, 0, 0]. In other words, 4 of A is needed, but C, T, G do not matter.

Line 47 - 51:
if (target.All(t => t == 0))
{
      Write(0);
      return; 
}

If all element in Target is 0, then return 0. Learn to use Array.All method. 

Left, right two pointer (l, r), starting from 0

Declare a sum array

Start a loop, loop on r

   

Add a[r]’s char into sum array,

r ++, r moves to next one

Inside the first loop, another loop for r, continue to move forward

if sums do not reach target 4 of them >= target

 

The test case "GAAATAAA", find substring: "GAAATA". 

Inside the first loop, another loop for left pointer – l

condition: l  <  r

If sums array is bigger than target array, then remove left pointer char count,

then move left pointer to next one, then the substring is reaching the target,

"GAAATA" => "AAATA"

and compare to existing smallest length

"AAATA" is the smallest one.

This algorithm is much easy to follow than the one in the blog - bear and steady gene.   

 

Reference: 

C# code implementation to study, code is here. 

HackerRank: Bear Steady Gene (II)

March 4, 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.


Julia's 1st practice:

https://gist.github.com/jianminchen/80723bae951328a690bb

score 15 out of 50, there are 2 run time error, failed a few of test cases.

The algorithm ends up in time complexity O(n^2), close to brute force solution - O(n^2)

C# code implementation to study:

Readable code, with some analysis.

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

Work on two pointers, sliding window, so time complexity is O(2n) = O(n).

Let us go over two pointers algorithm here using example:
GAAATAAA,
A - count of A, denoted as cA = 6, n/4 = 2, so we have to change 4 of A to other thing.
A - 6 -2  = 4 , 4 of change
C - 0 - 2 = -2
T - 1 -2  = -1
G - 1-2  = -1
So, at least minimum is 4, but a substring containing 4 of A, shortest one is AAAA. But "AAAA" is not a substring of "GAAATAAA"

G  A A A T A A A
0
start
end
Let us find the substring starting from 0, but will include all 4 of A, and then, rest of string will not include any char of "ACGT" more than n/4.
GAAATA, string length is 6.
start - 0, index of 0
end - A, index of 5

continue to move start to next one, 1, then, G is moved out from substring, adjust count of chars.
AAATA can be the substring, so the length is min (6, 5) = 5. Do not need to move end pointer.

next step, start = 2, missing one of A, and then, end has to move to next one until the string fits into requirement.

Every thing should be covered in 20 minutes, problem reading, the design of algorithm, the coding.

So, Julia had second practice, and the code scores 50 out of 50 this time.

https://gist.github.com/jianminchen/61dfe437f82edb9793fc

Conclusion:
After coding, Julia understands the algorithm much better.

1. count of array for substring, cB=[4, -2, -1, -1], so in other words, substring has to contain at least 4 'A', C, G, T does not matter.

So, using CB array, sliding windows of substring GAAATA, each time, end index is moving forward, tracking the substring's char by taking off from CB; in other words, GAAATA, CB will be
[0, -2, -2, -2].

Now, it is easy to understand that GAAATA will be added to the solution set, the length is 6.
line 51, if (cBAllLessThan1(cB)) 
<-add substring to solution set, compare length<- easy to understand now.

2. the code in https://gist.github.com/jianminchen/fae9142eff9a6f9643fc has discussion:

switch(line[0]) {
	case 'A': A--; break;
	case 'C': C--; break;
	case 'G': G--; break;
	case 'T': T--; break;
	}

Julia removed those detail discussion, but her code takes more time. Because she created a bug in her writing. Debugging takes time.

3. Julia's practice in 2015, sliding windows, two pointers:
http://juliachencoding.blogspot.ca/search/label/slide%20window

April 27, 2016
change C# program to make variables more meaningful, matching the design:
code -> GENES <- global string array
function name matches design of two pointers moving.

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

searchStrArray -> searchStrNumber, more meaningful.
https://gist.github.com/jianminchen/b23c4f606a101b9aeec71eff3268db32