java codility training Genomic-range-query

Question

The task is:

A non-empty zero-indexed string S is given. String S consists of N characters from the set of upper-case English letters A, C, G, T.

This string actually represents a DNA sequence, and the upper-case letters represent single nucleotides.

You are also given non-empty zero-indexed arrays P and Q consisting of M integers. These arrays represent queries about minimal nucleotides. We represent the letters of string S as integers 1, 2, 3, 4 in arrays P and Q, where A = 1, C = 2, G = 3, T = 4, and we assume that A < C < G < T.

Query K requires you to find the minimal nucleotide from the range (P[K], Q[K]), 0 ≤ P[i] ≤ Q[i] < N.

For example, consider string S = GACACCATA and arrays P, Q such that:

P[0] = 0    Q[0] = 8
P[1] = 0    Q[1] = 2
P[2] = 4    Q[2] = 5
P[3] = 7    Q[3] = 7

The minimal nucleotides from these ranges are as follows:

    (0, 8) is A identified by 1,
    (0, 2) is A identified by 1,
    (4, 5) is C identified by 2,
    (7, 7) is T identified by 4.

Write a function:

class Solution { public int[] solution(String S, int[] P, int[] Q); } 

that, given a non-empty zero-indexed string S consisting of N characters and two non-empty zero-indexed arrays P and Q consisting of M integers, returns an array consisting of M characters specifying the consecutive answers to all queries.

The sequence should be returned as:

    a Results structure (in C), or
    a vector of integers (in C++), or
    a Results record (in Pascal), or
    an array of integers (in any other programming language).

For example, given the string S = GACACCATA and arrays P, Q such that:

P[0] = 0    Q[0] = 8
P[1] = 0    Q[1] = 2
P[2] = 4    Q[2] = 5
P[3] = 7    Q[3] = 7

the function should return the values [1, 1, 2, 4], as explained above.

Assume that:

    N is an integer within the range [1..100,000];
    M is an integer within the range [1..50,000];
    each element of array P, Q is an integer within the range [0..N − 1];
    P[i] ≤ Q[i];
    string S consists only of upper-case English letters A, C, G, T.

Complexity:

    expected worst-case time complexity is O(N+M);
    expected worst-case space complexity is O(N), 
         beyond input storage 
         (not counting the storage required for input arguments).

Elements of input arrays can be modified.

My solution is:

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        final  char c[] = S.toCharArray();
        final int answer[] = new int[P.length];
        int tempAnswer;
        char tempC;

        for (int iii = 0; iii < P.length; iii++) {
            tempAnswer = 4;
            for (int zzz = P[iii]; zzz <= Q[iii]; zzz++) {
                tempC = c[zzz];
                if (tempC == 'A') {
                    tempAnswer = 1;
                    break;
                } else if (tempC == 'C') {
                    if (tempAnswer > 2) {
                        tempAnswer = 2;
                    }
                } else if (tempC == 'G') {
                    if (tempAnswer > 3) {
                        tempAnswer = 3;
                    }

                }
            }
            answer[iii] = tempAnswer;
        }

        return answer;
    }
}

It is not optimal, I believe it's supposed to be done within one loop, any hint how can I achieve it?

You can check quality of your solution here https://codility.com/train/ test name is Genomic-range-query.

Answer 1

Hope this helps.

public int[] solution(String S, int[] P, int[] K) {
        // write your code in Java SE 8
        char[] sc = S.toCharArray();
        int[] A = new int[sc.length];
        int[] G = new int[sc.length];
        int[] C = new int[sc.length];

        int prevA =-1,prevG=-1,prevC=-1;

        for(int i=0;i<sc.length;i++){
            if(sc[i]=='A')
               prevA=i;
            else if(sc[i] == 'G')
               prevG=i;
            else if(sc[i] =='C')
               prevC=i;
            A[i] = prevA;
            G[i] = prevG;
            C[i] = prevC;
            //System.out.println(A[i]+ " "+G[i]+" "+C[i]);

        }
        int[] result = new int[P.length];

        for(int i=0;i<P.length;i++){
            //System.out.println(A[P[i]]+ " "+A[K[i]]+" "+C[P[i]]+" "+C[K[i]]+" "+P[i]+" "+K[i]);

            if(A[K[i]] >=P[i] && A[K[i]] <=K[i]){
                  result[i] =1;
            }
            else if(C[K[i]] >=P[i] && C[K[i]] <=K[i]){
                  result[i] =2;
            }else if(G[K[i]] >=P[i] && G[K[i]] <=K[i]){
                  result[i] =3;
            }
            else{
                result[i]=4;
            }
        }

        return result;
    }

Answer 2

perl 100/100 solution:

sub solution {
    my ($S, $P, $Q)=@_; my @P=@$P; my @Q=@$Q;

    my @_A = (0), @_C = (0), @_G = (0), @ret =();
    foreach (split //, $S)
    {
        push @_A, $_A[-1] + ($_ eq 'A' ? 1 : 0);
        push @_C, $_C[-1] + ($_ eq 'C' ? 1 : 0);
        push @_G, $_G[-1] + ($_ eq 'G' ? 1 : 0);
    }

    foreach my $i (0..$#P)
    {
        my $from_index = $P[$i];
        my $to_index = $Q[$i] + 1;
        if ( $_A[$to_index] - $_A[$from_index] > 0 )
        {
            push @ret, 1;
            next;
        }
        if ( $_C[$to_index] - $_C[$from_index] > 0 )
        {
            push @ret, 2;
            next;
        }
        if ( $_G[$to_index] - $_G[$from_index] > 0 )
        {
            push @ret, 3;
            next;
        }
        push @ret, 4
    }

    return @ret;
}

Answer 3

Here is my solution. Got %100 . Of course I needed to first check and study a little bit prefix sums.

public int[] solution(String S, int[] P, int[] Q){

        int[] result = new int[P.length];

        int[] factor1 = new int[S.length()];
        int[] factor2 = new int[S.length()];
        int[] factor3 = new int[S.length()];
        int[] factor4 = new int[S.length()];

        int factor1Sum = 0;
        int factor2Sum = 0;
        int factor3Sum = 0;
        int factor4Sum = 0;

        for(int i=0; i<S.length(); i++){
            switch (S.charAt(i)) {
            case 'A':
                factor1Sum++;
                break;
            case 'C':
                factor2Sum++;
                break;
            case 'G':
                factor3Sum++;
                break;
            case 'T':
                factor4Sum++;
                break;
            default:
                break;
            }
            factor1[i] = factor1Sum;
            factor2[i] = factor2Sum;
            factor3[i] = factor3Sum;
            factor4[i] = factor4Sum;
        }

        for(int i=0; i<P.length; i++){

            int start = P[i];
            int end = Q[i];

            if(start == 0){
                if(factor1[end] > 0){
                    result[i] = 1;
                }else if(factor2[end] > 0){
                    result[i] = 2;
                }else if(factor3[end] > 0){
                    result[i] = 3;
                }else{
                    result[i] = 4;
                }
            }else{
                if(factor1[end] > factor1[start-1]){
                    result[i] = 1;
                }else if(factor2[end] > factor2[start-1]){
                    result[i] = 2;
                }else if(factor3[end] > factor3[start-1]){
                    result[i] = 3;
                }else{
                    result[i] = 4;
                }
            }

        }

        return result;
    }

Answer 4

pshemek's solution constrains itself to the space complexity (O(N)) - even with the 2-d array and the answer array because a constant (4) is used for the 2-d array. That solution also fits in with the computational complexity - whereas mine is O (N^2) - though the actual computational complexity is much lower because it skips over entire ranges that include minimal values.

I gave it a try - but mine ends up using more space - but makes more intuitive sense to me (C#):

public static int[] solution(String S, int[] P, int[] Q)
{
    const int MinValue = 1;
    Dictionary<char, int> stringValueTable = new Dictionary<char,int>(){ {'A', 1}, {'C', 2}, {'G', 3}, {'T', 4} };

    char[] inputArray = S.ToCharArray();
    int[,] minRangeTable = new int[S.Length, S.Length]; // The meaning of this table is [x, y] where x is the start index and y is the end index and the value is the min range - if 0 then it is the min range (whatever that is)
    for (int startIndex = 0; startIndex < S.Length; ++startIndex)
    {
        int currentMinValue = 4;
        int minValueIndex = -1;
        for (int endIndex = startIndex; (endIndex < S.Length) && (minValueIndex == -1); ++endIndex)
        {
            int currentValue = stringValueTable[inputArray[endIndex]];
            if (currentValue < currentMinValue)
            {
                currentMinValue = currentValue;
                if (currentMinValue == MinValue) // We can stop iterating - because anything with this index in its range will always be minimal
                    minValueIndex = endIndex;
                else
                    minRangeTable[startIndex, endIndex] = currentValue;
            }
            else
                minRangeTable[startIndex, endIndex] = currentValue;
        }

        if (minValueIndex != -1) // Skip over this index - since it is minimal
            startIndex = minValueIndex; // We would have a "+ 1" here - but the "auto-increment" in the for statement will get us past this index
    }

    int[] result = new int[P.Length];
    for (int outputIndex = 0; outputIndex < result.Length; ++outputIndex)
    {
        result[outputIndex] = minRangeTable[P[outputIndex], Q[outputIndex]];
        if (result[outputIndex] == 0) // We could avoid this if we initialized our 2-d array with 1's
            result[outputIndex] = 1;
    }

    return result;
}

In pshemek's answer - the "trick" in the second loop is simply that once you've determined you've found a range with the minimal value - you don't need to continue iterating. Not sure if that helps.

Answer 5

This program has got score 100 and performance wise has got an edge over other java codes listed above!

The code can be found here.

public class GenomicRange {

final int Index_A=0, Index_C=1, Index_G=2, Index_T=3;
final int A=1, C=2, G=3, T=4; 

public static void main(String[] args) {

    GenomicRange gen = new GenomicRange();
    int[] M = gen.solution( "GACACCATA", new int[] { 0,0,4,7 } , new int[] { 8,2,5,7 } );
    System.out.println(Arrays.toString(M));
} 

public int[] solution(String S, int[] P, int[] Q) {

    int[] M = new int[P.length];
    char[] charArr = S.toCharArray();
    int[][] occCount = new int[3][S.length()+1];

    int charInd = getChar(charArr[0]);

    if(charInd!=3) {
        occCount[charInd][1]++;
    }

    for(int sInd=1; sInd<S.length(); sInd++) {

        charInd = getChar(charArr[sInd]);

        if(charInd!=3)
            occCount[charInd][sInd+1]++;

        occCount[Index_A][sInd+1]+=occCount[Index_A][sInd];
        occCount[Index_C][sInd+1]+=occCount[Index_C][sInd];
        occCount[Index_G][sInd+1]+=occCount[Index_G][sInd];
    }

    for(int i=0;i<P.length;i++) {

        int a,c,g;

        if(Q[i]+1>=occCount[0].length) continue;

        a =  occCount[Index_A][Q[i]+1] - occCount[Index_A][P[i]];
        c =  occCount[Index_C][Q[i]+1] - occCount[Index_C][P[i]];
        g =  occCount[Index_G][Q[i]+1] - occCount[Index_G][P[i]];

        M[i] = a>0? A : c>0 ? C : g>0 ? G : T;    
    }

    return M;
}

private int getChar(char c) {

    return ((c=='A') ? Index_A : ((c=='C') ? Index_C : ((c=='G') ? Index_G : Index_T)));  
}
}

Answer 6

Here is the solution, supposing someone is still interested.

class Solution {
        public int[] solution(String S, int[] P, int[] Q) {
            int[] answer = new int[P.length];
            char[] chars = S.toCharArray();
            int[][] cumulativeAnswers = new int[4][chars.length + 1];

            for (int iii = 0; iii < chars.length; iii++) {
                if (iii > 0) {
                    for (int zzz = 0; zzz < 4; zzz++) {
                        cumulativeAnswers[zzz][iii + 1] = cumulativeAnswers[zzz][iii];
                    }
                }

                switch (chars[iii]) {
                    case 'A':
                        cumulativeAnswers[0][iii + 1]++;
                        break;
                    case 'C':
                        cumulativeAnswers[1][iii + 1]++;
                        break;
                    case 'G':
                        cumulativeAnswers[2][iii + 1]++;
                        break;
                    case 'T':
                        cumulativeAnswers[3][iii + 1]++;
                        break;
                }
            }

            for (int iii = 0; iii < P.length; iii++) {
                for (int zzz = 0; zzz < 4; zzz++) {

                    if ((cumulativeAnswers[zzz][Q[iii] + 1] - cumulativeAnswers[zzz][P[iii]]) > 0) {
                        answer[iii] = zzz + 1;
                        break;
                    }

                }
            }

            return answer;
        }
    }