Prefix and Suffix Search

Prefix and Suffix Search

What is this problem about?

The Prefix and Suffix Search problem asks you to design a word filter that supports efficient queries: given a prefix and suffix, return the index of the word in the dictionary with both the given prefix and suffix (return the highest index if multiple match). This hard design coding problem uses a trie with combined prefix-suffix keys. The array, hash table, design, trie, and string interview pattern is the core.

Why is this asked in interviews?

Microsoft, Meta, TikTok, and Google ask this because it tests trie design with composite keys — a technique used in autocomplete systems, search engines, and text editors. The clever encoding of (suffix + '#' + prefix) as a single trie key enables O(p+s) query time.

Algorithmic pattern used

Hash map with combined keys. During initialization: for each word at index i, generate all (suffix, prefix) combinations: for each split position k (0 to len), create key word[k:] + '#' + word. Store in hash map as key → max index. For each query (prefix, suffix), look up suffix + '#' + prefix in the hash map.

Example explanation

words=["apple","ape"].

• "apple": keys: "#apple"→0, "e#apple"→0, "le#apple"→0, "ple#apple"→0, "pple#apple"→0, "apple#apple"→0.
• "ape": keys: "#ape"→1, "e#ape"→1, "pe#ape"→1, "ape#ape"→1. Query("ap","e"): key="e#ap"→0 ("apple" at index 0). Return 0.

Common mistakes candidates make

• Only storing prefix or suffix separately (can't combine in a single lookup).
• Not generating all suffix combinations during preprocessing.
• Using '#' as separator without ensuring words don't contain '#'.
• Returning the wrong index when multiple words match (should return highest).

Interview preparation tip

Prefix and Suffix Search demonstrates the "combined key" trie technique: by storing suffix + '#' + word in the hash map, each (suffix, prefix) pair maps to a single lookup. This trade-off (O(word_length²) preprocessing space for O(p+s) query time) is common in search engine optimization. Practice similar "combined constraint search" design problems: range + prefix queries, multi-attribute lookups.