Tries

A trie stores strings by character path, so prefix queries depend on prefix length instead of the number of stored words. It is useful for autocomplete, dictionary validation, word search, and grouping by prefix, but it can consume much more memory than a sorted array or hash set.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: Interviewers test whether you can design nodes, mark terminal words, and reason about branching factor and memory.

Common pitfalls: Do not use a trie when exact lookup in a Set is enough. Normalize case and Unicode rules before comparing real user-facing strings.

Checklist:

• Mark terminal nodes.
• Count memory per edge.
• Clarify alphabet size.
• Prefer Set for exact lookup only.