
Условие
Выбрать победителя из двух тысяч кандидатов за пятьдесят миллисекунд и не потратить чужой бюджет сверх согласованного. Точность и задержка здесь обе стоят денег, и размен между ними приходится называть числом.
Спроектируйте показ рекламы на страницах сервиса.
Пользователь открывает страницу; в отведённых местах показываются объявления. Рекламодатель заводит кампанию с дневным бюджетом и ставкой, платит за показы или за клики, и кампания останавливается, когда бюджет исчерпан.
Считайте, что:
- страница не ждёт рекламу: на весь аукцион есть около 50 мс;
- кликают примерно по одному показу из ста, и клик приходит в среднем через минуту после показа;
- популярная кампания расходует дневной бюджет за минуты;
- рекламодатель согласен на перерасход дневного бюджета до 2%, если о нём сказано заранее;
- страница перезагружается, запросы повторяются, а часть событий приходит от источников, которым нельзя доверять.
Модели предсказания вероятности клика, таргетинг по интересам как система, креативы и модерация, отчёты рекламодателю и внешние биржи в задачу не входят.
Требования
Функциональные 7
- Отбор объявлений, подходящих под запрос и условия таргетинга
- Аукцион: выбор победителя и определение цены
- Страница получает ответ в срок: если аукцион не успел, показывается запасная выдача
- Учёт показов и кликов
- Расход дневного бюджета кампании
- Остановка кампании при исчерпании бюджета
- Повторное событие показа одного и того же аукциона не оплачивается дважды
Нефункциональные 4
- Аукцион отвечает за 50 мс; при превышении страница получает запасную выдачу
- Перерасход дневного бюджета не превышает 2% и объявлен рекламодателю
- Клик не теряется и не дублируется: расхождение по кликам 0
- Итоговый счёт отличается от расхода на момент остановки кампании не более чем на 0,5%
Задачи того же уровня
СложнаяРекомендательная системаЛента рекомендаций на сто миллионов человек в сутки. Правильного ответа у неё нет, а система учится на данных, которые сама же породила.
СложнаяСбор метрик с миллиона серверовДесять миллионов точек в секунду — решаемая задача. Систему убивает число уникальных рядов: метка с идентификатором запроса порождает новые ряды быстрее, чем хранилище успевает их принимать.
СложнаяСинхронизация файлов между устройствамиФайл правится на трёх устройствах, часть из них была офлайн, и все обязаны прийти к одному состоянию, не потеряв ничью правку молча. Нерв задачи: найти изменения среди десятков тысяч файлов и не гонять по сети мегабайты ради небольшой правки.
Решите задачу у доски
Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям




