DSA interview question

Trie Implementation (Insert, Search, StartsWith)

Hard · Data structures · Topics: trie, design

The problem

You're building the foundational autocomplete data structure for a search bar — before adding the advanced counting/deletion features from the previous problem, your team wants the bare-bones Trie: support inserting words, checking if an exact word exists, and checking if any inserted word starts with a given prefix. This is the canonical Trie interview question — almost every Trie-based problem you've solved so far builds on this exact foundation.

Function signature

class Trie {
public:
    Trie();
    void insert(string word);
    bool search(string word);       // exact match
    bool startsWith(string prefix); // prefix match
};

Test cases

Operations (in order)	Output / State
`insert("apple")`	"apple" added
`search("apple")`	`true`
`search("app")`	`false` ("app" was never explicitly inserted as a complete word)
`startsWith("app")`	`true` (some inserted word starts with "app")
`insert("app")`	"app" added
`search("app")`	`true` (now it's an exact match too)
`search("appl")`	`false`
`startsWith("appl")`	`true`
`startsWith("b")`	`false`
`search("")`	edge case — clarify expected behavior with interviewer

How interviewers phrase it

"Implement a Trie (prefix tree) with insert, search, and startsWith."
"Design a data structure that supports adding words and checking both exact existence and prefix existence efficiently."
This is LeetCode 208 — extremely common as either a standalone warm-up or as the first half of a larger Trie-based problem (word search, autocomplete, longest-word-with-prefixes, etc.). Interviewers expect this to be fast and clean, since it's foundational.

Clarifying questions to ask

What's the character set — lowercase English letters only (most common assumption), or broader (uppercase, digits, Unicode)? (Determines whether to use a fixed 26-element array or a hash map for children.)
Can insert be called with the same word multiple times? Does that matter for this basic version (no counting needed, just existence)?
Should I assume words are non-empty, or do I need to handle empty string inserts/searches as a valid edge case?
Is there a constraint on the number of operations or total characters, to gauge if performance optimization beyond the standard approach is needed? (Usually not necessary for this exact problem — O(L) per op is already optimal.)

Follow-ups to expect

"Why is array-based children (size 26) generally preferred over a hash map for this problem?"
"What's the time and space complexity of each operation?"
"How would you extend this to support deletion?"
"How would you support wildcard search (e.g., '.' matches any single character)?"
"Can you implement this iteratively vs. recursively, and does it matter here?"
"How would memory usage compare between a Trie and just using a hash set of all words for these same three operations?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview