de Marcin Moskala

Cum se rezolvă puzzle-ul recrutorilor Google despre aruncarea ouălor dintr-o clădire

Cum se rezolva puzzle ul recrutorilor Google despre aruncarea oualor dintr o

Există o mulțime de puzzle-uri grozave pentru programarea interviurilor de muncă. Preferatul meu este, de asemenea, cunoscut ca unul dintre preferatele printre recrutorii Google:

Lucrezi într-o clădire de 100 de etaje și primești 2 ouă identice. Trebuie să vă dați seama de etajul cel mai înalt în care un ou poate fi scăpat fără să se rupă. Găsiți un algoritm care minimizează numărul de aruncări în cel mai rău caz.

Putem face câteva ipoteze:

  • Dacă un ou nu se sparge când este scăpat de la un etaj, atunci nu se va sparge când este scăpat de la orice etaj inferior.
  • Un ou care supraviețuiește unei căderi poate fi folosit din nou.
  • Un ou rupt trebuie aruncat.
  • Efectul unei căderi este același pentru toate ouăle.
  • Dacă un ou se sparge atunci când este scăpat, atunci se rupe dacă este scăpat de la un etaj superior.

Majoritatea oamenilor scrie niște algoritmi pentru a rezolva acest puzzle (și o vom face și noi), dar există de fapt o soluție ușoară.

Cel mai simplu răspuns

Cea mai simplă modalitate de a obține podeaua minimă este de a arunca un ou de la primul etaj, apoi de la al doilea și așa mai departe. În acest fel, atunci când oul este în sfârșit rupt, vom ști că acesta este podeaua. Acesta este un algoritm de încredere, dar în cel mai rău caz ar dura 100 de aruncări.

Important de observat este că este singurul algoritm de încredere atunci când aveți un singur ou. Deci, trebuie să începeți să utilizați acest algoritm atunci când spargeți primul ou.

Răspuns intuitiv

În acest fel, primul nostru ou ar trebui să fie folosit pentru a împărți gama de 100 de etaje în zone mai mici cât mai eficient posibil. Astfel, un răspuns intuitiv și popular este să arunci primul ou din 1 / n-a etajelor pentru a verifica. De exemplu 1/3. Atunci algoritmul va arăta după cum urmează:

  • Aruncă oul de la etajul 33. Dacă se sparge, atunci verificăm primele 32 de etaje folosind al doilea ou.
  • În caz contrar, aruncăm oul de la 33 + (67 * 1/3) = etajul 55. Dacă se sparge, atunci verificăm etajele 34-55 folosind al doilea ou.

Cel mai rău scenariu pentru 1/3 este maxim (33, 24, …) = 33. În acest fel am putea găsi un n perfect care optimizează numărul de aruncări folosind unele programe dinamice. Aceasta este o soluție valoroasă care prezintă gândirea de programare, dar nu este o soluție optimă.

Soluție perfectă

Pentru a înțelege soluția perfectă, trebuie să înțelegem echilibrul care este utilizat pentru a calcula numărul de aruncări în cel mai rău scenariu:

Cum se rezolva puzzle ul recrutorilor Google despre aruncarea oualor dintr o

Unde F (n) este următorul etaj de unde aruncăm primul ou

Dacă introducem următoarea variabilă:

1612010646 660 Cum se rezolva puzzle ul recrutorilor Google despre aruncarea oualor dintr o

atunci echilibrul este următorul:

1612010647 477 Cum se rezolva puzzle ul recrutorilor Google despre aruncarea oualor dintr o

Soluția optimă este atunci când toate argumente din această funcție maximă sunt egale. Cum o realizăm? Privind de la final, ultimul D (n) va fi 1, pentru că vom ajunge în sfârșit la punctul în care există doar etajul unic pentru primul ou. Prin urmare, D (n-1) ar trebui să fie egal cu 2, deoarece are o aruncare mai mică din primul ou.

Vedem atunci că primul ou trebuie aruncat în cele din urmă de la etajul 99, anterior de la 99-2 = 97, anterior de la 97-3 = 94, 90, 85, 79, 72, 64, 55, 45, 34, 22 și etajul 9. Aceasta este o soluție optimă! În acest fel, avem nevoie de 14 aruncări în cel mai rău scenariu (cea mai mică diferență este 13, dar a trebuit să facem o aruncare suplimentară la etajul 9).

Ecuația simplă pentru a găsi răspunsul este următoarea:

1612010647 128 Cum se rezolva puzzle ul recrutorilor Google despre aruncarea oualor dintr o

Unde f este numărul de etaje. Acest lucru poate fi simplificat pentru:

1612010647 628 Cum se rezolva puzzle ul recrutorilor Google despre aruncarea oualor dintr o

Aceasta este egală cu:

1612010647 259 Cum se rezolva puzzle ul recrutorilor Google despre aruncarea oualor dintr o

Verifica

OK, deci avem o soluție și o putem calcula fără niciun ajutor. Este timpul să verificăm dacă este corect. Vom scrie un program Kotlin simplu pentru asta. În primul rând, să exprimăm cum să numărăm numărul de aruncări pentru o anumită decizie. Când sunt 2 sau mai puține etaje, atunci avem nevoie de atâtea aruncări cât au mai rămas etaje. Altfel ar trebui să folosim echilibrul deja prezentat:

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

Am folosit aici bestMaxThrows funcţie. Este o funcție ipotetică care returnează un număr de aruncări presupunând că următoarele decizii sunt perfecte. Acesta este modul în care îl putem defini:

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

Din nou, tocmai am delegat responsabilitatea optimizării etajului următor bestNextStep funcţie. Această funcție ne oferă cel mai bun pas următor. Îl putem defini simplu – când mai sunt 2 sau mai puține etaje, atunci vom arunca un ou de la primul etaj. În caz contrar, trebuie să verificăm toate opțiunile și să o găsim pe cea optimă. Iată implementarea:

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

Rețineți că această funcție folosește maxThrows funcție, deci ne ocupăm de recurență. Nu este o problemă, pentru că atunci când bestNextStep apeluri maxThrows, îl numește întotdeauna cu o valoare mai mică atunci floorsLeft (deoarece nextFloor este întotdeauna mai mare de 0). Înainte de ao folosi, vom adăuga tamponare pentru a accelera calculele:

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 <= 2) floorsLeft  else maxOf(nextFloor, bestMaxThrows(floorsLeft - nextFloor) + 1)val bestMaxThrows: (Int) -> Int = memorise { floorsLeft ->  maxThrows(floorsLeft, bestNextStep(floorsLeft))}fun <V, T> memorise(f: (V) -&gt; T): (V) -> T {    val map = mutableMapOf<V, T&gt;()    return { map.getOrPut(it) { f(it) } }}

Mai întâi, putem verifica dacă returnează același rezultat ca cel pe care l-am calculat:

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

Răspunsul este bun 🙂 Să verificăm următorii pași:

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

Rezultat:

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

Exact cum am calculat! Frumos: D

Imagine mai mare

Acum avem un algoritm frumos pe care îl putem folosi pentru o mulțime de probleme similare. De exemplu, îl putem modifica puțin pentru a calcula numărul de aruncări pentru scenariul cel mai probabilistic. De asemenea, putem verifica modul în care acest număr minim de aruncări va diferi în funcție de înălțimea clădirii. Iată un grafic care răspunde la:

Cum se rezolva puzzle ul recrutorilor Google despre aruncarea oualor dintr o

Concluzie

Acum sunteți mai bine pregătiți pentru interviul dvs. pe Google, dar este mai important să fiți mai bine pregătiți pentru gândirea algoritmică generală. Acest algoritm a prezentat o abordare plăcută și funcțională. O abordare similară poate fi utilizată pentru multe probleme diferite în slujbele noastre de zi cu zi.

Sper că ți-a plăcut. Bate să vă mulțumesc și să îi ajutați pe ceilalți să găsească acest articol. Mai multe materiale interesante pe Twitter-ul meu. Referința-mă folosind @marcinmoskala. Dacă sunteți interesat de Kotlin, verificați Academia Kotlin și Portalul Academiei Kotlin pentru puzzle-uri Kotlin și materiale avansate.