Две жемчужины и 100 этажей (egg drop)

Условие задания

Есть **2** одинаковых хрустальных шарика и здание в **100** этажей. Шарик разбивается, если бросить с этажа $\ge K$ (порог неизвестен), и цел ниже $K$. Нужно найти $K$, минимизировав **число бросков в ХУДШЕМ случае**. Сколько бросков достаточно?

Темы

логика оптимизация минимакс egg drop

Подсказки

• С одним шариком пришлось бы идти по одному этажу снизу (до 100 бросков) — нельзя «прыгать».
• Первый шарик бросаем с УБЫВАЮЩИМ шагом, чтобы выровнять худший случай.
• Если первый бросок с этажа $n$, далее шаги $n-1, n-2, \dots$; нужно $n(n+1)/2 \ge 100$.

Все тестовые задания →

Частые вопросы

Какой уровень знаний нужен для задачи "Две жемчужины и 100 этажей (egg drop)"?

Это задание для уровня Senior. Senior-уровень — глубокое понимание темы, опыт решения нестандартных задач, обсуждение trade-off на собеседовании.

На каких собеседованиях встречается такая задача?

Подобные задания в категории «Логика» регулярно дают на собеседованиях аналитика данных в Яндекс, Сбер, Ozon, Авито, Тинькофф, Wildberries, T-Bank, X5, ВТБ и других крупных IT-компаниях. Тематика: логика, оптимизация, минимакс, egg drop.

Сколько времени даётся на решение?

На реальном собеседовании на подобную задачу отводится 30-60 минут с обсуждением подходов, оптимизаций и trade-off. Для тренировки рекомендуем сначала решить самостоятельно, потом сверить с эталонным решением и подсказками.

Где ещё потренироваться по теме «Логика»?

На zasqlpython.ru есть другие задания в категории «Логика», продуктовые кейсы, справочник метрик, AI мок-собеседование с разбором ваших ответов.

← Все задания