HackerRank - Bear and Steady Gene

Problem statement

First version:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

{
{
/*
* Nov. 28, 2016
*
*/
static void Main(string[] args)
{
int number = practice(8, "GAAATAAA");
}

/*
* Nov. 28, 2016
*
*/
private static int practice(int n, string input)
{
int[] a = new int;

for (int i = 0; i < n; i++)
{
a[input[i]]++;
}

int ans = Int32.MaxValue;
int index = 0;
for (int i = 0; i < n; i++)
{
a[input[i]]--;
while (valid(n, a) && index <= i)
{
ans = Math.Min(ans, i - index + 1);
a[input[index]]++;
index++;
}
}

return ans;
}

private static bool valid(int n, int[] a)
{
int A, G, T, C;
A = a['A'];
G = a['G'];
T = a['T'];
C = a['C'];
if (A <= n / 4 && G <= n / 4 && T <= n / 4 && C <= n / 4) return true;
return false;
}
}
}

Based on the code review on this post, I wrote a new version:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

{
{

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:
* https://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;

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;
}
}
}

1. Line 26 - 36, add 4 test cases, with 4 postcondition assertions
2. Function name is changed to minChange
3. Line 61, array of size 4 is declared instead of 1007
5. Variable names are changed, left, right, two pointers, move forward only
6. Added two explanations for variables c1 and c2 to avoid a complicated expression
7. Valid function is declared using a for loop

• In C#, method names should be PascalCased, not camelCased.
• In minChange, you should use meaningful variable names for a, c, c2
• In minChange, you can set var ans = int.MaxValue, unless there is a compelling reason avoid using Int32 when you can use int, same with Int16 vs short or Int64 vs long.
• In indexOf, you can use a const string code = "ACGT"; instead. This gives some compiler optimizations.
• In valid, (and minChange) you should use meaningful parameter names, n and a don't have any contextual meaning.
• I also try to figure out how to help user understand left pointer needs to move forward, highlight the sliding left pointer one step forward in the function minChange: after the line: ans = Math.Min(ans, right - left + 1); Because I did not get the idea of moving left pointer as well until I debug the code with those 4 test cases. Any advice related to marketing the idea, those 3 lines of code: char c2 = input[left]; a[indexOf(c2)]++; left++; Nov 29 '16 at 6:11
• It would be a lot more apparent if you used meaningful variable names for a and c2. Nov 29 '16 at 21:05
• Great advice, "int[] a " is better to name "int[] geneChars" (gene chars's count), "char c2" is better to name "char moveOut" (move out from replaced substring). Nov 29 '16 at 21:46