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

« post anterior | home | post seguinte »

Segunda-feira, 11 de Janeiro de 2010

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.

tags: algoritmia, entrevistas, recrutamento, sapo

publicado por jac às 10:00
link do post | comentar | adicionar aos favoritos |

10 comentários:

De Alberto a 11 de Janeiro de 2010 às 12:13

Evidentemente que a primeira solução tem problemas. Mas as seguintes não. Repa no teu pedido: "Vais receber uma lista de números. Encontra a maior diferença entre quaisquer dois números nessa lista." A parte relevante aqui é o pseudo-código. Quando pedes isto não é suposto estares com problemas de eficiência porque a maior parte das vezes (e não no caso particular que indicas) as soluções em diferentes linguagens levam a soluções diferentes, especialmente se em causa estiver a eficiência.

Também sei que estás a falar de uma entrevista e não de um exame em que sai pergunta, entra solução, sai classificação. Mas só queria chamar à atenção que às vezes uma má solução corresponde a uma má especificação.

responder a comentário | discussão

De jac a 11 de Janeiro de 2010 às 19:03

É verdade. Mas infelizmente, a vida real está cheia de más especificações e invariavelmente temos que ser nós a encontrar as falhas nas ditas :-)

responder a comentário | início da discussão

De mwm a 11 de Janeiro de 2010 às 14:04

Não deixa, no entanto, de ser uma péssima maneira de recrutar alguém: submetendo-o a testes à pressão. Não é o verdadeiro ambiente de trabalho.

responder a comentário | discussão

De jac a 11 de Janeiro de 2010 às 19:00

Uma das coisas que nós fazemos é garantir que o candidato vai mais além do que é necessário.

Mesmo o verdadeiro ambiente de trabalho sendo descontraído e relaxado, é sempre bom sabermos que se um dia as coisas correrem mal (e podem correr) o colaborador vai conseguir dar conta do recado, mesmo sobre pressão.

Nas entrevistas no SAPO testamos não só o conhecimento técnico mas a reacção ao stress e a rapidez de raciocínio, entre outras qualidades. O resultado está na qualidade da equipa que temos: mais de 150 pessoas que vivem para a tecnologia, que têm o conhecimento necessário para desempenhar as suas funções e que sabem trabalhar num ambiente informal e relaxado mas não desesperam nem desistem quando as circunstâncias os apertam.

responder a comentário | início da discussão | discussão

De mwm a 11 de Janeiro de 2010 às 19:50

Fair enough. Mas compreende-se que uma pessoa que não esteja ambientada (ou mesmo stressada) numa entrevista não seja tão eficiente mas uma vez integrada na equipa, em situações mais stressantes, é capaz de acompanhar o ritmo.

responder a comentário | início da discussão

De ui a 11 de Janeiro de 2010 às 23:26

Ui, vejo que "treta" tb parece ser um dos requisitos. :-D

responder a comentário | início da discussão

De Paulo a 11 de Janeiro de 2010 às 20:19

Mau é o que vulgarmente acontece por todos os lados que é meter alguém porque é amigo/filho/primo/... de alguém.

Acho que este método é bastante eficaz para o pretendido.

Só acho é que deviam sempre de informar os candidatos do resultado da candidatura :P

responder a comentário | início da discussão

De Paulo a 11 de Janeiro de 2010 às 14:47

Para melhorar mais um pouco penso que os "or" deviam ser retirados dentro do for para melhorar a performance. É que se tivermos muito elementos estamos a testar esses or's n*2 vezes (uma em cada if)

if (tamanho<2)
{
return null;
}
else
{
min = lista[0];
max = lista[0];

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

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

return max - min;
}

responder a comentário | discussão

De jac a 11 de Janeiro de 2010 às 19:02

Isso mesmo :-)

responder a comentário | início da discussão | discussão

De Paulo Afonso a 29 de Janeiro de 2010 às 07:52

Com mais um else podemos poupar mais algumas validações do segundo if dentro do ciclo a não ser a lista esteja organizada por ordem crescente.

if (tamanho<2)
{
return null;
}
else
{
min = lista[0];
max = lista[0];

for ( i = 1; i < tamanho; i++ )
{
if ( lista[i] < min ) {
min = lista[i];
}
else if ( lista[i] > max ) {
max = lista[i];
}
}

return max - min;
}

responder a comentário | início da discussão

Comentar post

Autores

celso

rcarmo

pesquisar

Janeiro 2012

Dom

Seg

Ter

Qua

Qui