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

import java.util.Arrays;
import java.util.HashMap;
class Solution {

   static HashMap<Character, Integer > characterMapping = new HashMap<Character, Integer>(){{
    put('A',1);
    put('C',2);
    put('G',3);
    put('T',4);
  }};

  public static int minimum(int[] arr) {

    if (arr.length ==1) return arr[0];

    int smallestIndex = 0;
    for (int index = 0; index<arr.length; index++) {
      if (arr[index]<arr[smallestIndex]) smallestIndex=index;
    }
    return arr[smallestIndex];
  }

    public int[] solution(String S, int[] P, int[] Q) {
        final char[] characterInput = S.toCharArray();
    final int[] integerInput = new int[characterInput.length];

    for(int counter=0; counter < characterInput.length; counter++) {
      integerInput[counter] = characterMapping.get(characterInput[counter]);
    }

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

    //assuming P and Q have the same length
    for(int index =0; index<P.length; index++) {

      if (P[index]==Q[index]) {
        result[index] = integerInput[P[index]];
        break;
      }
      final int[] subArray = Arrays.copyOfRange(integerInput, P[index], Q[index]+1);
      final int minimumValue = minimum(subArray);
      result[index]= minimumValue;
    }
    return result;
    }
}

Answer 2

The php 100/100 solution:

function solution($S, $P, $Q) {
    $S      = str_split($S);
    $len    = count($S);
    $lep    = count($P);
    $arr    = array();
    $result = array();
    $clone  = array_fill(0, 4, 0);
    for($i = 0; $i < $len; $i++){
        $arr[$i] = $clone;
        switch($S[$i]){
            case 'A':
                $arr[$i][0] = 1;
                break;
            case 'C':
                $arr[$i][1] = 1;
                break;
            case 'G':
                $arr[$i][2] = 1;
                break;
            default:
                $arr[$i][3] = 1;
                break;
        }
    }
    for($i = 1; $i < $len; $i++){
        for($j = 0; $j < 4; $j++){
            $arr[$i][$j] += $arr[$i - 1][$j];
        }
    }
    for($i = 0; $i < $lep; $i++){
        $x = $P[$i];
        $y = $Q[$i];
        for($a = 0; $a < 4; $a++){
            $sub = 0;
            if($x - 1 >= 0){
                $sub = $arr[$x - 1][$a];
            }
            if($arr[$y][$a] - $sub > 0){
                $result[$i] = $a + 1;
                break;
            }
        }
    }
    return $result;
}

Answer 3

Here's a simple javascript solution which got 100%.

function solution(S, P, Q) {
    var A = [];
    var C = [];
    var G = [];
    var T = [];
    var result = [];
    var i = 0;

    S.split('').forEach(function(a) {
        if (a === 'A') {
            A.push(i);
        } else if (a === 'C') {
            C.push(i);
        } else if (a === 'G') {
            G.push(i);
        } else {
            T.push(i);
        }

        i++;
    });

    function hasNucl(typeArray, start, end) {
        return typeArray.some(function(a) {
            return a >= P[j] && a <= Q[j];
        });
    }

    for(var j=0; j<P.length; j++) {
        if (hasNucl(A, P[j], P[j])) {
            result.push(1)
        } else if (hasNucl(C, P[j], P[j])) {
            result.push(2);
        } else if (hasNucl(G, P[j], P[j])) {
            result.push(3);
        } else {
            result.push(4);
        }
    }

    return result;
}

Answer 4

This is my JavaScript solution that got 100% across the board on Codility:

function solution(S, P, Q) {
    let total = [];
    let min;

    for (let i = 0; i < P.length; i++) {
        const substring = S.slice(P[i], Q[i] + 1);
        if (substring.includes('A')) {
            min = 1;
        } else if (substring.includes('C')) {
            min = 2;
        } else if (substring.includes('G')) {
            min = 3;
        } else if (substring.includes('T')) {
            min = 4;
        }
        total.push(min);
    }
    return total;
}

Answer 5

Java, 100/100, but with no cumulative/prefix sums! I stashed the last occurrence index of lower 3 nucelotides in a array "map". Later I check if the last index is between P-Q. If so it returns the nuclotide, if not found, it's the top one (T):

class Solution {

int[][] lastOccurrencesMap;

public int[] solution(String S, int[] P, int[] Q) {
    int N = S.length();
    int M = P.length;

    int[] result = new int[M];
    lastOccurrencesMap = new int[3][N];
    int lastA = -1;
    int lastC = -1;
    int lastG = -1;

    for (int i = 0; i < N; i++) {
        char c = S.charAt(i);

        if (c == 'A') {
            lastA = i;
        } else if (c == 'C') {
            lastC = i;
        } else if (c == 'G') {
            lastG = i;
        }

        lastOccurrencesMap[0][i] = lastA;
        lastOccurrencesMap[1][i] = lastC;
        lastOccurrencesMap[2][i] = lastG;
    }

    for (int i = 0; i < M; i++) {
        int startIndex = P[i];
        int endIndex = Q[i];

        int minimum = 4;
        for (int n = 0; n < 3; n++) {
            int lastOccurence = getLastNucleotideOccurrence(startIndex, endIndex, n);
            if (lastOccurence != 0) {
                minimum = n + 1; 
                break;
            }
        }

        result[i] = minimum;
    }
    return result;
}

int getLastNucleotideOccurrence(int startIndex, int endIndex, int nucleotideIndex) {
    int[] lastOccurrences = lastOccurrencesMap[nucleotideIndex];
    int endValueLastOccurenceIndex = lastOccurrences[endIndex];
    if (endValueLastOccurenceIndex >= startIndex) {
        return nucleotideIndex + 1;
    } else {
        return 0;
    }
}
}

Answer 6

   static public int[] solution(String S, int[] P, int[] Q) {
    // write your code in Java SE 8

    int A[] = new int[S.length() + 1], C[] = new int[S.length() + 1], G[] = new int[S.length() + 1];

    int last_a = 0, last_c = 0, last_g = 0;

    int results[] = new int[P.length];
    int p = 0, q = 0;
    for (int i = S.length() - 1; i >= 0; i -= 1) {
        switch (S.charAt(i)) {
            case 'A': {
                last_a += 1;
                break;
            }
            case 'C': {
                last_c += 1;
                break;
            }

            case 'G': {
                last_g += 1;
                break;
            }

        }
        A[i] = last_a;
        G[i] = last_g;
        C[i] = last_c;
    }


    for (int i = 0; i < P.length; i++) {
        p = P[i];
        q = Q[i];

        if (A[p] - A[q + 1] > 0) {
            results[i] = 1;
        } else if (C[p] - C[q + 1] > 0) {
            results[i] = 2;
        } else if (G[p] - G[q + 1] > 0) {
            results[i] = 3;
        } else {
            results[i] = 4;
        }

    }
    return results;
}