{"id":377,"date":"2020-03-13T09:13:00","date_gmt":"2020-03-13T09:13:00","guid":{"rendered":"https:\/\/danwritescode.com\/?p=377"},"modified":"2020-07-08T01:33:33","modified_gmt":"2020-07-08T01:33:33","slug":"genomic-range-query-codility-100-correct-javascript-solution","status":"publish","type":"post","link":"https:\/\/danwritescode.com\/genomic-range-query-codility-100-correct-javascript-solution\/","title":{"rendered":"Genomic Range Query – Codility 100% Correct Javascript Solution"},"content":{"rendered":"\n
The genomic range query problem can be solved efficiently if we treat the sequances as a string instead of an array.<\/p>\n\n\n\n
The simplest solution I found is to exatract the substring between P[k] and Q[k] and analyse try to find the lowest impact element on each substring. Start from A, continue with C and G. If any of these are found, skip to the next K and save the impact. If none of them are found, then the impact is maximum (4) so add that to the results array.<\/p>\n\n\n\n
Here is my Javascript solution with complexity O(N + M)<\/strong>:<\/p>\n\n\n\nfunction solution(S, P, Q) {\n results = []\n impact = {'A':1, 'C':2, 'G':3, 'T':4}\n for (let i=0; i<P.length;i++){\n let analyze = S.substring(P[i],Q[i]+1)\n if (analyze.indexOf('A')!== -1) {\n results[i] = 1\n continue\n }\n if (analyze.indexOf('C')!== -1) {\n results[i] = 2\n continue\n }\n if (analyze.indexOf('G')!== -1) {\n results[i] = 3\n continue\n }\n results[i] = 4\n\n }\n return results\n}<\/code><\/pre>\n\n\n\n