Codility GenomicRangeQuery (Resolvido)

Depois de um tempo pensando na solução performática para o desafio do codility GenomicRangeQuery. Consegui resolve-lo com O(n+m).

O desafio é esse: https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/

Lendo a questão, a primeira solução que me veio a cabeça, de cara, era muito lenta resultando time complexity de O(n*m), dando timeout em alguns cenários.

Então comecei a pensar em outra possibilidade e cheguei a seguinte solução:

Peguei todas as letras de S e montei a seguinte estrutura:
Supondo o input: "CAGCCTA"

dna: {
   "C": [1,1,1,2,2,2,2],
   "A": [0,1,1,1,1,1,2],
   "G": [0,0,1,1,1,1,1],
   "T": [0,0,0,0,0,1,0]
}

Como podemos ver, montei um array, somando a ocorrência em cada index, dessa forma temos uma linha do tempo e caso queiramos saber qual o menor valor entre dois intervalos, basta fazer:

   for(let l = 0; l < letters.length; l++){
             let letter = letters[l];


             let startSumValue = start > 0 ? dnaMap[letter].sums[start - 1] : 0;
             if(startSumValue != dnaMap[letter].sums[end]){
                result.push(dnaMap[letter].value);
                break;
            }
        }

A solução final ficou assim:

function solution(S, P, Q) {

    var dnaMap = {
        'A': {value:1, last:0, sums:[] },
        'C': {value:2, last:0, sums:[] },
        'G': {value:3, last:0, sums:[] },
        'T': {value:4, last:0, sums:[] },
    }

    var letters = [..."ACGT"];

    var result = [];

    for(let i = 0; i < S.length; i++){
       let dna = S[i];


       letters.forEach((letter)=>{
            var lastValue = dnaMap[letter].last;

            if(S[i] == letter){
                lastValue++;
                dnaMap[letter].last += 1;
            }
            dnaMap[letter].sums.push(lastValue);
       })
    }


    for(let i = 0; i < P.length; i++){

        let start = P[i];
        let end = Q[i];

        if(start == end){
            result.push(dnaMap[S[start]].value);
            continue;
        }

        for(let l = 0; l < letters.length; l++){
             let letter = letters[l];


             let startSumValue = start > 0 ? dnaMap[letter].sums[start - 1] : 0;
             if(startSumValue != dnaMap[letter].sums[end]){
                result.push(dnaMap[letter].value);
                break;
            }
        }


    }

    return result;
}

Blog

Codility GenomicRangeQuery (Resolvido)

Caio Vidal

Join Our Newsletter. No Spam, Only the good stuff.

Related