Quando você tem que jogar ovos do telhado: problema diário de codificação

Problema diário de codificação 24

Bem-vindo de volta com outro problema para resolver! Hoje, estamos lidando com ovos caindo de telhados com esse problema muito legal, que envolverá duas soluções possíveis: uma bem ingênua e outra mais inteligente. Este último também nos dará a oportunidade de falar sobre um algoritmo bastante famoso.

Como sempre, o problema de hoje é fornecido pela maravilhosa newsletter Problema diário de codificação , que você pode assinar gratuitamente para receber seu desafio diário de codificação também. Confira e tente resolver seus problemas também!

Chega de conversa então; vamos ver o problema!

O problema

Esse problema foi questionado pelo Goldman Sachs em uma entrevista de emprego. Vamos ver o problema.

Você recebe N ovos idênticos e acesso a um prédio com k andares. Sua tarefa é encontrar o andar mais baixo que fará com que um ovo se quebre, se cair desse chão. Depois que um ovo quebra, ele não pode ser largado novamente. Se um ovo quebrar ao cair do xth andar, você pode presumir que ele também quebrará quando cair de qualquer andar maior que x .

Escreva um algoritmo que encontre o número mínimo de tentativas que serão necessárias, na pior das hipóteses, para identificar esse piso.

Por exemplo, se N = 1 e k = 5 , precisaremos tentar largar o ovo em todos os andares, começando pelo primeiro, até chegar ao quinto andar, então nossa solução será 5 .

Então, recebemos alguns ovos para jogar de diferentes andares de um prédio. Ficamos tristes porque de um determinado andar (que chamaremos de targetFloor ), os ovos jogados fora não quebram ao cair no chão.

Desse andar até todos os andares abaixo dele, os ovos não quebrarão quando jogados pela janela. O que nos pedem é encontrar um método eficiente para encontrar o targetFloor .

Como previsto, veremos dois métodos para resolver isso: um muito simples, que forçará a solução, mas não será eficiente. O segundo será muito mais eficiente e tentará resolver o problema quebrando o menor número de etapas.

Também nos dará a oportunidade de falar sobre um algoritmo realmente famoso e importante; um daqueles que você precisa saber para fazer… basicamente qualquer coisa!

Configurando o Ambiente

Para começar, precisamos configurar um pouco do ambiente, nomeadamente o edifício e o targetFloor . Para criar o edifício, basta criar um array contendo os números dos andares, desde o térreo até o andar nᵗʰ. Então, geramos um número aleatório que será nosso targetFloor .

Escreveremos esse problema em Go mais uma vez: simples o suficiente para ser legível, mas complexo o suficiente para entender a mecânica interna.

Primeiro criamos o array que servirá de edifício: podemos dar-lhe o tamanho que quisermos, quanto maior for o tamanho, mais alto será o edifício. Depois disso, criamos uma instância do targetFlor usando o módulo math/rand construído em Go.

Basicamente, criamos um novo número inteiro aleatório entre 0 e a altura do edifício (… o comprimento do array :D) usando como fonte a hora atual.

A solução da força bruta

Claro, a solução mais simples possível seria jogar fora cada ovo de cada andar, para ver em qual andar os ovos começam a quebrar. Como temos uma variável contendo essa informação, poderíamos simplesmente fazer um loop for para resolver o problema:

Embora esta seja a solução mais simples, infelizmente é altamente ineficiente. Imagine se o andar certo fosse o de cima: é preciso quebrar 100.000 ovos para resolver o problema: seria uma omelete enorme, mas um grande desperdício!

De modo geral, esta solução tem uma complexidade de tempo de O(n) porque a complexidade da solução cresce linearmente com a complexidade do problema de entrada. Esta não é a solução mais eficiente que poderíamos imaginar.

Uma solução eficiente

Vamos pensar então em uma solução eficiente. Em vez de andar andar por andar quebrando cada ovo em cada andar, poderíamos dar um palpite e, com base no resultado desse palpite, ajustar o próximo palpite.

Aqui está um exemplo: suponha que temos um prédio com 10 andares, e o targetFloor é o andar 7 (não sabemos disso, é claro). Poderíamos fazer as seguintes suposições:

Basicamente, achamos que targetFloor é o andar intermediário do edifício. Jogamos o ovo a partir daí e os resultados possíveis são dois:

• o ovo quebra, o que significa que estamos muito chapados. Podemos descartar o piso mais alto que este, inclusive, e continuar com nossas suposições.

• O ovo não quebra, o que significa que estamos muito baixos ou no chão correto. Descartamos todos os andares inferiores a este, inclusive, e

Diante disso, fazemos agora outra suposição sobre o andar intermediário ou o edifício “restante” e aplicamos a mesma estratégia vista acima. Podemos continuar com esta abordagem até ficarmos com um andar.

Se você reconhece essa abordagem, está perfeitamente certo: trata-se simplesmente de uma pesquisa binária aplicada a um problema do “mundo real”. A pesquisa binária é um algoritmo simples e organizado de dividir e conquistar , o que significa que, a cada etapa, o tamanho do problema é reduzido pela metade até encontrarmos a solução.

Isso significa que este algoritmo, comparado ao anterior, é bem mais rápido. Vamos ver o código!

Vamos dar uma olhada mais profunda. A função de pesquisa binária recebe 4 argumentos:

• overArray , um array de inteiros, que é o edifício sobre o qual estamos fazendo o loop;

• bottom , o índice inferior do edifício;

• top , o índice do último andar do edifício;

• breakFloor , a variável que contém targetFloor para verificar se podemos encontrá-lo no prédio.

Depois disso, fazemos um loop sobre o edifício enquanto bottom é inferior a top : na pesquisa binária, quando os dois argumentos posicionais se entrelaçam e trocam, significa que o elemento pesquisado não foi encontrado.

Portanto, se o algoritmo terminar nesta situação, o loop termina e retornamos -1 , significando que o elemento que procuramos não estava presente no array. Se ainda estivermos procurando o elemento, aplicamos o que mostra a imagem acima.

Calculamos o elemento middlePoint como o piso entre bottom e top e verificamos se middlePoint == breakFloor . Se for, retornamos o middlePoint como resultado.

Caso contrário, ajustamos bottom ou top de acordo: se middlePoint for maior que breakFloor , significa que estamos muito altos no edifício, então reduzimos nossa previsão definindo o piso top possível como middlePoint — 1 .

Se middlePoint for menor que breakFloor , ajustamos nosso bottom definindo como middlePoint+1 .

Agora para verificar tudo, na função main , geramos o ambiente como antes, e criamos uma nova variável chamada bsFloor que conterá nosso resultado.

Para confirmar que nosso algoritmo nos trouxe ao resultado correto, imprimimos bsFloor e targetFloor , que foi gerado anteriormente aleatoriamente.

Complexidade de tempo

Como antecipamos antes, este algoritmo é muito mais rápido que o linear. Como dividimos o edifício pela metade em cada etapa, podemos encontrar o andar correto em log₂(n) onde n é igual a len(building) .

Isso significa que a complexidade de tempo deste algoritmo é O(log(n)) . Para lhe dar uma comparação entre a solução linear e esta última, se o edifício tiver 100 andares, o algoritmo linear leva no pior caso 100 iterações, enquanto o algoritmo de pesquisa binária leva log₂100 = 6,64, ou seja, 7 iterações.

Além disso, este último é cada vez mais eficiente que o linear porque quanto mais o edifício cresce, mais eficiente é a busca binária. Para um edifício com 1.000.000.000 andares, o linear dá 1.000.000.000 passos, enquanto o binário dá log₂1.000.000.000 = 29,9, ou seja, 30 passos. Uma grande melhoria!

Conclusão

É isso! Espero que você tenha gostado do artigo tanto quanto eu me diverti tentando resolver o desafio! Se sim, por favor, deixe uma ou duas palmas, seria um grande apoio! Se você gosta desse tipo de artigo e quer ver mais, acompanhe a página pois eu libero esse tipo de conteúdo sempre que posso.

Por fim, se você achou este artigo interessante ou útil e gostaria de contribuir oferecendo um café, fique à vontade para fazê-lo no meu Ko-fi página!

E, como sempre, obrigado pela leitura!

Nicola

Também publicado aqui