Tries

Trie хранит strings как путь по символам, поэтому prefix queries зависят от длины prefix, а не от числа stored words. Он полезен для autocomplete, dictionary validation, word search и grouping by prefix, но может потреблять намного больше memory, чем sorted array или hash set.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Интервьюеры проверяют, можете ли вы спроектировать nodes, отметить terminal words и рассуждать о branching factor и memory.

Типовые ошибки: Не используйте trie, когда exact lookup в Set достаточно. Нормализуйте case и Unicode rules перед сравнением реальных user-facing strings.

Чеклист:

• Отмечайте terminal nodes.
• Считайте memory per edge.
• Уточните alphabet size.
• Предпочитайте Set только для exact lookup.