
Условие
Подсказок в восемь раз больше, чем самих поисков, а предрасчёт для всех префиксов стоит сотни гигабайт. Задача не про префиксное дерево, а про то, что в него не помещается.
Спроектируйте подсказки в строке поиска.
Человек начинает печатать, и под строкой появляются варианты: популярные запросы, то, что он искал раньше, свежие темы. Подсказка обновляется по мере ввода и должна появляться быстрее, чем человек напечатает следующий символ.
Считайте, что:
- подсказка запрашивается несколько раз за один поиск — на каждое нажатие; - популярность формулировок меняется: сегодняшняя новость завтра исчезнет; - человек ошибается в раскладке и делает опечатки; - подсказка должна появиться не позже чем через 100 мс, иначе она бесполезна.
Сама выдача поиска, исправление опечаток в результатах, голосовой ввод и подсказки внутри документа в задачу не входят.
Требования
Функциональные 6
- Подсказки по началу ввода, отсортированные по полезности
- Личная история запросов среди подсказок
- Новые формулировки попадают в подсказки
- Устойчивость к частым опечаткам и неверной раскладке клавиатуры
- Выбор подсказки ведёт в поиск по ней
- Удаление записи из личной истории: она больше не показывается
Нефункциональные 5
- Подсказка: p99 < 100 мс
- Новая популярная формулировка появляется в подсказках не позже чем через час
- Отказ персонализации не убирает подсказки, а убирает только личные
- Недоступность сервиса подсказок не блокирует ввод и поиск
- Формулировка, снятая модератором, исчезает из подсказок не позже чем через 5 минут
Задачи того же уровня
СредняяПоиск заведений рядомОдин и тот же запрос «в радиусе пяти километров» находит двадцать заведений в пригороде и двадцать тысяч в центре города. Задача про то, как уложиться в 300 мс при таком разбросе плотности.
СредняяПоиск по каталогу маркетплейсаПолнотекстовый поиск по ста миллионам товаров — решённая задача. Нерешённая рядом: счётчики у значений фильтров, которые зависят от выбранных фильтров и пересчитываются на каждый запрос, тысячи раз в секунду.
СредняяПриложение знакомств: колода и взаимный лайкЛента, где повтор ломает продукт, а матч должен возникнуть ровно один раз, даже когда двое лайкнули друг друга одновременно. Нерв задачи — дёшево помнить, что человеку уже показывали, и закрыть гонку взаимного лайка.
Решите задачу у доски
Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям




