Saltar para: Posts [1], Pesquisa [2]

SAPO developers blog

SAPO developers blog

Encontrar a maior diferença entre dois números numa lista

Janeiro 11, 2010

jac

Recentemente colocámos neste blog um post com um dos problemas que usamos em muitas das entrevistas de 2009 no SAPO.

O problema consistia em desenhar (escrever) um algoritmo para resolver o seguinte problema, em pseudo-código:

    "Vais receber uma lista de números. Encontra a maior diferença entre quaisquer dois números nessa lista."

Hoje vamos analisar algumas das soluções com que nos deparámos nas entrevistas.

Estranhamente, uma solução que é apresentada com frequência é a seguinte:

    maior_diferenca = 0;

    for ( i = 1 ; i < length lista ; i++ ) {
        if ( lista[i] - lista[i-1] > maior_diferenca ) {
            maior_diferenca = lista[i] - lista[i-1];
        }
    }

    return maior_diferenca;

Esta é uma solução que não apresenta o resultado correcto e que demonstra uma série de problemas no raciocínio do candidato (problemas esses que não iremos abordar aqui, mas é de facto uma situação comum).

Eis a solução mais básica que poderia ser apresentada (seguindo-se a lista de problemas que a mesma apresenta):

    maior_diferenca = 0;

    for ( i = 0 ; i < length lista ; i++ ) {
        for ( j = 0 ; j < length lista ; j++ ) {
            if ( abs( lista[i] - lista[j] > maior_diferenca ) ) {
                maior_diferenca = abs( lista[i] - lista[j] );
            }
        }
    }

    return maior_diferenca;

Problemas de eficiência:

 

  • Para cada dois números na lista, a diferença é calculada duas vezes
  • Em cada um dos ciclos, o resultado de "length lista" é calculado n vezes


Erros e corner-cases:

  • O valor 0 é retornado caso a lista seja vazia ou tenha apenas um elemento.


Vejamos agora a mesma solução já com alguns destes problemas resolvidos:

    maior_diferenca = 0;

    tamanho = length lista;

    for ( i = 0 ; i < tamanho ; i++ ) {
        for ( j = i+1 ; j < tamanho ; j++ ) {
            diferenca = abs( lista[i] - lista[j] );
            if ( diferenca_actual > maior_diferenca ) ) {
                maior_diferenca = diferenca_actual;
            }
        }
    }

    return maior_diferenca;

Apesar de esta solução ainda não estar a prever os casos da lista vazia ou da lista com um único elemento, esta já é uma solução mais eficiente que a anterior.

Ainda assim, um bom candidato consegue, desde o início, compreender que não necessita realizar tantas operações, já que lhe basta encontrar o maior e o menor elemento da lista e calcular a diferença entre dois.

Infelizmente, isto faz com que alguns candidatos apresentem uma solução semelhante à seguinte:

    lista = sort  lista;
    max   = last  lista;
    min   = first lista;
    return max - min;

Apesar da solução estar correcta, não é de todo eficaz, dada a complexidade de um sort numa lista com, por exemplo, 20,000 valores.

Eis uma outra solução seguindo esta ideia, ainda com alguns problemas:

    min = 0;
    max = 0;

    for ( i = 0; i < tamanho; i++ ) {
        if ( lista[i] < min ) {
            min = lista[i];
        }

        if ( lista[i] > max ) {
            max = lista[i];
        }
    }

    return max - min;

Esta é uma solução que não funciona, uma vez que basta que todos os números sejam positivos ou negativos para retornar o valor errado.

Uma melhor solução seria algo no seguinte sentido:

    min = null;
    max = null;

    for ( i = 0; i < tamanho; i++ ) {
        if ( min == null or lista[i] < min ) {
            min = lista[i];
        }

        if ( max == null or lista[i] > max ) {
            max = lista[i];
        }
    }

    if ( min != null and max != null ) {
        return max - min;
    }
    else {
        # ...
    }

Entre todas estas versões, há ainda mais uma série de variantes que outros candidatos apresentam.

Há também questões específicas de cada linguagem que podem fazer com que pequenas partes devam ser alteradas por uma questão de eficiência.

Ao ser confrontado com este problema, o candidato ideal:

 

  • sabe que a lista pode ser vazia ou ter apenas um elemento
  • sabe que a lista pode ser enorme (e não tenta fazer um sort)
  • sabe que a lista recebida pode ter elementos que não sejam números
  • percebe quase imediatamente que basta encontrar o máximo e o mínimo da lista
  • consegue sugerir uma ou mais soluções para quando não é possível encontrar uma diferença
  • resolve o problema rápida e eficazmente, e sabe explicar porque fez o que fez

Convém ainda deixar claro que este é apenas um problema que fez parte de um grande conjunto de desafios colocados aos candidatos e que não é apenas a resolução de um simples problema que dita o recrutamento ou não da pessoa.

Algoritmia e entrevistas

Novembro 03, 2009

jac

A título da SAPO Session desta semana, em que abordaremos o tema do recrutamento, divulgamos hoje um dos problemas que foi usado em muitas das entrevistas técnicas que realizamos este ano.

 

O objectivo é que o candidato escreva, em papel, um algoritmo para soluccionar o seguinte problema:

 

"Vais receber uma lista de números. Encontra a maior diferença entre quaisquer dois números nessa lista."

 

É suposto o algoritmo ser escrito em pseudo-código. Não é de todo necessário que o mesmo compile, mas é necessário que se consiga ler e perceber.

 

Este é um problema com muitas nuances que serão explicadas num outro post a ser publicado muito em breve, logo depois de darmos uns dias para que todos possam preparar a sua solução.

 

De notar que é esperado que o problema seja resolvido em menos de cinco minutos, e não no decorrer de vários dias de estudo e optimização.

 

Fica a sugestão aos leitores: resolva o problema, em papel. Aquando da publicação da solução, compare a sua com a esperada.

Mais sobre mim

Subscrever por e-mail

A subscrição é anónima e gera, no máximo, um e-mail por dia.

Arquivo

  1. 2012
  2. J
  3. F
  4. M
  5. A
  6. M
  7. J
  8. J
  9. A
  10. S
  11. O
  12. N
  13. D
  1. 2011
  2. J
  3. F
  4. M
  5. A
  6. M
  7. J
  8. J
  9. A
  10. S
  11. O
  12. N
  13. D
  1. 2010
  2. J
  3. F
  4. M
  5. A
  6. M
  7. J
  8. J
  9. A
  10. S
  11. O
  12. N
  13. D
  1. 2009
  2. J
  3. F
  4. M
  5. A
  6. M
  7. J
  8. J
  9. A
  10. S
  11. O
  12. N
  13. D