Problem context and objectives
Mission briefing
Rune decoder · Thousands of spells share the same opening symbols
Reuse shared prefixes to complete the requested spell: The Glyph Index.
Checking every full spell makes each keystroke feel slow.
How you win
- 1Recognize when Trie construction and lookup matches the clues
- 2Keep this true after every move: the current node represents exactly the characters consumed from the query
- 3Reach the result within O(total inserted characters + total queried characters)
Rules and pressure
- Target cost: O(total inserted characters + total queried characters)
- State rule: the current node represents exactly the characters consumed from the query
Lesson 1 of 3
Live algorithm trace
Trie construction and lookup
Complete execution1 of 7
app
word
apple
apt
bat
Create one root node before inserting any word.
1
root = empty node2
for each word3
walk or create one child per character4
mark the final node as a word5
for each query, walk its characters6
search also requires an end marker7
prefix only requires a complete walknodes = 1root = empty prefix
Truth to preserve / Cost target
Truth to preserve
the current node represents exactly the characters consumed from the query
Cost target
O(total inserted characters + total queried characters)
A trie stores one character per edge. Words with a shared prefix reuse the same path, while an end marker distinguishes a complete word from a prefix that merely leads farther.
Your call · What should guide every step of this algorithm?