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

Средняя

Подсказки при вводе

Условие

Подсказок в восемь раз больше, чем самих поисков, а предрасчёт для всех префиксов стоит сотни гигабайт. Задача не про префиксное дерево, а про то, что в него не помещается.

Спроектируйте подсказки в строке поиска.

Человек начинает печатать, и под строкой появляются варианты: популярные запросы, то, что он искал раньше, свежие темы. Подсказка обновляется по мере ввода и должна появляться быстрее, чем человек напечатает следующий символ.

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

- подсказка запрашивается несколько раз за один поиск — на каждое нажатие; - популярность формулировок меняется: сегодняшняя новость завтра исчезнет; - человек ошибается в раскладке и делает опечатки; - подсказка должна появиться не позже чем через 100 мс, иначе она бесполезна.

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

Требования

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

  • Подсказки по началу ввода, отсортированные по полезности
  • Личная история запросов среди подсказок
  • Новые формулировки попадают в подсказки
  • Устойчивость к частым опечаткам и неверной раскладке клавиатуры
  • Выбор подсказки ведёт в поиск по ней
  • Удаление записи из личной истории: она больше не показывается

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

  • Подсказка: p99 < 100 мс
  • Новая популярная формулировка появляется в подсказках не позже чем через час
  • Отказ персонализации не убирает подсказки, а убирает только личные
  • Недоступность сервиса подсказок не блокирует ввод и поиск
  • Формулировка, снятая модератором, исчезает из подсказок не позже чем через 5 минут

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

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

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