Как да решим пъзела на Google вербовчици за хвърляне на яйца от сграда

Има много страхотни пъзели за програмиране на интервюта за работа. Любимият ми е известен и като един от любимите сред вербовчиците на Google:

Работите в 100 етажна сграда и получавате 2 еднакви яйца. Трябва да разберете най-високия етаж, едно яйце може да бъде изпуснато, без да се счупи. Намерете алгоритъм, който намалява броя на хвърлянията в най-лошия сценарий.

Можем да направим няколко предположения:

  • Ако яйцето не се счупи при падане от някакъв етаж, то то няма да се счупи при изпускане от ниски етажи.
  • Яйце, което оцелява при падане, може да се използва отново.
  • Счупеното яйце трябва да се изхвърли.
  • Ефектът от падането е еднакъв за всички яйца.
  • Ако едно яйце се счупи при изпускане, то ще се счупи, ако се изпусне от по-висок етаж.

Повечето хора пишат някои алгоритми за решаване на този пъзел (и ние също ще го направим), но всъщност има лесно решение.

Най-простият отговор

Най-простият начин да получите минималния под е да хвърлите яйце от първия етаж, след това от втория и така нататък. По този начин, когато яйцето най-накрая се счупи, ще разберем, че това е пода. Това е надежден алгоритъм, но в най-лошия сценарий ще отнеме 100 хвърляния.

Важното е да забележите, че това е единственият надежден алгоритъм, когато имате само едно яйце. Така че трябва да започнете да използвате този алгоритъм, когато счупите първото яйце.

Интуитивен отговор

По този начин първото ни яйце трябва да се използва за разделяне на 100-те етажа на по-малки диапазони възможно най-ефективно. По този начин интуитивен и популярен отговор е да хвърлите първото яйце от 1 / n-тия етаж, за да проверите. Например 1/3. Тогава алгоритъмът ще изглежда по следния начин:

  • Хвърли яйцето от 33-ия етаж. Ако се счупи, проверяваме първите 32 етажа, като използваме второто яйце.
  • В противен случай хвърляме яйцето от 33 + (67 * 1/3) = 55-ия етаж. Ако се счупи, проверяваме етажи от 34 до 55, като използваме второто яйце.
  • ...

Най-лошият сценарий за 1/3 е max (33, 24, ...) = 33. По този начин можем да намерим перфектно n, което оптимизира броя на хвърлянията, използвайки някакво динамично програмиране. Това е ценно решение, което представя програмното мислене, но не е оптимално решение.

Перфектно решение

За да разберем перфектното решение, трябва да разберем равновесието, което се използва за изчисляване на броя на хвърлянията в най-лошия случай:

Където F (n) е следващият етаж, от който хвърляме първото яйце

Ако въведем следната променлива:

тогава равновесието е следното:

Оптималното решение е, когато всички аргументи на тази функция max са равни. Как да го постигнем? Поглеждайки от края, последното D (n) ще бъде 1, защото най-накрая ще стигнем до точката, в която има само единичния под за първото яйце. Следователно D (n-1) трябва да е равно на 2, тъй като има едно по-малко хвърляне на първото яйце.

Тогава виждаме, че първото яйце трябва да бъде хвърлено накрая от 99-ия етаж, преди това от 99–2 = 97, преди това от 97–3 = 94, 90, 85, 79, 72, 64, 55, 45, 34, 22 и 9-ия етаж. Това е оптимално решение! По този начин се нуждаем от 14 хвърляния в най-лошия случай (най-малката разлика е 13, но трябваше да направим едно допълнително хвърляне на 9-ия етаж).

Простото уравнение за намиране на отговора е следното:

Къде fе броят на етажите. Това може да бъде опростено до:

Това е равно на:

Проверете

Добре, така че имаме решение и можем да го изчислим без никаква помощ. Време е да проверите дали е правилно. За това ще напишем проста програма Kotlin. Първо, нека изразим как да преброим броя хвърляния за някакво решение. Когато има 2 или по-малко етажа, тогава се нуждаем от толкова хвърляния, колкото са останали етажи. В противен случай трябва да използваме вече представеното равновесие:

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

Използвахме тук bestMaxThrowsфункцията. Това е хипотетична функция, която връща редица хвърляния, предполагайки, че следващите решения са перфектни. Ето как можем да го определим:

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

Отново, току-що делегирахме отговорността за оптимизацията на следващия етаж bestNextStepфункция. Тази функция ни дава най-добрата следваща стъпка. Можем да го определим просто - когато останат 2 или по-малко етажа, тогава ще хвърлим яйце от първия етаж. В противен случай трябва да проверим всички опции и да намерим оптималната. Ето изпълнението:

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

Имайте предвид, че тази функция използва maxThrowsфункцията, така че се справяме с повторяемост. Това не е проблем, защото когато се bestNextStepобажда maxThrows, той винаги го извиква с по-малка стойност floorsLeft(защото nextFloorвинаги е по-голямо от 0). Преди да го използваме, ще добавим буфериране, за да ускорим изчисленията:

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

Първо, можем да проверим дали връща същия резултат като този, който сме изчислили:

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

Отговорът е добър :) Нека проверим следващите ни стъпки:

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

Резултат:

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

Точно как сме изчислили! Хубаво: D

По-голяма картина

Now we have a nice algorithm that we can use for a lot of similar problems. For example, we can change it a little to calculate the number of throws for the most probabilistic scenario. We can also check how this minimal number of throws will differ depending on the height of the building. Here is a graph answering that:

Conclusion

You are now better prepared for your Google interview, but it is more important that you are now better prepared for general algorithmic thinking. This algorithm presented a nice, functional approach. A similar approach can be used for lot’s of different problems in our daily jobs.

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.