Duas bolinhas de gude e um prédio de 100 andares

https://stackoverflow.com/questions/6547

08-06-2019
|

Pergunta

Uma daquelas perguntas clássicas de entrevistas de programação...

Você recebe duas bolinhas de gude e é informado de que elas quebrarão quando caírem de uma certa altura (e provavelmente não sofrerão nenhum dano se caírem abaixo dessa altura).Você é então levado a um prédio de 100 andares (presumivelmente mais alto do que a altura certa) e solicitado a encontrar o andar mais alto de onde você pode jogar uma bola de gude sem quebrá-la da maneira mais eficiente possível.

Informação extra

Você deve encontrar o piso correto (não um intervalo possível)
As bolinhas de gude têm a garantia de quebrar no mesmo chão
Suponha que você não precise de tempo para trocar de piso - apenas o número de quedas de mármore conta
Suponha que o piso correto esteja distribuído aleatoriamente no edifício

Solução

O interessante aqui é como você pode fazer isso com a menor quantidade de gotas possível.Ir para o 50º andar e derrubar o primeiro seria desastroso se o piso de ruptura fosse o 49º, resultando em ter que fazer 50 quedas.Devemos largar a primeira bola de gude no andar n, onde n é a quantidade máxima de quedas necessárias.Se a bola de gude quebrar no andar n, poderemos ter que fazer n-1 quedas depois disso.Se a bolinha não quebrar subimos para o andar 2n-1 e se quebrar aqui teremos que derrubar a segunda bolinha n-2 vezes na pior das hipóteses.Continuamos assim até o 100º andar e tentamos quebrá-lo em 3n-2, 4n-3....
e n+(n-1)+(n-2)+...1 <=100
n=14 As quedas máximas são necessárias

Outras dicas

Este problema é abordado no Problema 6.5 do Livro "Entrevista decifrando a codificação (5º)", com soluções resumidas da seguinte forma:

Observação:

Independentemente de como eliminamos Marble1, Marble2 deve fazer uma pesquisa linear.Por exemplo, se o marble1 quebrar entre o piso 10 e 15, temos que verificar todos os andares com o marble2

A abordagem:

Uma primeira tentativa: Suponha que deixemos cair uma bolinha de gude do 10º andar, depois do 20º,…

Nas primeiras quebras do Marble no primeiro drop (Piso 10), então temos no máximo 10 drops no total.
Se o primeiro mármore quebrar na última gota (piso 100), temos no máximo 19 gotas no total (piso 1 a 100, depois 91 a 99).
Isso é muito bom, mas tudo o que consideramos é o pior caso.Devemos fazer algum "balanceamento de carga" para tornar esses dois casos mais uniformes.

Meta: Crie um sistema para descartar o Marble1 para que o maior número de quedas necessárias seja consistente, independentemente de o Marble1 quebrar na primeira ou na última queda.

Um sistema perfeitamente balanceado de carga seria aquele em que gotas de marble1 + gotas de marble2 são sempre as mesmas, independentemente de onde o marble1 quebrou.
Para que esse seja o caso, como cada gota de Marble1 dá mais um passo, o Marble2 é permitido um passo a menos.
Portanto, devemos reduzir o número de etapas potencialmente exigidas pelo Marble2 por uma queda a cada vez.Por exemplo, se o Marble1 for lançado no piso 20 e depois o piso 30, o Marble2 é potencialmente necessário para dar 9 etapas.Quando descartarmos o Marble1 novamente, devemos reduzir as etapas potenciais do Marble2 para apenas 8.por exemplo, devemos largar Marble1 no andar 39.
Sabemos, portanto, Marble1 deve começar no piso X, depois subir por andares X-1, depois X-2,…, até chegar a 100.
Resolva para X+(X-1)+(X-2)+…+1 = 100.X(X+1)/2 = 100 -> X = 14

Vamos para o andar 14, depois para o 27, depois para o 39,… Isso leva no máximo 14 passos.

Código e extensão:

Para implementação de código, você pode conferir aqui.
Para que a extensão N mármores, M andares, confira Capítulo 12:O quebra-cabeça de ovos e pisos .

Cada um deles quebra quando cai da mesma altura ou são diferentes?

Se forem iguais, vou até o 50º andar e deixo cair a primeira bolinha.Se não quebrar, vou até o 75º andar e faço o mesmo, enquanto não quebrar continuo subindo 50% do que sobrou.Quando ela quebra, volto para uma mais alta do que onde estava anteriormente (então, se quebrou no 75º andar, volto para o 51º andar) e deixo cair a segunda bola de gude e subo um andar de cada vez até que ela quebre, nesse ponto, conheço o andar mais alto de onde posso cair sem quebrar o mármore.

Provavelmente não é a melhor resposta, estou curioso para ver como os outros respondem.

Solte a primeira bola de gude no andar 10, 20, 30, etc.até quebrar, então volte para o último conhecido bom andar e começar a jogar bolinhas de gude, um andar de cada vez.O pior caso é 99 sendo o Magic Floor e você sempre pode encontrá-lo em 19 drops ou menos.

Pessoalmente, não sou muito fã dessas questões de quebra-cabeças; prefiro exercícios reais de programação em entrevistas.

Dito isto, primeiro dependeria se eu posso dizer se eles estão quebrados ou não no chão onde os estou deixando cair.Presumo que posso.

Eu subia até o segundo andar, deixava cair a primeira bolinha.Se quebrasse, eu tentaria o primeiro andar.Se isso quebrasse, eu saberia que não era chão.

Se o primeiro não quebrasse, eu iria para o 4º andar e cairia de lá.Se quebrasse, eu voltaria para baixo e pegaria a outra bolinha, depois cairia no 3º andar, quebrando ou não, saberia qual é o limite.

Se nenhum deles quebrasse, eu iria buscar os dois e faria o mesmo processo, desta vez começando no 6º andar.

Dessa forma, posso pular todos os outros andares até conseguir uma bola de gude que quebre.

Isso seria otimizado se a bola de gude quebrar cedo ...Suponho que provavelmente haja uma quantidade ideal de andares que eu poderia pular para aproveitar ao máximo cada salto...mas se um deles quebrar, eu teria que verificar cada andar individualmente, do primeiro andar até o último andar conhecido...o que, claro, seria um problema se eu pulasse muitos andares (desculpe, não vou descobrir a solução ideal agora).

Idealmente, eu gostaria de um saco inteiro de bolinhas de gude, então poderia usar um algoritmo de busca binária e dividir o número de andares pela metade a cada queda...mas então, essa não era a questão, era?

Eu acho que o real A questão é quão precisa você deseja a resposta.Porque a sua eficiência vai depender muito disso.

Vou concordar com Justin se você quiser 100% de precisão no bolinha de mármores, depois que o primeiro mármore quebrar, você terá que subir 1 andar de cada vez do último piso "bom" conhecido até descobrir qual andar é o vencedor." Talvez até jogue algumas estatísticas e comece no 25º andar, em vez do 50º andar, para que seu pior cenário fosse de 24 em vez de 49.

Se sua resposta puder ser mais ou menos um ou dois andares, poderá haver algumas otimizações.

Em segundo lugar, subir/descer escadas conta contra a sua eficiência?Nesse caso, sempre deixe cair as duas bolinhas de gude e pegue-as em cada viagem para cima/para baixo.

Solte a primeira bola de gude do 3º andar.Se quebrar, você sabe que é o andar 1 ou 2, então deixe cair a outra bola de gude do andar 2.Se não quebrar, você descobrirá que o andar 2 é o mais alto.Se quebrar, você descobriu que o andar 1 é o mais alto.2 gotas.

Se cair do 3º andar não quebrar o mármore, desça do 6º andar.Se quebrar, você sabe que o andar 4 ou 5 é o mais alto.Solte a segunda bola de gude do andar 5.Se não quebrar, você descobriu que 5 é o mais alto.Se isso acontecer, o piso 4 é o mais alto.4 gotas.

Continuar.

3 andares – máximo de 2 quedas

6 andares – máximo de 4 quedas

9 andares – máximo de 6 quedas

12 andares – máximo de 8 quedas

etc.

3x andares - máximo de 2x quedas

Portanto, para um prédio de 99 andares, você teria no máximo 66 quedas.E isso é o máximo.Você provavelmente teria menos gotas do que isso.Ah, e 66 é o máximo para um prédio de 100 andares também.Você só precisaria de 66 quedas se o piso de intervalo fosse 98 ou 97.Se o intervalo fosse 100, você usaria 34 gotas.

Mesmo que você tenha dito que não importava, isso provavelmente exigiria o mínimo de caminhada e você não precisa saber a altura do prédio.

Parte do problema é como você define eficiência.É mais "eficiente" sempre ter uma solução em menos de x gotas, ou é mais eficiente ter uma boa chance de ter uma solução em y gotas, onde y < x com a ressalva de que você poderia ter mais de x gotas ?

Isso pode ser feito melhor com apenas 7 bolinhas de gude.

Então, seguindo a resposta votada, digamos que a bola de gude quebre pelo menos no 49º andar.

50º andar -> intervalos (a resposta está entre 1 a 50 inclusive)
25º andar -> não quebra (26 a 50)
37º andar -> não quebra (38 a 50)
43º andar -> não quebra (44 a 50)
46º andar -> não quebra (47 a 50)
48º andar -> não quebra (49 ou 50)
49º andar -> quebras (49º, esta etapa é realmente necessária porque pode ter sido o piso mínimo para o mármore quebrar é no 50º)

Isso pode ser imaginado como fazer uma pesquisa binária em um conjunto ordenado para algum k, onde obtemos metade do espaço de solução a cada tentativa.Para 100 andares, precisamos de log2 100 = 6,644 (7 tentativas).Com 7 bolinhas de gude podemos ter certeza de qual é o piso mínimo que o mármore vai quebrar até 128 andares.

A primeira coisa que eu faria é usar o algoritmo extremamente simples que começa no andar 1 e deixa cair a bola de gude um andar de cada vez até atingir 100 ou a bola de gude quebrar.

Então eu perguntaria por que deveria gastar tempo otimizando isso até que alguém possa mostrar que isso será um problema.Muitas vezes as pessoas ficam presas em encontrar o algoritmo complicado e perfeito, quando um algoritmo muito mais simples resolverá o problema.Em outras palavras, não otimize as coisas até que seja necessário.

Esta pode ser uma pergunta capciosa para ver se você é uma daquelas pessoas que consegue transformar um pequeno morro em uma montanha.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow