Kuidas lahendada Google'i värbajate mõistatus hoonete munade viskamise kohta

Tööintervjuude programmeerimisel on palju häid mõistatusi. Minu lemmikut tuntakse ka Google'i värbajate seas ühe lemmikuna:

Töötate 100 korruselises hoones ja saate 2 ühesugust muna. Peate välja mõtlema kõrgeima põranda, mille muna saab ilma purustamata maha visata. Leidke algoritm, mis minimeerib visete arvu halvimal juhul.

Saame teha mõned eeldused:

  • Kui muna ei murdu, kui ta mõne põrandalt maha kukub, siis see ei purune, kui see mõnelt madalamale põrandale kukub.
  • Kukkumise üle elanud muna saab uuesti kasutada.
  • Katkine muna tuleb minema visata.
  • Kukkumise mõju on kõigi munade puhul sama.
  • Kui muna puruneb kukkumisel, puruneb see kõrgemalt korruselt kukkumise korral.

Enamik inimesi kirjutab selle mõistatuse lahendamiseks mõned algoritmid (ja me teeme seda ka), kuid tegelikult on lihtne lahendus.

Lihtsaim vastus

Lihtsaim viis minimaalse põranda saamiseks on muna viskamine esimeselt korruselt, siis teiselt ja nii edasi. Kui muna on lõpuks katki, saame teada, et see on põrand. See on usaldusväärne algoritm, kuid halvimal juhul kuluks 100 viset.

Oluline on tähele panna, et see on ainus usaldusväärne algoritm, kui teil on ainult üks muna. Nii et peate esimese muna purustamisel seda algoritmi kasutama hakkama.

Intuitiivne vastus

Nii tuleks meie esimest muna kasutada 100 korruse vahemiku võimalikult efektiivseks jagamiseks väiksemateks vahemikeks. Seega on intuitiivne ja populaarne vastus visata esimene muna 1 / n-st põrandast ja seda kontrollida. Näiteks 1/3. Siis näeb algoritm välja järgmine:

  • Viska muna 33. korruselt. Kui see puruneb, kontrollime esimese munaga 32 esimest muna, kasutades teist muna.
  • Vastasel juhul viskame muna 33 + (67 * 1/3) = 55. korruselt. Kui see puruneb, kontrollime teise muna abil põrandaid 34 kuni 55.

Halvim stsenaarium 1/3 jaoks on max (33, 24,…) = 33. Sel viisil võime leida täiusliku n, mis optimeerib viskete arvu mõne dünaamilise programmeerimise abil. See on väärtuslik lahendus, mis esitleb programmeerimismõtlemist, kuid see pole optimaalne lahendus.

Täiuslik lahendus

Täiusliku lahenduse mõistmiseks peame mõistma tasakaalu, mida kasutatakse viske arvu arvutamiseks halvimal juhul:

Kus F (n) on järgmine korrus, kust me viskame esimese muna

Kui võtame kasutusele järgmise muutuja:

siis on tasakaal järgmine:

Optimaalne lahendus on siis, kui selle max funktsiooni kõik argumendid on võrdsed. Kuidas me seda saavutame? Lõpust vaadates saab viimane D (n) 1, sest jõuame lõpuks punkti, kus esimese muna jaoks on ainult üks korrus. Seetõttu peaks D (n-1) olema võrdne kahega, kuna tal on esimesest munast vähem kui üks viske.

Siis näeme, et esimene muna tuleks lõpuks visata 99. korruselt, varem 99–2 = 97, varem 97–3 = 94, 90, 85, 79, 72, 64, 55, 45, 34, 22 ja 9. korrus. See on optimaalne lahendus! Nii vajame halvimal juhul 14 viset (väikseim erinevus on 13, kuid pidime tegema ühe lisaviske 9. korrusele).

Lihtne võrrand vastuse leidmiseks on järgmine:

Kus f on korruste arv. Seda saab lihtsustada järgmiselt:

See võrdub:

Kontrollima

OK, nii et meil on lahendus ja saame selle ilma abita arvutada. On aeg kontrollida, kas see on õige. Kirjutame selleks lihtsa Kotlini programmi. Esiteks öelgem, kuidas mõne otsuse langetamisel visata visete arv. Kui korruseid on 2 või vähem, vajame nii palju viskeid, kui põrandaid on jäänud. Muidu peaksime kasutama juba esitatud tasakaalu:

lõbusad maxThrows (floorLeft: Int, nextForor: Int): Int =
  if (floorLeft <= 2) floorLeft
  else maxOf (järgmine korrus, bestMaxThrows (põrandad vasakul - järgmine korrus) + 1)

Oleme siin kasutanud funktsiooni bestMaxThrows. See on hüpoteetiline funktsioon, mis tagastab mitu viset eeldades, et järgmised otsused on ideaalsed. Nii saame seda määratleda:

lõbus bestMaxThrows (floorLeft: Int): Int =
  maxThrows (põrandadVasa, bestNextStep (põrandadVasa))

Jälle oleme delegeerinud järgmise korruse optimeerimise vastutuse funktsioonile bestNextStep. See funktsioon annab meile parima järgmise sammu. Me saame selle määratleda lihtsalt - kui järele on jäänud 2 või vähem korrust, siis viskame muna teiselt korruselt. Vastasel juhul peame kontrollima kõiki võimalusi ja leidma optimaalne. Siin on rakendamine:

val bestNextStep (floorLeft: Int): Int =
  if (floorLeft <= 2) 1
  muu (1..põrandad vasakul)
        .loetlema()
        .minBy {maxThrows (floorLeft, it)})!

Pange tähele, et see funktsioon kasutab funktsiooni maxThrows, nii et käsitleme kordumist. See ei ole probleem, sest kui bestNextStep kutsub maxThrows, kutsub ta seda alati väiksema väärtusega kui floorLeft (kuna nextFloor on alati suurem kui 0). Enne selle kasutamist lisame arvutuste kiirendamiseks puhverdamise:

val bestNextStep: (Int) -> Int = jätke meelde {floorLeft ->
  if (floorLeft <= 2) 1
  muu (1..põrandad vasakul)
        .loetlema()
        .minBy {maxThrows (floorLeft, it)})!
}

lõbusad maxThrows (floorLeft: Int, nextForor: Int): Int =
  if (floorLeft <= 2) floorLeft
  else maxOf (järgmine korrus, bestMaxThrows (põrandad vasakul - järgmine korrus) + 1)


val bestMaxThrows: (Int) -> Int = jätke meelde {floorLeft ->
  maxThrows (põrandadVasa, bestNextStep (põrandadVasa))
}

lõbus  meelde jätma (f: (V) -> T): (V) -> T {
    val map = muudetavMapOf  ()
    tagasta {map.getOrPut (it) {f (it)}}
}

Esiteks saame kontrollida, kas see annab sama tulemuse, mille oleme arvutanud:

lõbus peamine (args: massiiv ) {
    print (bestMaxThrows (100)) // Trükised: 14
}

Vastus on hea :) Vaatame järgmisi samme:

lõbus peamine (args: massiiv ) {
    var korrus = 0
    kuigi (põrand <100) {
        val põrandadLeft = 100 - korrus
        val nextStep = bestNextStep (floorLeft)
        korrus + = järgmine samm
        print ("$ põrand")
    }
}

Tulemus:

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

Kuidas me arvutasime! Tore: D

Suurem pilt

Nüüd on meil kena algoritm, mida saame kasutada paljude sarnaste probleemide lahendamiseks. Näiteks võime seda pisut muuta, et arvutada kõige tõenäolisema stsenaariumi korral viskete arv. Samuti saame kontrollida, kuidas see minimaalne viskearv erineb, sõltuvalt hoone kõrgusest. Siin on graafik, mis vastab järgmisele:

Järeldus

Olete nüüd oma Google'i intervjuuks paremini valmistunud, kuid veelgi olulisem on, et oleksite üldise algoritmilise mõtlemise jaoks paremini valmis. See algoritm esitas kena ja funktsionaalse lähenemise. Sarnast lähenemisviisi saab kasutada paljude erinevate probleemide korral meie igapäevastes töökohtades.

Loodan, et see meeldis teile. Plaksutage, et tänada teid ja aidata teistel seda artiklit leida. Rohkem huvitavaid materjale minu Twitteris. Viita mulle, kasutades @marcinmoskala. Kui olete Kotlinist huvitatud, siis tutvuge Kotlin Akadeemia ja Kotlin Akadeemia portaali Kotlin mõistatuste ja täiustatud materjalidega.