Saturday, May 23, 2015

Prefix Sums - GenomicRangeQuery

Here is another codility problem solution from the codility lessons (GenomicRangeQuery-Find the minimal nucleotide from a range of sequence DNA..) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.




// you can also use imports, for example:
import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
	HashMap < Integer, Integer > ListOfA = new HashMap < Integer, Integer > ();
	HashMap < Integer, Integer > ListOfC = new HashMap < Integer, Integer > ();
	HashMap < Integer, Integer > ListOfG = new HashMap < Integer, Integer > ();
	HashMap < Integer, Integer > ListOfT = new HashMap < Integer, Integer > ();
	public int[] solution(String S, int[] P, int[] Q) {
		// write your code in Java SE 8
		int sum = getSum(S);
		fillMap(S);
		int[] queries = new int[P.length];
		for (int i = 0; i < P.length; i++) {
			int startIndex = P[i];
			int endIndex = Q[i];
			int sumA = ListOfA.get(endIndex) - ListOfA.get(startIndex);

			if (S.charAt(startIndex) == 'A') sumA++;

			if (sumA > 0) {
				queries[i] = 1;
			} else {
				int sumC = ListOfC.get(endIndex) - ListOfC.get(startIndex);
				if (S.charAt(startIndex) == 'C') sumC++;

				if (sumC > 0) {
					queries[i] = 2;
				} else {
					int sumG = ListOfG.get(endIndex) - ListOfG.get(startIndex);
					if (S.charAt(startIndex) == 'G') sumG++;

					if (sumG > 0) {
						queries[i] = 3;
					} else {
						int sumT = ListOfT.get(endIndex) - ListOfT.get(startIndex);
						if (S.charAt(startIndex) == 'T') sumT++;

						if (sumT > 0) {
							queries[i] = 4;
						}
					}
				}
			}

			// System.out.println(queries[i]+"========"+P[i]+"========"+Q[i]);
		}

		// System.out.println(S);

		return queries;
	}

	private void fillMap(String S) {
		int sumA = 0;
		int sumC = 0;
		int sumG = 0;
		int sumT = 0;
		int len = S.length();
		for (int i = 0; i < len; i++) {
			char c = S.charAt(i);
			switch (c) {
				case 'A':
					sumA++;
					break;
				case 'C':
					sumC++;
					break;
				case 'G':
					sumG++;
					break;
				case 'T':
					sumT++;
					break;

			}
			ListOfA.put(i, sumA);
			ListOfC.put(i, sumC);
			ListOfG.put(i, sumG);
			ListOfT.put(i, sumT);


		}

	}
	private int getSum(String S) {
		int sum = 0;
		int len = S.length();
		for (int i = 0; i < len; i++) {
			sum += mapChartoInt(S.charAt(i));
		}
		return sum;

	}
	private int mapChartoInt(char c) {
		int mappedVal = -1;
		switch (c) {
			case 'A':
				mappedVal = 1;
				break;
			case 'C':
				mappedVal = 2;
				break;
			case 'G':
				mappedVal = 3;
				break;
			case 'T':
				mappedVal = 4;
				break;

		}
		return mappedVal;
	}
}

No comments:

Post a Comment