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 | 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.


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


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.


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.


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.


De ui a 11 de Janeiro de 2010 às 23:26
Ui, vejo que "treta" tb parece ser um dos requisitos. :-D


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


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;
}


De jac a 11 de Janeiro de 2010 às 19:02
Isso mesmo :-)


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;
}


Comentar post

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