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.
De Paulo a 3 de Novembro de 2009 às 12:05
haha
Agora será mais fácil responder a esta pergunta durante uma entrevista.
Agora será mais fácil responder a esta pergunta durante uma entrevista.
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.
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;
@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 stv a 3 de Novembro de 2009 às 17:44
sort($array_nums);
$diferenca = first($array_nums) - last($array_nums);
echo "Moooo!";
$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.
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
$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!
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
$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;
}
}
}
$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
2º - a maneira que eu faria sem me chatear mt era ordenar esse array e apenas imprimir a difenrença [0]-[.length]
ty
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);
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...
Autores
pesquisar
Janeiro 2012
Dom
Seg
Ter
Qua
Qui
Sex
Sab
1
2
3
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
posts recentes
arquivos
tags
- 2009
- acessibilidade
- administração de sistemas
- algoritmia
- android
- aniversário
- anne van kesteren
- api
- apresentações
- bases de dados
- best
- blogs
- bolsas
- brian leroux
- campus
- cartão de cidadão
- codebits
- codebits 2009
- compactação de urls
- concurso
- conferências
- couchdb
- css
- css 3
- damian conway
- data centers
- design
- dovecot
- entrevistas
- escalabilidade
- eventos
- eye tracking
- formação
- fotos
- fruta
- galp
- geek room
- gis
- hijax
- homepage
- html
- html 5
- imagens
- integração
- invited speakers
- iphone
- ipv4
- ipv6
- isel
- ist
- jan lehnardt
- janet read
- java
- javascript
- larry wall
- libsapo.js
- linux
- lxmls
- machine learning
- mapas
- master classes
- memcached
- meo
- microsoft
- monitorização
- mysql
- nokia
- open search
- openid
- perl
- pesquisa
- php
- pond
- prémios
- profiling
- prototype
- publicidade digital
- puny url
- python
- qualidade
- rasmus lerdorf
- realizar apresentações
- recrutamento
- rss
- sapo
- sapo developer network
- sapo labs
- sapo mail
- sapo sessions
- segurança
- storage
- sxsw
- tmn
- trainees
- usabilidade
- verbatim
- web services
- widgets
- yapc
últ. comentários
Paulo Nobre
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...
subscrever feeds
