Движок автодополнения на основе trie

До любого обхода зафиксируй форму одного TrieNode. Классическое представление хранит потомков в массиве из 26 слотов; практичное использует Map<string, TrieNode> (или простой объект), чтобы алфавит был открытым, а память масштабировалась с фактическим набором символов, а не с наихудшим. Каждому узлу нужны три вещи: его потомки, булево значение, помечающее его терминалом допустимого слова, и вес, связанный с этим словом (ноль или отсутствует, когда узел не является терминалом). Вес живёт на терминальном узле, а не на ведущем к нему ребре, потому что префикс разделяет рёбра с многими словами, и все их веса нельзя записать на одно ребро. Выбор неправильного представления здесь потребует полного переписывания на следующем этапе, поэтому явно продумай расположение памяти: массив из 26 слотов тратит 26 × pointer_size на каждый внутренний узел, даже когда присутствует только один потомок, что нормально при тысячах слов, но болезненно при миллионах. Задокументируй свой выбор и его компромисс до написания класса.

Реализуй три простейшие операции и зафиксируй их гарантии сложности точно. insert(word, weight) идёт от корня, создавая узлы по мере необходимости, затем помечает последний узел как терминал и записывает его вес. has(word) идёт по тому же пути и возвращает true только если последний узел существует и помечен как терминал — возврат true для хранимого префикса, но не полного слова, является классической ошибкой на единицу здесь. startsWith(prefix) идентичен has, но останавливается на узле префикса и возвращает true, если этот узел вообще существует, независимо от isEnd — именно эта операция делает trie эффективным для автодополнения. Все три операции O(k), где k — длина входной строки; рекурсивная реализация допустима, но итеративная избегает давления на стек вызовов при длинных строках. Семантика обновления веса: если insert вызван дважды для одного и того же слова, перезапиши вес, а не накапливай — тест-сьют утверждает это.

Реализуй обход поддерева, на котором строится автодополнение: дан префикс, перейди к узлу префикса, затем запусти поиск в глубину от этого узла для сбора каждого терминала с его словом и весом. Это операция O(префикс + размер_поддерева) — поддерево может быть большим (каждое слово, разделяющее префикс), поэтому DFS не должен выделять структуры на узел помимо стека рекурсии или небольшой очереди; просто накапливай пары (слово, вес). Построение слова-кандидата по мере рекурсии — стандартный приём: передавай накопленную строку вниз по DFS, а не восстанавливай её из пути. Отсутствующий префикс (нет узла для последнего символа) должен возвращать пустой коллектор, а не выбрасывать — это случай, который автодополнение видит при каждом нажатии клавиши, пока пользователь не набрал распознанный префикс. Выходом этого шага является несортированный массив всех подходящих пар (слово, вес); ранжирование происходит на следующем этапе.

Преврати несортированный список кандидатов из предыдущего этапа в ранжированный ограниченный результат. Сортируй собранные пары (слово, вес) по убыванию веса, а при равных весах — по слову в лексикографически возрастающем порядке — это правило разрешения ничьих делает вывод автодополнения предсказуемым между запусками и тестируемым с точными утверждениями. Возьми только первые k пар и верни их слова в виде строкового массива. Наивный подход — собери все, отсортируй все, обрежь — корректен и хорош для тысяч слов. На senior-глубине ты должен понимать, когда мин-куча размера k выигрывает у сортировки: если поддерево содержит N слов, сбор всех и последующая сортировка — O(N log N); поддержание кучи размера k во время DFS — O(N log k) и избегает материализации полного списка кандидатов, что важно при k << N. Сначала реализуй наивную сортировку, затем укажи альтернативу с кучей как комментарий, а не как преждевременную оптимизацию.

Заставь trie корректно реагировать на изменения весов и удаления без перестройки. Вызов insert для уже хранимого слова должен перезаписать его вес на месте (узел уже существует, просто обнови поле weight), и изменение должно немедленно отражаться в следующем вызове autocomplete без шага инвалидации кеша — потому что кеша нет; DFS пересчитывает ранжирование при каждом вызове. Удаление (если ты решишь его реализовать) сложнее: нужно сбросить флаг isEnd и обнулить вес, затем опционально обрезать листовые узлы без потомков-допустимых-слов для экономии памяти, но обрезка не требуется для корректности. Тонкая ошибка, которую надо избежать, — устаревшее агрегатное состояние: некоторые реализации trie кешируют 'максимальный вес в поддереве' на внутренних узлах для раннего обрезания DFS; если ты это делаешь, обновление веса должно распространить новый максимум вверх по цепочке предков. Реши заранее, хочешь ли ты эту оптимизацию и какой инвариант консистентности берёшь на себя поддерживать.

Сравни свою реализацию с альтернативой на плоском Map и сформулируй, когда одна выигрывает у другой. Плоский Map<string, number> (слово → вес) поддерживает insert и has за O(k) хеш-время, autocomplete за O(N × k) время полного сканирования, где N — общее количество слов. Для небольших словарей плоский Map часто выигрывает по памяти, потому что trie выделяет один узел на символ, а не одну запись на слово. Trie выигрывает, когда запросы по префиксу часты, а словарь велик: O(префикс + результаты) выигрывает у O(N) для autocomplete, когда N >> результаты. Замерь пиковое количество узлов после вставки реалистичного списка слов (например, 5000 английских слов), вычисли примерную память на узел (запись Map ≈ 64 байта на V8, узел с потомками Map ≈ 96–128 байт) и напиши комментарий, указывающий точку пересечения — количество слов и паттерн запросов, при которых trie начинает окупаться в скорости запросов против накладных расходов по памяти. Это именно тот анализ, который senior-инженер делает перед выбором структуры данных в продакшне.