Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created November 29, 2016 01:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/124b33e3d7aa0276e7b6ea4542c8ad5b to your computer and use it in GitHub Desktop.
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
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