Solution to Genomic-Range-Query by codility
Question: http://codility.com/demo/take-sample-test/genomic_range_query Question Name: GenomicRangeQuery This is a typical case that uses more space for less time.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | def solution(S, P, Q): result = [] DNA_len = len(S) mapping = {"A":1, "C":2, "G":3, "T":4} # next_nucl is used to store the position information # next_nucl[0] is about the "A" nucleotides, [1] about "C" # [2] about "G", and [3] about "T" # next_nucl[i][j] = k means: for the corresponding nucleotides i, # at position j, the next corresponding nucleotides appears # at position k (including j) # k == -1 means: the next corresponding nucleotides does not exist next_nucl = [[-1]*DNA_len, [-1]*DNA_len, [-1]*DNA_len, [-1]*DNA_len] # Scan the whole DNA sequence, and retrieve the position information next_nucl[mapping[S[-1]] - 1][-1] = DNA_len-1 for index in range(DNA_len-2,-1,-1): next_nucl[0][index] = next_nucl[0][index+1] next_nucl[1][index] = next_nucl[1][index+1] next_nucl[2][index] = next_nucl[2][index+1] next_nucl[3][index] = next_nucl[3][index+1] next_nucl[mapping[S[index]] - 1][index] = index for index in range(0,len(P)): if next_nucl[0][P[index]] != -1 and next_nucl[0][P[index]] <= Q[index]: result.append(1) elif next_nucl[1][P[index]] != -1 and next_nucl[1][P[index]] <= Q[index]: result.append(2) elif next_nucl[2][P[index]] != -1 and next_nucl[2][P[index]] <= Q[index]: result.append(3) else: result.append(4) return result |