Coupon collector: сколько покупок до полного набора

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

В каждой упаковке — случайный купон из $n$ равновероятных видов (например, $n=6$ героев). Сколько упаковок в среднем нужно купить, чтобы собрать ВСЕ $n$ видов?

Дай формулу и посчитай для $n=6$.

Темы

тервер мат.ожидание coupon collector геометрическое

Подсказки

• Разбей на этапы: время до получения $k$-го НОВОГО купона, когда уже собрано $k-1$.
• Когда собрано $k-1$, вероятность вытащить новый = $\frac{n-(k-1)}{n}$ — это геометрическое распределение.
• Ожидание геометрического с вероятностью $p$ равно $1/p$. Сложи по всем этапам (linearity).

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

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

Какой уровень знаний нужен для задачи "Coupon collector: сколько покупок до полного набора"?

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

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

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

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

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

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

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

← Все задания