58 / 72
ПрактикаПродвинутыйSenior

Взвешенный случайный выбор за O(log n)

Частота на собеседованиях: Низкая - нишевая, но эффектная задача на senior-собеседованияхСпрашивают в: Яндекс, Big Tech-style

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

Наивное решение - O(n) на каждый выбор