1
\$\begingroup\$

Problem statement

First version:

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

namespace BearAndSteadyGene2
{
class BearAndSteadyGene2
{               
    /*
     * 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[1007];             

        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;
using System.Threading.Tasks;

namespace BearAndSteadyGene2
{
  class BearAndSteadyGene2
  {

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

Source code link

  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
  4. Function indexOf() is added
  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

Please provide your code review advice. I tring to get C# advice, coding style, and algorithm design advice.

\$\endgroup\$
3
\$\begingroup\$

Just a few comments:

  • 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.
\$\endgroup\$
3
  • \$\begingroup\$ 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++; \$\endgroup\$ – Jianmin Chen Nov 29 '16 at 6:11
  • 1
    \$\begingroup\$ It would be a lot more apparent if you used meaningful variable names for a and c2. \$\endgroup\$ – Ron Beyer Nov 29 '16 at 21:05
  • \$\begingroup\$ 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). \$\endgroup\$ – Jianmin Chen Nov 29 '16 at 21:46
2
\$\begingroup\$

A few more comments:

  • int number = practice(8, "GAAATAAA") - this tells me absolutely nothing about what the called method is about. Give the method a better name.
  • Why 8 in Main, why 1007 in practice, why 4 in valid? Don't use magic numbers.
  • I think it would be more intuitive to write if (A <= n / 4 && G <= n / 4 && T <= n / 4 && C <= n / 4) return true; return false; as return (A <= n / 4 && G <= n / 4 && T <= n / 4 && C <= n / 4);
  • It seems quite awkward to have a class with the same name as the namespace.
\$\endgroup\$
1
  • \$\begingroup\$ I did a research on hackerRank Bear and steady gene algorithm submission, I did study over 100 submissions. One of C++ solution is here:gist.github.com/jianminchen/c6b51207f9cc9b083573, the code works perfectly, so I wrote a C# version. Your review is helpful, but I did work on a new version to overcome those pitfalls. \$\endgroup\$ – Jianmin Chen Nov 30 '16 at 3:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.