Created
November 29, 2016 01:55
-
-
Save jianminchen/124b33e3d7aa0276e7b6ea4542c8ad5b to your computer and use it in GitHub Desktop.
HackerRank - medium algorithm - Bear and steady gene algorithm - code is reviewed by guideline - http://codereview.stackexchange.com/questions/142808/quick-sort-algorithm/142853#142853
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Diagnostics; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace BearAndSteadyGene2 | |
{ | |
class BearAndSteadyGene2 | |
{ | |
/* | |
* Nov. 28, 2016 | |
* | |
* HackerRank Bear Steady Gene algorithm - medium one | |
* http://juliachencoding.blogspot.ca/search/label/Bear%20Steady%20Gene%20%28II%29 | |
* | |
* code review based on the blog: | |
* http://codereview.stackexchange.com/questions/142808/quick-sort-algorithm/142853#142853 | |
* | |
* code review checklist: | |
* | |
*/ | |
static void Main(string[] args) | |
{ | |
int testCase1 = minChange(8, "GTAAAAAA"); | |
Debug.Assert(testCase1 == 4); | |
int testCase2 = minChange(8, "GATAAAAA"); | |
Debug.Assert(testCase2 == 4); | |
int testCase3 = minChange(8, "GAAATAAA"); | |
Debug.Assert(testCase3 == 5); | |
int testCase4 = minChange(8, "AAAGTAAA"); | |
Debug.Assert(testCase4 == 6); | |
} | |
/* | |
* Nov. 28, 2016 | |
* code review based on the blog: | |
* http://codereview.stackexchange.com/questions/142808/quick-sort-algorithm/142853#142853 | |
* | |
* 1. change the variable name from i -> right, index -> right, | |
* therefore, 2 pointers are very clear: left and right, both pointers moves forward only | |
* 2. First, get the count for each char; | |
* and then, use two pointers, first right point moves forward, the substring | |
* from left to right position will be replaced, stop when the rest of string fits | |
* the requirement: <=n/4. | |
* Record the length; and then, move left pointer until it breaks the requirement. | |
* Continue the iteration on the right pointer again. | |
* 3. Add 4 test cases | |
* 4. error handling - ? | |
* 5. Consider adding postcondition assertions: | |
* Debug.Assert | |
*/ | |
private static int minChange(int n, string input) | |
{ | |
int[] a = new int[4]; | |
for (int i = 0; i < n; i++) | |
{ | |
char c = input[i]; | |
a[indexOf(c)]++; | |
Debug.Assert(indexOf(c) != -1); // add postcondition assertions | |
} | |
int ans = Int32.MaxValue; | |
// two pointers: left and right, both go through O(n) time | |
int left = 0; | |
for (int right = 0; right < n; right++) | |
{ | |
char c1 = input[right]; | |
a[indexOf(c1)]--; | |
while (valid(n, a) && | |
left <= right) | |
{ | |
ans = Math.Min(ans, right - left + 1); | |
char c2 = input[left]; | |
a[indexOf(c2)]++; | |
left++; | |
} | |
} | |
return ans; | |
} | |
private static int indexOf(char c) | |
{ | |
string code = "ACGT"; | |
return code.IndexOf(c); | |
} | |
/* | |
* Nov. 28, 2016 | |
*/ | |
private static bool valid(int n, int[] a) | |
{ | |
for (int i = 0; i < a.Length; i++) | |
{ | |
if (a[i] > n / 4) | |
return false; | |
} | |
return true; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment