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).

HackerRank: Bear and Steady Gene algorithm (IV)

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.

Julia did 3 practice code using C#, but she likes one of solutions using Java, and then, she spent 5 minutes to convert it to C#.

study code:
Java code implementation to study:
https://gist.github.com/jianminchen/d52ced38de0bffa2d9e8

Julia's fourth practice:
use two pointers, sliding window, linear time solution

https://gist.github.com/jianminchen/0892107fc0f6b6bec7a0

Julia's comment:
Julia learned a few things through the code:
1.  Declare cnt array using size of 256, ascii code is 256. So, ACGT shoud be ok.
2.  Declare a string "ACGT", and then the code uses 'A', 'C', 'G', 'T' only once.
3. Only two loops, first loop, variable l - left pointer from 0 to n-1.
    second while loop, move r pointer if cnt arrray is bigger than mx - minimum
  while (cnt['A'] > mx || cnt['C'] > mx || cnt['T'] > mx || cnt['G'] > mx) {

How to paraphrase this conditional checking?
Let us go through the test case "GAAATAAA", 
cnt['A'] = 6, cnt['C'] = 0, cnt['G']= 1, cnt['T'] = 1
mx = 2, 
starting from G, and then, while loop <- get in, 
G-> GA->...->GAAATA, cnt['A'] = 2, cnt['G'] = 0,

now, it is time to exit while loop. <- making sense. Because cnt array contains the count 
for rest of substring "GAAATA", requirement is "none of 'ACGT" is more than 2".



April 14, 2016

I put the for loop into a standalone function, and then, add some comment for the function, explain the design. Basically, it is using sliding window. 

Here is the link of code, which passes HackerRank as well. 
https://gist.github.com/jianminchen/9b02beab326b2bfcd4b524f219d2946f

statistics:
This post is one of most viewed so far, over 130 views, from March 5 to April 13, 2016.

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.