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  , que você pode assinar gratuitamente para receber seu desafio diário de codificação também. Confira e tente resolver seus problemas também!   Problema diário de codificação  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.      ovos idênticos e acesso a um prédio com   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   andar, você pode presumir que ele também quebrará quando cair de qualquer andar maior que   . Você recebe N k xth 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.      e   , precisaremos tentar largar o ovo em todos os andares, começando pelo primeiro, até chegar ao quinto andar, então nossa solução será   . Por exemplo, se N = 1 k = 5 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   ), os ovos jogados fora não quebram ao cair no chão. targetFloor  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   . 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 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.   https://gist.github.com/NicolaM94/85ae34f01e7de8cd00264276b385e137?embedable=true#file-main-go  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   usando o módulo   construído em Go. targetFlor math/rand  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:   https://gist.github.com/NicolaM94/dd49b3b44a8938c40d0539512fd613cb?embedable=true#file-main-go  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   é o andar 7 (não sabemos disso, é claro). Poderíamos fazer as seguintes suposições:  targetFloor  Basicamente, achamos que   é o andar intermediário do edifício. Jogamos o ovo a partir daí e os resultados possíveis são dois: targetFloor  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   aplicada a um problema do “mundo real”. A pesquisa binária é um algoritmo simples e organizado   , o que significa que, a cada etapa, o tamanho do problema é reduzido pela metade até encontrarmos a solução. pesquisa binária de dividir e conquistar  Isso significa que este algoritmo, comparado ao anterior, é bem mais rápido. Vamos ver o código!   https://gist.github.com/NicolaM94/79d625ecef07cb26a7a8d9bcdb6143fd?embedable=true#file-main-go  Vamos dar uma olhada mais profunda. A função de pesquisa binária recebe 4 argumentos:    , um array de inteiros, que é o edifício sobre o qual estamos fazendo o loop; overArray    , o índice inferior do edifício; bottom    , o índice do último andar do edifício; top    , a variável que contém   para verificar se podemos encontrá-lo no prédio. breakFloor targetFloor  Depois disso, fazemos um loop sobre o edifício enquanto   é inferior a   : na pesquisa binária, quando os dois argumentos posicionais se entrelaçam e trocam, significa que o elemento pesquisado não foi encontrado. bottom top  Portanto, se o algoritmo terminar nesta situação, o loop termina e retornamos   , 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. -1  Calculamos o elemento   como o piso entre   e   e verificamos se   . Se for, retornamos o   como resultado. middlePoint bottom top middlePoint == breakFloor middlePoint  Caso contrário, ajustamos   ou   de acordo: se   for maior que   , significa que estamos muito altos no edifício, então reduzimos nossa previsão definindo o piso   possível como   . bottom top middlePoint breakFloor top middlePoint — 1  Se   for menor que   , ajustamos nosso   definindo como   . middlePoint breakFloor bottom middlePoint+1  Agora para verificar tudo, na função   , geramos o ambiente como antes, e criamos uma nova variável chamada   que conterá nosso resultado. main bsFloor  Para confirmar que nosso algoritmo nos trouxe ao resultado correto, imprimimos   e   , que foi gerado anteriormente aleatoriamente. bsFloor targetFloor  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 é   . 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. O(log(n))  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  página!   Ko-fi  E, como sempre, obrigado pela leitura!   Nicola   Também publicado  aqui

Read My Stories

Este áudio é produzido no idioma original da história!

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

About Author

COMENTARIOS

Rótulos

ESTE ARTIGO FOI APRESENTADO EM

Related Stories

Quer ganhar um concurso de redação do HackerNoon? Aqui está o que os vencedores do concurso #crypto-api recomendam

Vazamento do prompt do sistema Claude Sonnet 3.5: uma análise forense

Telegram: a ponte da Crypto Island para o continente

Aumente sua produtividade com estas 18 ferramentas para desenvolvedores 🚀🔥

Quer ganhar um concurso de redação do HackerNoon? Aqui está o que os vencedores do concurso #crypto-api recomendam

Vazamento do prompt do sistema Claude Sonnet 3.5: uma análise forense

Telegram: a ponte da Crypto Island para o continente

Aumente sua produtividade com estas 18 ferramentas para desenvolvedores 🚀🔥

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps