Kuinka ratkaista Google-rekrytoijien palapeli munien heittämisestä rakennuksesta

Työhaastattelujen ohjelmoinnissa on paljon hienoja palapelit. Suosikkini tunnetaan myös yhtenä Google-rekrytoijien suosikeista:

Työskentelet 100 kerrosrakennuksessa ja saat 2 identtistä munaa. Sinun on selvitettävä korkein kerros, josta muna voidaan pudottaa rikkomatta. Etsi algoritmi, joka minimoi heittojen määrän pahimmassa tapauksessa.

Voimme tehdä muutamia oletuksia:

  • Jos muna ei rikkoudu pudotessaan jostakin kerroksesta, se ei rikkoudu pudotettaessa mistä tahansa alakerroksesta.
  • Munua, joka selviää pudotuksesta, voidaan käyttää uudelleen.
  • Murtunut muna on hävitettävä.
  • Pudonnan vaikutus on sama kaikille munille.
  • Jos muna murtuu pudotettaessa, se hajoaa, jos putoaa korkeammalta kerrokselta.

Useimmat ihmiset kirjoittavat joitain algoritmeja tämän palapelin ratkaisemiseksi (ja me myös teemme sen), mutta todellakin on olemassa helppo ratkaisu.

Yksinkertaisin vastaus

Yksinkertaisin tapa saada pienin kerros on heittää muna ensimmäisestä kerroksesta, sitten toisesta ja niin edelleen. Tällä tavalla kun muna lopulta rikkoutuu, tiedämme, että tämä on lattia. Tämä on luotettava algoritmi, mutta pahimmassa tapauksessa se vie 100 heittoa.

Tärkeä huomata, että se on ainoa luotettava algoritmi, kun sinulla on vain yksi muna. Joten sinun täytyy alkaa käyttää tätä algoritmia murtaessasi ensimmäisen munan.

Intuitiivinen vastaus

Tällä tavalla ensimmäistä munaamme tulisi käyttää jakamaan 100 lattia-alue pienempiin alueisiin mahdollisimman tehokkaasti. Siten intuitiivinen ja suosittu vastaus on heittää ensimmäinen muna yhdestätoista kerroksesta tarkistaakseen. Esimerkiksi 1/3. Sitten algoritmi näyttää seuraavalta:

  • Heitä muna 33. kerroksesta. Jos se rikkoutuu, tarkistamme ensimmäiset 32 ​​kerrosta toisella munalla.
  • Muussa tapauksessa heitämme muna 33 + (67 * 1/3) = 55. kerroksesta. Jos se rikkoutuu, tarkistamme kerrokset 34 - 55 toisella munalla.
  • ...

1/3: n pahin tapaus on maks. (33, 24,…) = 33. Tällä tavoin voimme löytää täydellisen n, joka optimoi heittäytymisten määrän jollain dynaamisella ohjelmoinnilla. Tämä on arvokas ratkaisu, joka esittelee ohjelmointiajattelua, mutta se ei ole optimaalinen ratkaisu.

Täydellinen ratkaisu

Täydellisen ratkaisun ymmärtämiseksi meidän on ymmärrettävä tasapaino, jota käytetään heittojen määrän laskemiseen pahimmassa tapauksessa:

Missä F (n) on seuraava kerros, josta heitämme ensimmäisen munan

Jos esittelemme seuraavan muuttujan:

silloin tasapaino on seuraava:

Optimaalinen ratkaisu on, kun kaikki tämän max-funktion argumentit ovat samat. Kuinka saavutamme sen? Viimeisimmästä D (n): sta tulee lopusta katsottuna 1, koska pääsemme lopulta pisteeseen, jossa ensimmäiselle munalle on vain yksi kerros. Siksi D (n-1) tulisi olla yhtä suuri kuin 2, koska siinä on yksi munanväli vähemmän ensimmäisestä munasta.

Silloin näemme, että ensimmäinen muna pitäisi heittää lopulta 99. kerroksesta, aikaisemmin 99–2 = 97, aiemmin 97–3 = 94, 90, 85, 79, 72, 64, 55, 45, 34, 22 ja 9. kerros. Tämä on optimaalinen ratkaisu! Tällä tavoin tarvitsemme 14 heittoa pahimmassa tapauksessa (pienin ero on 13, mutta jouduimme tekemään yhden ylimääräisen heiton 9. kerroksessa).

Yksinkertainen yhtälö vastauksen löytämiseksi on seuraava:

Missä f on kerrosten lukumäärä. Tätä voidaan yksinkertaistaa:

Se on yhtä suuri kuin:

Tarkistaa

OK, joten meillä on ratkaisu ja voimme laskea sen ilman apua. On aika tarkistaa, onko se oikea. Me kirjoitamme siihen yksinkertaisen Kotlin-ohjelman. Ensinnäkin ilmaistaan ​​kuinka laskea heittojen määrä jokaisesta päätöksestä. Kun kerroksia on 2 tai vähemmän, tarvitsemme niin monta heittoa, kuin kerroksia on jäljellä. Muussa tapauksessa meidän pitäisi käyttää jo esitettyä tasapainoa:

hauskat maxThrows (floorLeft: Int, nextFloor: Int): Int =
  if (Lattia Vasen <= 2) Lattia Vasen
  else maxOf (nextFloor, bestMaxThrows (floorLeft - nextFloor) + 1)

Olemme käyttäneet täällä bestMaxThrows-toimintoa. Se on hypoteettinen toiminto, joka palauttaa useita heittoja olettaen, että seuraavat päätökset ovat täydellisiä. Näin voimme määritellä sen:

hauskaa bestMaxThrows (floorLeft: Int): Int =
  maxThrows (lattiat Vasen, paras Seuraava Askel (Lattiat Vasen))

Olemme jälleen delegoineet seuraavan kerroksen optimoinnin vastuun bestNextStep-toiminnolle. Tämä toiminto antaa meille parhaan seuraavan vaiheen. Voimme määritellä sen yksinkertaisesti - kun jäljellä on 2 tai vähemmän kerroksia, heitämme munan ensimmäisestä kerroksesta. Muuten meidän on tarkistettava kaikki vaihtoehdot ja löydettävä optimaalinen vaihtoehto. Tässä on toteutus:

val bestNextStep (floorLeft: Int): Int =
  if (floorLeft <= 2) 1
  muuta (1..kerroksetLauta)
        .listata()
        .minBy {maxThrows (floorLeft, it)})!

Huomaa, että tämä toiminto käyttää maxThrows-toimintoa, joten käsittelemme toistumista. Se ei ole ongelma, koska kun bestNextStep kutsuu maxThrows, se kutsuu sitä aina pienemmällä arvolla kuin floorLeft (koska nextFloor on aina suurempi kuin 0). Ennen kuin käytämme sitä, lisäämme puskuroinnin nopeuttaaksesi laskelmia:

val bestNextStep: (Int) -> Int = muista {floorLeft ->
  if (floorLeft <= 2) 1
  muuta (1..kerroksetLauta)
        .listata()
        .minBy {maxThrows (floorLeft, it)})!
}

hauskat maxThrows (floorLeft: Int, nextFloor: Int): Int =
  if (Lattia Vasen <= 2) Lattia Vasen
  else maxOf (nextFloor, bestMaxThrows (floorLeft - nextFloor) + 1)


val bestMaxThrows: (Int) -> Int = muista {floorLeft ->
  maxThrows (lattiat Vasen, paras Seuraava Askel (Lattiat Vasen))
}

hauskaa  muista (f: (V) -> T): (V) -> T {
    val map = muutettavissaMapOf  ()
    palauta {map.getOrPut (it) {f (it)}}
}

Ensinnäkin voimme tarkistaa, tuottaako se saman tuloksen kuin mitä olemme laskeneet:

hauska main (args: Array ) {
    tulosta (bestMaxThrows (100)) // Tulosteet: 14
}

Vastaus on hyvä :) Katsotaanpa seuraavia vaiheita:

hauska main (args: Array ) {
    var lattia = 0
    kun taas (kerros <100) {
        val floorLeft = 100 - kerros
        val nextStep = bestNextStep (floorLeft)
        kerros + = seuraava askel
        tulosta ("$ kerros")
    }
}

Tulos:

9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100,

Kuinka lasimme! Mukava: D

Isompi kuva

Nyt meillä on mukava algoritmi, jota voimme käyttää moniin vastaaviin ongelmiin. Voimme esimerkiksi muuttaa sitä hiukan laskeaksesi heittojen määrän todennäköisimmälle skenaarialle. Voimme myös tarkistaa, kuinka tämä vähäinen heittojen lukumäärä eroaa rakennuksen korkeudesta riippuen. Tässä on kaavio, joka vastaa:

johtopäätös

Olet nyt paremmin varautunut Google-haastatteluosi, mutta on tärkeämpää, että olet nyt paremmin varautunut yleiseen algoritmisiin ajatteluun. Tämä algoritmi esitti mukavan, toimivan lähestymistavan. Samanlaista lähestymistapaa voidaan käyttää moniin erilaisiin ongelmiin päivittäisessä työssämme.

Toivon, että pidit siitä. Taputtaa kiittääkseni ja auttaa muita löytämään tämän artikkelin. Lisää mielenkiintoisia materiaaleja Twitterissäni. Ohjaa minua @marcinmoskalan avulla. Jos olet kiinnostunut Kotlinista, tutustu Kotlin Academy- ja Kotlin Academy -portaaliin Kotlin-pulmapeleistä ja edistyneistä materiaaleista.