Terça-feira, 3 de Novembro de 2009

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.



publicado por jac às 08:55
link do post | comentar | adicionar aos favoritos |

16 comentários:
De Paulo a 3 de Novembro de 2009 às 12:05
haha

Agora será mais fácil responder a esta pergunta durante uma entrevista.


De jac a 3 de Novembro de 2009 às 12:16
Motivo pelo qual deixaremos de a fazer :-)


De Marco a 3 de Novembro de 2009 às 12:23
Vou dar já uma resposta,

A resposta para os 5 minutos seria(isto em pseudo codigo):
Dado o problema ser só 5 nrs, eu procurava o maior e o menor nr e fazia a diferença.


Como vais dar mais uns dias, bora lá fazer uma coisas mais optimizada, para listas com mais de 5 nr e companhia.


De Ricardo Dias Marques a 3 de Novembro de 2009 às 13:45

OK. Tenho uma dúvida de interpretação do enunciado.

Quando se diz:

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

Significa isto que:

A) "Desenvolve um algoritmo para encontrar os dois números desta lista que têm a maior diferença entre si"? (parece-me que é isto que se pretende)

-OU-

B) "Desenvolve um algoritmo para dado um (qualquer) número da lista (escolhido aleatoriamente ou por "input" de utilizador) encontrar o número que tem maior diferença relativamente a ele"? (Neste caso, dependendo da lista de números, é possível que haja 2 números à mesma "maior distância" do 1º - um menor e outro maior).


De jac a 3 de Novembro de 2009 às 14:39
A primeira, mas atenção que o objectivo não é dizer quais são os números, mas sim qual a diferença entre estes.


De mwm a 3 de Novembro de 2009 às 15:42
Tive a mesma dúvida que o Ricardo Dias Marques. Não está no melhor português, digamos :)

@jac : "... atenção que o objectivo não é dizer quais são os números, mas sim qual a diferença entre estes."

Qual a dificuldade de fazer a-b depois de encontrados o máximo e o mínimo?

Eu faria algo do género:

int v[];
int s = size_vec(v);
int i, min = v[i], max = v[i], solucao;
for (i = 0; i < s; i++) {
if (v[i] >= max)
max = v[i];
if (v[i] <= min)
min = v[i];
}
solucao = max -min;


De mwm a 3 de Novembro de 2009 às 15:46
min=v[0] e max=v[0] e não v[i] :)


De stv a 3 de Novembro de 2009 às 17:44
sort($array_nums);
$diferenca = first($array_nums) - last($array_nums);
echo "Moooo!";


De Paulo a 3 de Novembro de 2009 às 22:00
Esta têm menos linhas mas é mais pesada, ordenar o array é mais pesado que calcular o mínimo e o máximo.

Eu fui um dos questionados e na altura fiz instantaneamente o que ocorreu sem pensar muito e saiu uma burrice como fazer a diferença entre todos os números. Embora funcione é muito pesado (mesmo assim menos pesado que ordenar a lista toda :D)

É um bocado diferente conseguir responder sentado na cadeira em frente ao computador ou responder numa entrevista, especialmente se tivermos aquele sistema nervoso a trabalhar.



De stv a 4 de Novembro de 2009 às 11:45
meus 2 minutos de hoje.
$v[1])
$v[1] = $w;
return $v;
}
list($min, $maior) = array_reduce($nums, "reduce", array($nums[0],$nums[0]));
echo $min;
echo $maior;
?>
:P


De stv a 4 de Novembro de 2009 às 15:02
Viva pessoal, esta faltando pedaços:

function reduce($v, $w){
if($w < $v[0])
$v[0] = $w;
if($w > $v[1])
$v[1] = $w;
return $v;
}
list($min, $max) = array_reduce($nums, "reduce", array($nums[0],$nums[0]));
$diff = $min-$max;


Até mais!


De mariorui a 9 de Novembro de 2009 às 14:50
Aqui vai a minha contribuição :)

$a = array(1, 2, 3, 4, 5, 6, 7, 51, 9, 10, 11, 12, 13, 14, 15);

$maxDif = 0;
$mTmp = 0;
for ($i=0; $i
[Error: Irreparable invalid markup ('<count($a);>') in entry. Owner must fix manually. Raw contents below.]

Aqui vai a minha contribuição :)

$a = array(1, 2, 3, 4, 5, 6, 7, 51, 9, 10, 11, 12, 13, 14, 15);

$maxDif = 0;
$mTmp = 0;
for ($i=0; $i<count($a); $i++){
for ($j=0; $j<count($a); $j++){
$mTemp = $a[$j] - $a[$i];
if ($mTemp>$maxDif){
$maxDif = $mTemp;
}
}
}


De Ricardo a 9 de Novembro de 2009 às 22:43
1º - entram nº negativos para esse input?
2º - a maneira que eu faria sem me chatear mt era ordenar esse array e apenas imprimir a difenrença [0]-[.length]
ty


De jac a 10 de Novembro de 2009 às 09:11
Podem entrar números negativos no input, sim.


De Luís Sousa a 10 de Novembro de 2009 às 14:06
Se permitirem utilizar funcionalidades de uma linguagem como o PHP (penso que não já que se trata de um algoritmo),

echo "A maior diferença é de ". (max($array) - min($array));

Caso contrário (mas mt mais lento),

for ($i = 0,$max = 0,$min=0,$count = sizeof($array); $i < $count; $i++){
if ($array[$i] > $max) {
$max = $array[$i];
}
elseif ($array[$i] < $min){
$min = $array[$i];
}
}
echo "A maior diferença é de ". ($max - $min);


De ag a 27 de Novembro de 2009 às 14:21
engraçado é que ninguém está a escrever em pseudo-código...


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