Streaming

What is this?

Characters arrive one at a time, forever, and after each one you must answer: does any dictionary word end right here? That is a question about suffixes of everything seen so far — and a trie is built for prefixes. Re-scanning the recent history against every word on every character is far too slow.

The fix is to change the data rather than the structure. Store the words backwards. Now walking the recent characters in reverse order through the trie answers the suffix question with an ordinary prefix walk.

💡 Fun fact: the walk is bounded by the longest dictionary word, not by the length of the stream. As soon as the reversed walk reaches a node with no matching child, no longer suffix can match either — because every longer candidate would have to pass through that node. So a stream of a billion characters still costs at most L steps per arrival, and the history buffer can be truncated to L characters and forgotten beyond that.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: a trie answers prefix questions, and reversing the dictionary turns "does a word end here?" into exactly that. The walk terminates the moment no child matches, so the cost is bounded by the longest word rather than the stream.

1. The implementation

class StreamChecker:
    def __init__(self, words):
        self.root = Node()
        self.max_len = max(map(len, words))
        for w in words:
            node = self.root
            for ch in reversed(w):                  # store backwards
                node = node.children.setdefault(ch, Node())
            node.is_end = True
        self.history = deque()

    def query(self, letter):
        self.history.appendleft(letter)             # newest first
        if len(self.history) > self.max_len:
            self.history.pop()                      # forget what can never matter
        node = self.root
        for ch in self.history:                     # newest → oldest
            if ch not in node.children:
                return False                        # no longer suffix can match
            node = node.children[ch]
            if node.is_end:
                return True
        return False

Two decisions carry the whole solution. appendleft keeps the newest character at the front, so iterating the deque naturally walks backwards through the stream. And the early return on a missing child is what bounds the work — it is not an optimisation, it is the correctness argument for why the cost does not grow with the stream.

Capping the history at max_len is the memory counterpart: characters older than the longest word can never participate in a match.

2. A 30-second worked example

Dictionary ["cd", "f", "kl"], stored reversed as dc, f, lk. Stream: a, b, c, d.

query 'a'  history = [a]
           root has no 'a' child → False

query 'b'  history = [b, a]
           root has no 'b' child → False

query 'c'  history = [c, b, a]
           root has no 'c' child → False        ← 'c' only appears INSIDE "dc"

query 'd'  history = [d, c, b, a]
           root → 'd' ✓ (not is_end)
                → 'c' ✓ is_end → True          ← "cd" ends here ✅

The third query is the instructive one: c alone is not a word, and the reversed trie's root has no c edge because cd reversed starts with d. Only when the d arrives does the backwards walk d → c spell a stored word.

3. Where you'll actually meet this

• Content moderation. Matching an inbound message stream against a blocklist without re-scanning history.
• Intrusion detection. Signature matching over network traffic as packets arrive.
• Log monitoring. Triggering when a known error pattern completes in a live log tail.
• Voice and text input. Detecting wake words or command phrases in a continuous stream.
• Protocol parsing. Recognising terminator sequences in a byte stream, where you never get to look ahead.

4. Problems in this chapter

▶ Stream of Characters

Report, after each arriving character, whether any dictionary word ends there. Reversed trie, bounded history, backwards walk.
Pattern: reversed trie over a stream. Target: O(L) per query, O(L) memory for the history.

5. Common pitfalls 🚫

• Storing the words forwards. Then each query needs every possible start position — quadratic and unnecessary.
• Appending to the end of the history and iterating forwards. The walk must go newest to oldest; appendleft makes that natural.
• Never trimming the history. Memory grows without bound for no benefit; anything older than the longest word is dead.
• Continuing after a missing child. The early exit is the reason the cost is bounded — removing it does not just slow things down, it obscures why the solution is correct.
• Checking is_end only at the end of the walk. A match can occur at any depth, so test after every step.
• Assuming the alphabet is lowercase-only without saying so; a dictionary per node keeps it general.
• Rebuilding the trie per query. It is built once in the constructor.

6. Key takeaways

1. Reverse the data to reverse the question. Suffix matching becomes prefix matching with no change to the structure.
2. Keep the newest character first so the natural iteration order is the backwards walk.
3. Stop at the first missing child — that bound is what makes the solution scale.
4. Trim the history to the longest word. Older characters can never matter.
5. Test is_end at every depth, not only at the end.
6. Cost is bounded by the dictionary, not the stream — the sentence to say out loud.
7. Why interviewers like it: the naive solution is obvious and quadratic, and the fix is a single reframing rather than a new data structure, which makes it a clean test of insight over recall.

Order: Stream of Characters.