Перейти к содержанию

Средняя

Таблица лидеров сезона

место каждого из 400 миллионов

Условие

Пока таблица помещается в один узел, место игрока — одна команда. На 400 миллионах игроков таблицу режут на шарды, и позиция игрока в своём шарде уже ничего не говорит о его месте в сезоне. Как ответить «какое я место» каждому из 400 миллионов, пока результаты идут по сто пятьдесят тысяч в секунду, — вся задача.

Спроектируйте таблицу лидеров сезона в мобильной онлайн-игре.

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

Считайте, что:

- за матч начисляется от 0 до 30 очков, целым числом, и очки сезона только растут; - очки начисляет игровой сервер, клиент своих очков не присылает; - при равных очках игроки делят место, как в спорте: двое вторых, следующий — четвёртый; - результат матча может прийти повторно и с опозданием: на секунды, а после сбоя игрового сервера на минуты; - по итогам сезона выдаются награды, поэтому итоговые места терять нельзя.

Таблица друзей, таблицы по странам, соседи сверху и снизу, дневные и недельные таблицы, античит и выдача наград в задачу не входят.

Требования

Функциональные 6

  • Очки за матч начисляются по результату, который прислал игровой сервер
  • Экран результата показывает очки за сезон и место с учётом этого матча
  • Первая сотня сезона с местами и очками
  • Своё место и очки в любой момент сезона
  • Каждый месяц сезон начинается с нуля
  • Итоговые места закрытого сезона сохраняются для наград

Нефункциональные 6

  • Место на экране результата: p99 < 200 мс
  • Первая сотня: p99 < 100 мс
  • Место и первая сотня отстают от результатов не больше чем на 2 с
  • Каждый результат матча учитывается ровно один раз, в том числе при повторной доставке
  • Результат матча, законченного в сезоне и принятого в течение 10 минут после его конца, учитывается в этом сезоне
  • Потеря любого узла, где хранится таблица, не теряет очков; места снова точны не позже чем через 10 минут

Задачи того же уровня

Решите задачу у доски

Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям