Trie Searches, XOR Tries & Interview Day

Tries & Bit Manipulation, lesson 3 of 3

Trie Searches, XOR Tries & Interview Day

Wildcard and grid searches over a trie, a binary trie for max XOR, and your interview checklist.

14 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Wildcards. Suppose . matches any single letter. Walking the trie still works: on a normal letter you follow one child; on a dot you try every child and succeed if any branch does. That is a DFS over the trie, indexed by position in the pattern.

Worst case is O(26^d · L) for d dots, but real patterns prune fast because most branches die within a letter or two.

Example

Wildcard search

b. is False: the path b-a exists, but no word ends there. The end check at i == len(word) is what makes length matter.

Many words on a grid. "Find every dictionary word you can trace on this letter board." Brute force runs a separate grid DFS for each word: O(W · cells · 4^L).

With a trie you do one DFS from each cell and walk the trie in lockstep. The moment the letters so far aren't a prefix of any word, you stop. Every word sharing that prefix is checked by the same walk.

Tricks that make it fast and correct:

  • store the whole word at its end node (node["$"] = word) so you don't rebuild strings
  • pop it when found, so a word found twice is reported once
  • mark the cell as visited by overwriting it with "#", and restore it on the way back
  • optionally delete trie nodes that become empty, so later searches skip finished branches
Example

Trie + grid DFS

"#" is never a key in the trie, so a visited cell automatically fails the in node check. That is the whole "visited set".

Quiz

Why does a trie make the board word search so much faster than a set of words?

Tries meet bits: the binary trie. Insert numbers as bit strings, highest bit first; each node has at most two children, 0 and 1.

To find the number in the trie that maximises q ^ x, walk from the top bit and greedily take the opposite bit of q whenever that child exists. A 1 in a higher bit beats everything below it combined, so greedy is optimal.

q = 010 → want 1, then 0, then 1
stored: 011, 100
top bit: want 1 → go to 1 (100 branch)
result: 010 ^ 100 = 110 = 6
Example

Best XOR partner for a query

Each query costs O(BITS), so the best pair over n numbers costs O(n · BITS) instead of O(n²). That is "Maximum XOR of Two Numbers" in a nutshell.

Quiz

A binary trie holds 3 (011) and 4 (100). Which stored number does the greedy walk pick for q = 2 (010)?

Exercise

Count wildcard matches

Write count_matches(words, pattern): build a trie from the (distinct) words, then return how many of them match pattern, where . matches any one letter. Lengths must match exactly.

count_matches(["bad", "dad", "mad", "ba"], ".ad") is 3.

Where to go next

You've now met every major interview pattern. To make them stick:

  • Re-solve, don't re-read. Redo problems you needed hints for, a few days later, without hints.
  • Mix patterns. Pick problems at random so you practise recognising the pattern, not just applying the one you just studied. The cheatsheets' "when to use" lists are your recognition drills.
  • Time yourself. Aim for a medium in about 20–25 minutes including tests.
  • Going further: union-find, segment and Fenwick trees, string hashing and KMP, and harder DP (on intervals, trees and bitmasks).

Interview day checklist

  1. Restate the problem and ask about input size, empty input, duplicates and negatives.
  2. Work an example by hand before any code.
  3. Say the brute force and its complexity out loud. It is a valid starting point.
  4. Name the pattern that beats it, and why the signals point to it.
  5. Code it cleanly with clear names, talking as you go.
  6. Test with your example, then edge cases: empty, one element, all the same, extremes.
  7. State the final time and space complexity and any trade-offs.