How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Anthropic.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Anthropic during technical interviews.

Implement an extensible prefix tree | Anthropic Coding Question

Quick Overview

This question evaluates the ability to design and implement an extensible prefix tree (trie), covering competencies in Unicode-aware string handling, memory and time optimization, concurrency or thread-safety considerations, and support for operations like insert, search, startsWith, countPrefix and erase.

Implement an extensible prefix tree

Company: Anthropic

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement a prefix tree (trie) supporting insert(word), search(word), startsWith(prefix), countPrefix(prefix), and erase(word). Optimize for time and memory; handle Unicode characters; and ensure thread-safety or document assumptions. Provide Big-O complexity for each operation, outline test cases (including edge cases like duplicates and deletions of non-existent words), and discuss trade-offs versus alternative data structures.

Quick Answer: This question evaluates the ability to design and implement an extensible prefix tree (trie), covering competencies in Unicode-aware string handling, memory and time optimization, concurrency or thread-safety considerations, and support for operations like insert, search, startsWith, countPrefix and erase.

Process a sequence of operations on one Unicode-aware trie: insert(word), search(word), startsWith(prefix), countPrefix(prefix), and erase(word). Duplicates are allowed, so inserting the same word multiple times increases its multiplicity, countPrefix counts duplicates, and erase removes only one occurrence, returning False if the word is absent. startsWith should return whether at least one currently stored word begins with the prefix. Design the trie to support efficient prefix queries, safe deletions, and pruning of unused nodes for memory efficiency. Expected per-operation complexity: insert O(L) time and up to O(L) new space, search O(L), startsWith O(L), countPrefix O(L), and erase O(L), where L is the length of the word or prefix. The reference approach stores only existing children, uses pass and end counters, handles Unicode naturally via Python strings, and wraps each public operation with a lock for thread-safety. Compared with a hash set, a trie uses more memory but supports prefix operations efficiently; compared with a sorted list, it avoids O(n) inserts and deletes but has higher constant factors.

Constraints

1 <= len(operations) == len(arguments) <= 2 * 10^5
Each operations[i] is one of insert, search, startsWith, countPrefix, or erase
0 <= len(arguments[i]) <= 10^3
The sum of all argument lengths is at most 2 * 10^5
Arguments may contain arbitrary Unicode characters, and duplicate words are allowed

Examples

Input: (['insert','insert','search','search','startsWith','countPrefix','erase','search','countPrefix','startsWith'], ['apple','app','apple','ap','ap','app','apple','apple','app','apple'])

Expected Output: [None, None, True, False, True, 2, True, False, 1, False]

Input: (['insert','insert','countPrefix','search','erase','search','countPrefix','erase','search','erase'], ['cat','cat','ca','cat','cat','cat','ca','cat','cat','cat'])

Expected Output: [None, None, 2, True, True, True, 1, True, False, False]

Hints

Store two counters at each node: how many words pass through the node and how many words end there. This makes duplicates and countPrefix easy to support.
During erase, record the path from the root to the terminal node. After decrementing counts, walk backward and delete child links whose pass count becomes zero.