Medium

Google-styleMicrosoft-style

Prefix Lookup Service for a Word Dictionary DSA Interview

Given a dictionary of words, build a structure that can efficiently answer whether any dictionary word starts with a given prefix, and how many words share that prefix.

Mock Interview with AI

1. Problem Statement

You are given a dictionary of words. Build a structure supporting countWithPrefix(prefix), which returns how many dictionary words start with the given prefix. Multiple prefix queries will be made against the same dictionary.

2. Live Coding Format

Choose Python, JavaScript, Java, or C++, then solve while explaining your reasoning to the live interviewer.

Validation uses handwritten tests only. The MVP does not compile or run code, and it does not provide AI algorithm completion.

3. Key Focus Areas

1
Problem clarification and contract
2
Approach exploration and optimality
3
Think-aloud communication and pacing
4
Implementation correctness
5
Code quality and language fluency
6
Handwritten tests and dry run
7
Debugging and self-correction
8
Complexity analysis
9
Follow-up performance

4. What Strong Candidates Should Demonstrate

✓Clarify character set, duplicate words, and empty-prefix behavior before coding.
✓Explain a naive per-query full-scan baseline and improve to a trie with per-node word counts.
✓Think aloud while implementing careful trie construction and traversal.
✓Validate with explicit expected outputs and a top-to-bottom handwritten dry run.
✓Analyze time and space complexity and handle a bounded follow-up modification.

Evaluation Guide

This is an evaluation framework, not a single model answer. Strong designs may make different choices when their assumptions and trade-offs are explicit.

Problem clarification and contract

10%

Senior signals

✓Clarifies the character set (e.g., lowercase letters only), whether duplicate words in the dictionary count separately, and what an empty prefix should return.
✓Confirms that the dictionary is built once and then queried many times, motivating a preprocessing structure.

Staff-level signals

◆Asks about expected dictionary size and query volume to justify the chosen tradeoff.

Common red flags

×Codes immediately while assuming a single query only, without recognizing the repeated-query motivation.

Approach exploration and optimality

20%

Senior signals

✓Explains a naive baseline that scans every dictionary word for each query checking a prefix match, identifies the repeated linear-scan bottleneck across many queries, and improves to building a trie once, where each node tracks how many words pass through it.
✓Explains why annotating each trie node with a pass-through word count allows an O(prefix length) answer per query after the one-time build.

Staff-level signals

◆Discusses memory tradeoffs of a trie versus a sorted list with binary search for prefix range counting.

Common red flags

×Starts implementation without explaining an approach even after one interviewer prompt.

Think-aloud communication and pacing

10%

Senior signals

✓Explains the plan before coding and narrates trie node creation and count updates while implementing.
✓Paces the core solution to leave time for validation and the follow-up.

Common red flags

×Writes substantial code silently and cannot explain what the code is doing.

Implementation correctness

25%

Senior signals

✓Implements a correct trie build that inserts every word character by character, incrementing a pass-through count at each visited node, and a query that walks the prefix and returns the count at the final node (or zero if the path breaks early).
✓Handles an empty dictionary, an empty prefix (matches all words), duplicate words, and a prefix longer than any dictionary word.
✓Provides a convincing invariant argument for why the node count equals the number of words sharing that prefix.

Common red flags

×Returns a count based on exact-word matches only, ignoring words that extend beyond the queried prefix.
×Final code contains a material correctness bug that the candidate does not identify.

Code quality and language fluency

15%

Senior signals

✓Produces readable, language-appropriate code with a clear trie node structure, child mapping, and count field.

Common red flags

×Contains child-mapping errors or syntax-level incoherence that prevents credible reasoning.

Handwritten validation, dry run, and debugging

10%

Senior signals

✓Provides explicit inputs and expected outputs before tracing the code from top to bottom, drawing the trie structure for a small dictionary.
✓Covers an empty dictionary, empty prefix, duplicate words, and a prefix with no matches.
✓Finds and fixes an error independently, then re-validates the affected path.

Common red flags

×Claims the code works without a representative trace.

Complexity analysis and follow-up

10%

Senior signals

✓States build time proportional to total characters across all words, query time proportional to prefix length, and auxiliary space proportional to total distinct characters stored, comparing this with the naive per-query scan baseline.

Staff-level signals

◆Discusses the memory overhead of per-node child maps versus fixed-size arrays for a known small alphabet.

Common red flags

×Cannot state the complexity of the implemented solution.
×Fails a reasonable follow-up despite having at least five minutes and receiving bounded clarification.

Trade-offs to articulate

Scanning all words per query is simple to build but costs linear time in total dictionary size for every single query.
A trie with per-node counts costs one-time build effort proportional to total characters, but then answers each query in time proportional only to the prefix length.
A sorted word list with binary search for prefix range boundaries is a viable alternative, trading trie memory overhead for O(log n + range) query time.

Practice follow-up questions

1.Coding follow-up: extend the structure to also return one lexicographically smallest complete dictionary word that has the given prefix, in addition to the count.
2.Verbal extension: how would the approach change if words could be inserted into or removed from the dictionary between queries?

Want interactive feedback?

Practice this problem in the live coding workspace while the interviewer probes your clarification, algorithm, implementation, complexity, and handwritten tests.

Start Interview

Core Concepts

TriesStringsData Structure DesignComplexity Analysis