Coding interviews
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
var trie = new Trie(); foreach (string word in new[] { "car", "cart", "cat", "car" }) trie.Add(word);
Console.WriteLine("ca prefix:" + trie.Prefix("ca").ToString().ToLowerInvariant());
Console.WriteLine("ca word:" + trie.Contains("ca").ToString().ToLowerInvariant());
Console.WriteLine("car word:" + trie.Contains("car").ToString().ToLowerInvariant());
Console.WriteLine("empty prefix:" + trie.Prefix("").ToString().ToLowerInvariant());
sealed class Trie {
private readonly Node root = new();
public void Add(string word) { Node n=root; foreach(char c in word) { if(!n.Children.TryGetValue(c,out var next)) n.Children[c]=next=new Node(); n=next; } n.Word=true; }
private Node? Find(string text) { Node n=root; foreach(char c in text) { if(!n.Children.TryGetValue(c,out var next)) return null; n=next; } return n; }
public bool Prefix(string text) => Find(text) is not null;
public bool Contains(string text) => Find(text)?.Word == true;
private sealed class Node { public Dictionary<char,Node> Children { get; } = new(); public bool Word; }
}
Reveal answer and reasoning
The output lines, in order, are “ca prefix:true”; “ca word:false”; “car word:true”; “empty prefix:true”. Inserting car creates c,a,r; cart reuses that path and adds t. Cat shares c,a and adds another branch. Re-inserting car leaves its terminal flag true. The path for ca exists but its node is not terminal, while car is terminal. Finding an empty prefix returns the root, even though no empty word was inserted.
After car and cart are inserted, the r node is terminal and has a t child. Neither fact cancels the other. The shared c,a path branches at r and t for car and cat. Repeated car insertion changes no counts because this implementation stores membership rather than occurrence frequency.
For m code units, insertion and lookup take expected O(m) dictionary work, with O(total distinct prefix nodes) retained space. A node can allocate a child dictionary even before many children exist. A fixed alphabet array trades lookup characteristics for potentially much larger sparse storage. Assuming every reached node is a word makes prefix queries accidentally satisfy exact-word checks. Treating char as a user-perceived character changes Unicode semantics.
Suggestions also require a separate ordering and result-limit contract; this trie intentionally exposes only existence checks, not a ranked autocomplete system.
What a strong answer covers
- Exact output: ca prefix:true | ca word:false | car word:true | empty prefix:true
- Inserting car creates c,a,r; cart reuses that path and adds t.
- Assuming every reached node is a word makes prefix queries accidentally satisfy exact-word checks.
Common pitfall
Assuming every reached node is a word makes prefix queries accidentally satisfy exact-word checks. Treating char as a user-perceived character changes Unicode semantics. Suggestions also require a separate ordering and result-limit contract; this trie intentionally exposes only existence checks, not a ranked autocomplete system.
Follow-up questions
- Insert the empty word and verify that Contains empty changes while Prefix empty remains true. Hint: there is no character edge to create, so the operation modifies the root. Add a mixed-case word to verify exact matching.
- When deleting car, which nodes must remain to preserve cart and cat?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.