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

Sunday watching: Jamie Dimon to HBS MBA Class of 2009

March 6, 2016

Spend time to relax this Sunday, and enjoy the video from Harvard business school:

https://www.youtube.com/watch?v=9T9Kp4NE5l4

Take some notes, and enjoy the teaching.

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

March 5, 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:

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)

Let us walk through this binary search algorithm using test case GAAATAAA.
int low = 0;
int high = n; // n = 8
int need = 8/4 = 2
int[] cnt = {6, 0, 1, 1}   // "ACGT"
mid = 4,
so, copy cnt to tmp[],
and then, first half, take it away, see left half meet the standard:
tmp[i]<=2,  i = 0, ..., 3
because first half contains 3 'A', and then, tmp[0] = 3,

deal with second half, go through a loop:
get confused, let us debug through the code.

debug through the code, still confuse! 
Java code:
https://gist.github.com/jianminchen/d01faa03ca9b06696db3
C# code
https://gist.github.com/jianminchen/76dffc51880a80279f25

April 28, 2016
Come back to the problem on binary search solution, figure out the design:
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).