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:

 


Erros e corner-cases:


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:

 

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.



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

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.


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 :-)


Comentar:
De
  (moderado)
Nome

Url

Email

Guardar Dados?

Este Blog tem comentários moderados

(moderado)
Ainda não tem um Blog no SAPO? Crie já um. É grátis.

Comentário

Máximo de 4300 caracteres




O dono deste Blog optou por gravar os IPs de quem comenta os seus posts.

Autores
pesquisar
 
Janeiro 2012
Dom
Seg
Ter
Qua
Qui
Sex
Sab

1
2
3
4
5
6
7

8
9
10
11
12
13
14

15
16
17
18
19
20
21

22
23
24
25
26
27
28

29
30
31



follow saposessions at http://twitter.com
posts recentes

Integração do Blog de Dev...

Vídeos da LXMLS

Evento HTML5 PT - 3 de No...

Prémios SAPO 2011

Extensão de prazo de subm...

Candidaturas SAPO Labs

Portuguese Perl Workshop

16 anos

Fun with Dead Languages -...

CPA 2011

arquivos

Janeiro 2012

Dezembro 2011

Outubro 2011

Setembro 2011

Agosto 2011

Julho 2011

Junho 2011

Maio 2011

Abril 2011

Março 2011

Janeiro 2011

Outubro 2010

Setembro 2010

Agosto 2010

Julho 2010

Junho 2010

Maio 2010

Abril 2010

Março 2010

Fevereiro 2010

Janeiro 2010

Dezembro 2009

Novembro 2009

Outubro 2009

Setembro 2009

Agosto 2009

Julho 2009

Junho 2009

Maio 2009

Abril 2009

Março 2009

Fevereiro 2009

tags

todas as tags

últ. comentários
Boas, Apesar deste post já ser um pouco antigo gos...
Por sinal já foi desenvolvido e encontra-se neste ...
A informação que faltava está agora aqui: http://d...
A informação já está aqui: http://developers.blogs...
Boas,Onde é que isto vai ser? Há algum critério pa...
blogs SAPO
subscrever feeds