Hogyan oldhatjuk meg a Google toborzóinak rejtvényét, amely arról szól, hogy tojást dobnak egy épületből

Nagyon sok remek rejtvény van az állásinterjúk programozásához. Kedvencemet a Google toborzók között is az egyik kedvencként ismerjük:

100 emeleti épületben dolgozol, és 2 egyforma tojást kapsz. Meg kell találnod a legmagasabb emeletet, ahol egy tojást le lehet ejteni törés nélkül. Találjon meg egy olyan algoritmust, amely minimalizálja a dobások számát a legrosszabb esetben.

Néhány feltevést tehetünk:

  • Ha egy petesejt nem törik el, ha valamelyik emeletről leesik, akkor nem törik el, ha bármelyik alsó szintről leesik.
  • A tojást, amely túléli a zuhanást, újra lehet használni.
  • A törött tojást el kell dobni.
  • Az esés hatása minden tojás esetében azonos.
  • Ha egy petesejt eltörik, amikor leesik, akkor eltörik, ha leesik egy magasabb emeletről.

A legtöbb ember ír néhány algoritmust ennek a rejtvénynek a megoldására (és mi is meg fogjuk csinálni), de valójában van egy egyszerű megoldás.

A legegyszerűbb válasz

A minimális padló megszerzésének legegyszerűbb módja egy tojás dobása az első emeletről, majd a második emeletről és így tovább. Így amikor a tojás végleg eltörik, akkor tudni fogjuk, hogy ez a padló. Ez egy megbízható algoritmus, de a legrosszabb esetben 100 dobásra lenne szükség.

Fontos észrevenni, hogy ez az egyetlen megbízható algoritmus, ha csak egy tojása van. Tehát el kell kezdenie ezt az algoritmust, amikor eltöri az első tojást.

Intuitív válasz

Így az első tojásunkat fel kell használni arra, hogy a 100 emeletet a lehető leghatékonyabban kisebb tartományokra osszuk. Így intuitív és népszerű válasz az, hogy az első tojást az emeletek 1 / n-edik részéről dobják ellenőrzésre. Például 1/3. Ekkor az algoritmus a következőképpen fog kinézni:

  • Dobja a tojást a 33. emeletről. Ha elszakad, akkor az első 32 emeletet a második tojás segítségével ellenőrizzük.
  • Egyébként a tojást a 33 + (67 * 1/3) = 55. emeletről dobjuk. Ha elszakad, akkor a második tojás segítségével ellenőrizzük a 34–55. Emeletet.

Az 1/3 legrosszabb forgatókönyve max (33, 24,…) = 33. Így találhatunk egy tökéletes n-t, amely néhány dinamikus programozással optimalizálja a dobások számát. Ez egy értékes megoldás, amely bemutatja a programozási gondolkodást, de nem optimális megoldás.

Tökéletes megoldás

A tökéletes megoldás megértéséhez meg kell értenünk azt az egyensúlyt, amelyet a legrosszabb esetben a dobások számának kiszámításához használunk:

Ahol F (n) a következő emelet, ahonnan az első tojást dobjuk

Ha a következő változót vezetjük be:

akkor az egyensúly a következő:

Az optimális megoldás az, ha ennek a max függvénynek az összes argumentuma megegyezik. Hogyan érhetjük el? A végéről nézve az utolsó D (n) 1 lesz, mert végül eljutunk oda, hogy az első tojásnak csak az egyetlen padlója van. Ezért D (n-1) egyenlőnek kell lennie 2-vel, mert eggyel kevesebb dobása van az első tojásból.

Ekkor látjuk, hogy az első tojást végül a 99. emeletről kell kidobni, korábban 99–2 = 97, korábban 97–3 = 94, 90, 85, 79, 72, 64, 55, 45, 34, 22 és a 9. emelet. Ez optimális megoldás! Így 14 dobásra van szükségünk a legrosszabb esetben (a legkisebb különbség 13, de egy extra dobást kellett elvégeznünk a 9. emeleten).

A válasz megtalálásának egyszerű egyenlete a következő:

Hol fvan az emeletek száma. Ez egyszerűsíthető:

Ez egyenlő:

Jelölje be

Rendben, tehát van megoldás, és minden segítség nélkül kiszámíthatjuk. Ideje ellenőrizni, hogy helyes-e. Erre egy egyszerű Kotlin-programot írunk. Először fejezzük ki, hogyan számoljuk meg a dobások számát valamilyen döntéshez. Ha 2 vagy kevesebb emelet van, akkor annyi dobásra van szükségünk, ahány emelet maradt. Ellenkező esetben a már bemutatott egyensúlyt kell használnunk:

fun maxThrows(floorsLeft: Int, nextFloor: Int): Int = if (floorsLeft <= 2) floorsLeft else maxOf(nextFloor, bestMaxThrows(floorsLeft - nextFloor) + 1)

Itt használtuk a bestMaxThrowsfunkciót. Ez egy hipotetikus függvény, amely számos dobást ad vissza, feltételezve, hogy a következő döntések tökéletesek. Így tudjuk meghatározni:

fun bestMaxThrows(floorsLeft: Int): Int = maxThrows(floorsLeft, bestNextStep(floorsLeft))

Megint csak átruháztuk a következő emelet optimalizálásának felelősségét bestNextStepfunkció. Ez a funkció biztosítja a legjobb következő lépést. Meghatározhatjuk egyszerűen - ha 2 vagy kevesebb emelet van hátra, akkor dobunk egy tojást az első emeletről. Egyébként meg kell vizsgálnunk az összes lehetőséget, és meg kell találnunk az optimálisat. Itt van a megvalósítás:

val bestNextStep(floorsLeft: Int): Int = if (floorsLeft <= 2) 1 else (1..floorsLeft) .toList() .minBy { maxThrows(floorsLeft, it) }!!

Ne feledje, hogy ez a függvény a függvényt használja maxThrows, ezért a visszatéréssel foglalkozunk. Nem jelent problémát, mert bestNextStephíváskor maxThrowsmindig kisebb értékkel hívja floorsLeft(mert nextFloormindig nagyobb, mint 0). Mielőtt használnánk, hozzáadjuk a pufferelést a számítások felgyorsításához:

val bestNextStep: (Int) -> Int = memorise { floorsLeft -> if (floorsLeft <= 2) 1 else (1..floorsLeft) .toList() .minBy { maxThrows(floorsLeft, it) }!!}fun maxThrows(floorsLeft: Int, nextFloor: Int): Int = if (floorsLeft  Int = memorise { floorsLeft -> maxThrows(floorsLeft, bestNextStep(floorsLeft))}fun  memorise(f: (V) -> T): (V) -> T { val map = mutableMapOf
    
     () return { map.getOrPut(it) { f(it) } }}
    

Először ellenőrizhetjük, hogy ugyanazt az eredményt adja-e, mint amit kiszámítottunk:

fun main(args: Array) { print(bestMaxThrows(100)) // Prints: 14}

A válasz jó :) Nézzük meg a következő lépéseinket:

fun main(args: Array) { var floor = 0 while (floor < 100) { val floorsLeft = 100 - floor val nextStep = bestNextStep(floorsLeft) floor += nextStep print("$floor, ") }}

Eredmény:

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

Csak hogy számoltunk! Szép: D

Nagyobb kép

Most van egy szép algoritmusunk, amelyet sok hasonló probléma esetén használhatunk. Például változtathatunk rajta egy kicsit, hogy kiszámítsuk a dobások számát a legvalószínűbb forgatókönyv szerint. Azt is ellenőrizhetjük, hogy ez a minimális dobásszám hogyan fog eltérni az épület magasságától függően. Itt van egy grafikon, amely erre válaszol:

Következtetés

Most jobban felkészült a Google-interjúra, de sokkal fontosabb, hogy most jobban felkészült az általános algoritmikus gondolkodásra. Ez az algoritmus szép, funkcionális megközelítést mutatott be. Hasonló megközelítés alkalmazható mindennapi munkánk során sokféle problémára.

I hope that you liked it. Clap to say thank you and to help others find this article. More interesting materials on my Twitter. Reference me using @marcinmoskala. If you are interested in Kotlin, check out Kotlin Academy and Kotlin Academy portal for Kotlin puzzlers and advanced materials.