Sådan løses Googles rekrutterers puslespil om at smide æg fra en bygning

Der er mange gode gåder til programmering af jobinterviews. Min favorit er også kendt som en af ​​favoritterne blandt Google-rekrutterere:

Du arbejder i en bygning på 100 etager, og du får 2 identiske æg. Du skal finde ud af den højeste etage, hvor et æg kan smides uden at gå i stykker. Find en algoritme, der minimerer antallet af kast i værste fald.

Vi kan antage et par antagelser:

  • Hvis et æg ikke går i stykker, når det falder ned fra et eller andet gulv, går det ikke i stykker, når det falder ned fra nogen lavere etager.
  • Et æg, der overlever et fald, kan bruges igen.
  • Et knust æg skal kasseres.
  • Effekten af ​​et fald er den samme for alle æg.
  • Hvis et æg går i stykker, når det droppes, vil det knække, hvis det falder ned fra et højere gulv.

De fleste mennesker skriver nogle algoritmer for at løse dette puslespil (og vi gør det også), men der er faktisk en nem løsning.

Enkleste svar

Den enkleste måde at opnå det minimale gulv på er at smide et æg fra første sal, derefter fra det andet osv. Denne måde, når ægget endelig er brudt, så ved vi, at dette er gulvet. Dette er en pålidelig algoritme, men i værste fald tager det 100 kast.

Det vigtige at bemærke er, at det er den eneste pålidelige algoritme, når du kun har et æg. Så du skal begynde at bruge denne algoritme, når du bryder det første æg.

Intuitivt svar

På denne måde skal vores første æg bruges til at opdele de 100 etager i mindre intervaller så effektivt som muligt. Således er et intuitivt og populært svar at smide det første æg fra 1 / nte af gulvene for at kontrollere. For eksempel 1/3. Derefter vil algoritmen se ud som følger:

  • Kast ægget fra 33. etage. Hvis det går i stykker, kontrollerer vi de første 32 etager ved hjælp af det andet æg.
  • Ellers smider vi ægget fra 33 + (67 * 1/3) = 55. etage. Hvis det går i stykker, kontrollerer vi etage 34 til 55 ved hjælp af det andet æg.
  • ...

Worst case-scenariet for 1/3 er max (33, 24,…) = 33. På denne måde finder vi muligvis et perfekt n, der optimerer antallet af kast ved hjælp af dynamisk programmering. Dette er en værdifuld løsning, der præsenterer programmeringstenkning, men det er ikke en optimal løsning.

Perfekt løsning

For at forstå den perfekte løsning er vi nødt til at forstå ligevægten, der bruges til at beregne antallet af kast i værste fald:

Hvor F (n) er den næste etage, hvorfra vi kaster det første æg

Hvis vi introducerer følgende variabel:

så følger ligevægt:

Den optimale løsning er, når alle argumenter for denne max-funktion er ens. Hvordan opnår vi det? Ser man fra slutningen, bliver den sidste D (n) 1, fordi vi endelig kommer til det punkt, hvor der kun er etage til det første æg. Derfor skal D (n-1) være lig med 2, fordi det har et mindre kast af det første æg.

Vi ser derefter, at det første æg endelig skal kastes fra 99. etage, tidligere fra 99-2 = 97, tidligere fra 97-3 = 94, 90, 85, 79, 72, 64, 55, 45, 34, 22 og 9. sal. Dette er en optimal løsning! På denne måde har vi brug for 14 kast i værste fald (den mindste forskel er 13, men vi var nødt til at tage et ekstra kast på 9. etage).

Enkel ligning for at finde svaret er følgende:

Hvor fer antallet af etager. Dette kan forenkles til:

Det svarer til:

Kontrollere

OK, så vi har en løsning, og vi kan beregne den uden hjælp. Det er tid til at kontrollere, om det er korrekt. Vi skriver et simpelt Kotlin-program til det. Lad os først udtrykke, hvordan man tæller antallet af kast for en beslutning. Når der er 2 eller færre etager, så har vi brug for så mange kast, som der er etager tilbage. Ellers skal vi bruge den allerede præsenterede ligevægt:

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

Vi har brugt bestMaxThrowsfunktionen her. Det er en hypotetisk funktion, der returnerer et antal kast, forudsat at de næste beslutninger er perfekte. Sådan kan vi definere det:

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

Igen har vi lige delegeret ansvaret for optimering af næste etage til bestNextStepfungere. Denne funktion giver os det bedste næste trin. Vi kan definere det enkelt - når der er 2 eller færre etager tilbage, kaster vi et æg fra første sal. Ellers skal vi kontrollere alle muligheder og finde den optimale. Her er implementeringen:

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

Bemærk, at denne funktion bruger maxThrowsfunktionen, så vi håndterer gentagelse. Det er ikke et problem, for når det bestNextStepkaldes maxThrows, kalder det det altid med en mindre værdi floorsLeft(fordi nextFloordet altid er større end 0). Før vi bruger det, vil vi tilføje buffering for at fremskynde beregningerne:

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) } }}
    

Først kan vi kontrollere, om det returnerer det samme resultat som det, vi har beregnet:

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

Svaret er godt :) Lad os tjekke vores næste trin:

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

Resultat:

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

Lige hvordan vi beregnede! Dejligt: ​​D

Større billede

Nu har vi en god algoritme, som vi kan bruge til mange lignende problemer. For eksempel kan vi ændre det lidt for at beregne antallet af kast for det mest sandsynlige scenarie. Vi kan også kontrollere, hvordan dette minimale antal kast vil variere afhængigt af bygningens højde. Her er en graf, der svarer på det:

Konklusion

Du er nu bedre forberedt på dit Google-interview, men det er vigtigere, at du nu er bedre forberedt på generel algoritmisk tænkning. Denne algoritme præsenterede en god, funktionel tilgang. En lignende tilgang kan bruges til mange forskellige problemer i vores daglige job.

Jeg håber, at du kunne lide det. Klapp for at sige tak og hjælpe andre med at finde denne artikel. Mere interessante materialer på min Twitter. Henvis mig ved hjælp af @marcinmoskala. Hvis du er interesseret i Kotlin, skal du tjekke Kotlin Academy og Kotlin Academy-portalen for Kotlin-puslespilere og avancerede materialer.