28 setembro 2007

É lógico!

Ok. Todo mundo está perguntando que questão complicada foi aquela da minha entrevista. Vou tentar reproduzi-la aqui. Trata-se de uma questão que envolve mais lógica e matemática do que propriamente programação. Em todo caso, ela foi proposta na segunda entrevista, pelo CTO da empresa. A princípio ele pediu para eu desenhar algum projeto que tivesse desenvolvido. Depois ele me veio com essa:

Considere uma empresa que produz peças: parafusos e porcas. Os parafusos pesam 11g e as porcas, 10g. Para atender a uma encomenda de porcas, foi separado um certo número de caixas, mas, por engano, uma das caixas continha parafusos, só que agora todas as caixas já estão fechadas. É preciso descobrir qual é a caixa errada!
Suponha-se um sistema automático que pode coletar uma determinada quantidade de peças de uma determinada caixa e guardar numa bandeja e pode também levar o conteúdo da bandeja para uma balança. A primeira ação é executada por uma função void pegar(int numPecas, int caixa); e a segunda por uma função int pesar(); embora isso seja meramente ilustrativo, porque não precisava escrever o programa, mas apenas demonstrar a minha maneira de raciocinar (se bem que essas funções acabaram me dando uma dica importante no final).
O problema é montar um algoritmo que execute essas operações (um programa que chame essas funções) para determinar qual é a caixa que contém parafusos em vez de porcas.
A princípio, ele disse que era apenas uma maneira de observar a minha maneira de pensar e resolver problemas. Por isso eu comecei com a solução mais simples: pegar uma peça da primeira caixa e pesar, depois uma da segunda e assim sucessivamente até encontrar um parafuso. Depois ele pediu para considerar a balança como um recurso caro que precisa ser otimizado e pediu para elaborar um algoritmo que executasse menos pesagens. Eu propus uma solução com busca binária (ele me pediu até a função matemática que descreve a eficiência da busca binária). Por fim, ele disse que a balança era um recurso muito, muito caro e perguntou se eu poderia fazer um algoritmo com o mínimo de pesagens possível. Ele até saiu da sala para deixar eu pensando. Se bem que a resposta me veio logo que ele saiu. Na verdade esse é um problema clássico de lógica que aparece em muitos livrinhos de passatempo. Apesar disso, depois que eu dei a resposta, ele disse que mais ou menos 90% das pessoas não conseguem chegar a essa solução.
Alguém mais sabe a resposta?

9 comentários:

:= disse...

Se eu fosse depender de uma entrevista dessa pra arranjar emprego ficaria desempregada o resto da vida!

Anônimo disse...

Eu nao faco ideia...
Envolve matematica??? Entao esquece.. Como a Jeanne disse, se eu dependesse de matematica pra sobreviver passaria fome!!! hehehehe..

Bjs!!!

;)

Ravi disse...

Eu acho que eu descobri a resposta, se funcao pegar(int pecas, int caixa) puder ser chamada mais de uma vez antes de você pesar, então o esquema seria o seguinte:

1 item da caixa 1
2 itens da caixa 2
... sucessivamente até a caixa número 9

E então você pesa isso, tudo junto. Divida por dez. Pegue o resto. Se der zero, só tem porca. Senão, o resto será o número da caixa que está com o parafuso.

Por exemplo:
1 x 10 = 10
2 x 10 = 20
3 x 10 = 30
...
6 x 11 = 66
7 x 10 = 70
8 x 10 = 80
9 x 10 = 90
Soma: 456, resto da divisão por 10, seis, que é a caixa que contém os itens errados.

Anônimo disse...

Oi, Pedro e Jeanne!

Legal já ter arrumado um emprego. Parabéns!!!
Pra solução, acho que dividiria as caixas por número primos, começando por 2 (desde que divisível), e pesaria cada grupo. O grupo com maior peso é o que está com a caixa errada. Continuaria, até se chegar num número primo. Aí, não tem jeito. Tem que pesar um por um mesmo.
Acertei? Será que consigo um emprego assim também?
Ainda unemployeed,

Marcelo e Julia

Pedro disse...

O Ravi Wallau acertou a resposta. Pelo menos foi a que eu usei, embora, num caso real, isso fosse causar a maior confusão na encomenda.
Tenho a impressão de já ter visto um problema parecido alguma vez, mas, na hora da entrevista, que nem deveria ser técnica, eu demorei um pouco para lembrar dela.

Anônimo disse...

Olha aí!

Por isso, que não arrumei emprego ainda!!! rsrsrsr

Abraços,

Marcelo

Ravi disse...

Opa Pedro!!!
Depois que eu li seu post eu fiquei pensando um tempão neste problema, aí eu vi que o único jeito era poder colocar mais de um item na balança.
Eu gosto destas questões de lógica... As três últimas entrevistas de emprego que eu fiz foram todas na conversa, nas duas primeiras eu fui empregado e agora estou esperando a resposta.
A propósito, eu também sou de TI, mas estou em Calgary. Com o que você trabalha (tecnologias)?

Paula Regina disse...

HEINNNNN???? Excuse-me??? Socorro! Ainda bem que eu sou uma "operária da palavra e da escrita" e só precisei delas para conseguir o meu emprego aqui:) De qualquer maneira adorei o post!
bjs e sucesso!

:: ultranol :: disse...

Peraí, se as caixas estão fechadas e não dá pra saber qual é o conteúdo, como que tem uma máquina que pega as peças de dentro de uma caixa? Se a máquina abre a caixa pra pegar a peça, já dá pra ver se é parafuso ou porca... não é?
Não consegui sair desse meu raciocínio... hehehe