Собеседование для программиста — как решить задачу Google про бросание яиц со здания

Собеседование для программиста — отличный опыт, в ходе него возникает много отличных задач. Моя любимая задача также нравится и рекрутерам Google:

Вы работаете в 100-этажном здании и у вас есть два одинаковых яйца. Вам нужно определить наивысший этаж, с которого можно уронить яйцо и не разбить его. Найдите алгоритм, который минимизирует количество бросков в худшем сценарии развития событий.

Мы можем сделать несколько предположений:

• Если при падении с конкретного этажа яйцо не разбивается, то оно не разобьется и при падении с более низких этажей.
• Если яйцо не разбилось, его можно использовать снова.
• Разбитое яйцо нужно исключить.
• Эффект падения одинаков для всех яиц.
• Если яйцо разбивается при падении, то оно разобьется и при падении с более высокого этажа.

Многие люди написали алгоритм для решения этой задачи (и мы напишем свой), но здесь есть простое решение.

Простой ответ

Простой способ получить минимальный этаж — начать бросать яйцо с первого этажа, потом со второго и так далее. Когда яйцо разобьется, мы будем знать, что это этаж, который мы ищем. Это надежный способ, но в худшем случае он потребует 100 бросков.

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

Интуитивный ответ

Наше первое яйцо нужно использовать, чтобы разделить сто этажей на более мелкие диапазоны как можно эффективнее. Тогда первое яйцо нужно бросить с 1/n этажа, например, ⅓. Тогда алгоритм будет выглядеть так:

• Бросаем яйцо с 33 этажа. Если оно разбивается, проверяем первые 32 этажа вторым яйцом.
• Если оно не разбивается, бросаем яйцо с 33 + (67 * ⅓) = 55 этажа. Если разбивается, проверяем этажи 34–55 вторым яйцом.
• …

В худшем случае для ⅓ (33, 24,…) — это 33. Так мы можем найти идеальный n, который оптимизирует количество бросков при помощи динамического программирования. Это хорошее решение, которое показывает программистское мышление, но оно не является оптимальным.

Идеальное решение

Чтобы понять идеальное решение, нам нужно понять равенство, которое используется для вычисления количества бросков в худшем случае:

Где F(n) — это следующий этаж, с которого мы бросаем первое яйцо.

Если мы введем такую переменную:

То равенство будет выглядеть так:

Оптимальным решением является такое, когда все аргументы этой максимальной функции равны. Как этого достичь? Если смотреть с конца, последним 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 этажа).

Собеседование для программиста: проверка

Ок, у нас есть решение, и мы можем вычислить его без посторонней помощи. Время проверить его правильность. Для этого мы напишем простую программу на 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 всегда больше нуля). Перед использованием добавим буферизацию для ускорения вычислений:

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) -> T): (V) -> T {
    val map = mutableMapOf<V, T>()
    return { map.getOrPut(it) { f(it) } }
}

Теперь мы можем проверить, возвращает ли функция тот же результат, что мы вычислили:

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

Хороший ответ. Проверим следующие шаги:

fun main(args: Array<String>) {
    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, как мы и вычислили.

Большая перспектива

Теперь у нас есть хороший алгоритм для решения похожих проблем. Например, мы можем немного изменить его, чтобы вычислить количество бросков в самом вероятном сценарии. Мы можем проверить, как минимальное число бросков будет зависеть от высоты здания. Вот график с ответом на этот вопрос:

Заключение

Теперь вы лучше подготовлены, может быть собеседование для программиста в Google пройдет проще, но, что важнее, вы лучше знакомы с общим алгоритмическим мышлением. Этот алгоритм представляет хороший функциональный подход, который можно использовать для разных проблем в нашей работе.

Источник