PPractick

The problem

You're building the core data structure behind a search engine's autocomplete and typo-suggestion service. The basic Trie (insert/search/startsWith) isn't enough — your team needs a production-grade Trie that also supports deletion (e.g., removing a deprecated search term) and counting how many indexed words exactly match a given string, or how many indexed words have a given string as a prefix — both needed for ranking suggestions by popularity. Design and implement this Trie class.

Function signature

class Trie {
public:
    Trie();
    void insert(string word);
    int countWordsEqualTo(string word);     // exact match count
    int countWordsStartingWith(string prefix); // prefix match count
    void erase(string word);                 // remove one occurrence of word
};

Test cases

Operations (in order)	Output / State
insert("apple"), insert("apple"), insert("app")	Trie now has "apple" x2, "app" x1
countWordsEqualTo("apple")	2
countWordsStartingWith("app")	3 (counts "apple" x2 + "app" x1, since all start with "app")
erase("apple")	One "apple" removed, one remains
countWordsEqualTo("apple")	1
countWordsStartingWith("app")	2 (1 remaining "apple" + 1 "app")
erase("apple"), erase("app")	All words removed
countWordsEqualTo("app")	0
countWordsStartingWith("a")	0
erase("nonexistent")	No-op, should not crash or corrupt state

(This mirrors a well-known GFG/competitive-programming Trie variant where each node tracks both endCount and prefixCount, supporting duplicates and proper deletion.)

How interviewers phrase it

• "Design a Trie that supports insert, exact-match count, prefix-match count, and deletion."
• "Implement a Trie class — but beyond the basics, I also want countWordsEqualTo, countWordsStartingWith, and erase."
• This is a system-design-flavored DSA problem — interviewers care heavily about clean class design, correct invariant maintenance (especially during deletion), and how you reason about edge cases like deleting a word that doesn't exist or deleting a prefix of another existing word.

Clarifying questions to ask

1. Can the same word be inserted multiple times — should the Trie track counts (multiplicities) rather than just boolean presence? (Yes — this is what makes countWordsEqualTo meaningful beyond just 0/1.)
2. For erase, should I assume the word being erased is guaranteed to exist, or do I need to handle erasing a non-existent word gracefully (no-op, no crash)? (Always handle defensively — confirm expected behavior.)
3. Should deletion physically remove unused Trie nodes (memory cleanup), or is it acceptable to just decrement counts and leave empty nodes in place? (Proper implementations clean up nodes that become entirely unused — discuss the tradeoff.)
4. What's the character set — lowercase English letters only, or broader? (Affects whether to use a fixed-size array of 26 children or a hash map.)
5. Are operations expected to be thread-safe / concurrent? (Usually no for a DSA interview, but worth a quick check if the role is systems-focused.)

Follow-ups to expect

1. "How do you maintain correctness when erasing a word that is also a prefix of another existing word?"
2. "Walk through why you need TWO counters per node (endCount and prefixCount), not just one."
3. "How would you implement actual memory cleanup during erase (removing now-unused nodes), and what's the complexity tradeoff?"
4. "What if you wanted to support wildcard search (e.g., '.' matches any character) on top of this Trie?"
5. "How would this Trie need to change to support case-insensitive search, or Unicode characters?"
6. "What's the space complexity in the worst case, and how would real-world usage (like an actual search engine) optimize this further?"

Related questions

• Trie Implementation and Operations Hard
• Implement Min Stack Hard
• LFU Cache Hard
• Kth largest element in a stream of running integers Hard
• Find Median from Data Stream Hard
• Serialize and De-serialize BT Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in