Short Problem Definition:
Find the minimal nucleotide from a range of sequence DNA.
Link
Complexity:
expected worst-case time complexity is O(N+M);
expected worst-case space complexity is O(N)
Execution:
Remember the last position on which was the genome (A, C, G, T) was seen. If the distance between Q and P is lower than the distance to the last seen genome, we have found the right candidate.
Solution:
def writeCharToList(S, last_seen, c, idx): if S[idx] == c: last_seen[idx] = idx elif idx > 0: last_seen[idx] = last_seen[idx -1] def solution(S, P, Q): if len(P) != len(Q): raise Exception("Invalid input") last_seen_A = [-1] * len(S) last_seen_C = [-1] * len(S) last_seen_G = [-1] * len(S) last_seen_T = [-1] * len(S) for idx in xrange(len(S)): writeCharToList(S, last_seen_A, 'A', idx) writeCharToList(S, last_seen_C, 'C', idx) writeCharToList(S, last_seen_G, 'G', idx) writeCharToList(S, last_seen_T, 'T', idx) solution = [0] * len(Q) for idx in xrange(len(Q)): if last_seen_A[Q[idx]] >= P[idx]: solution[idx] = 1 elif last_seen_C[Q[idx]] >= P[idx]: solution[idx] = 2 elif last_seen_G[Q[idx]] >= P[idx]: solution[idx] = 3 elif last_seen_T[Q[idx]] >= P[idx]: solution[idx] = 4 else: raise Exception("Should never happen") return solution
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.




