Implement a BPE Tokenizer
On this page
Problem statement
Implement Byte Pair Encoding (BPE). Write
train_bpe(word_counts, num_merges)that takes a dictionary of words and their frequencies and returns the ordered list of learned merges, where each merge joins the most frequent adjacent pair of symbols. Then writeencode(word, merges)that splits a new word into tokens using those merges.
A classic ML coding question for LLM roles: small enough for 45 minutes, and it shows whether you understand how tokenizers really work (see Tokens and Tokenization).
Example

corpus = {"low": 5, "lower": 2, "lowest": 3, "newest": 6, "widest": 3}
merges = [('s','t'), ('e','st'), ('o','w'), ('l','ow'), ('w','est'), ('n','e')]
encode("lowest") → ['low', 'est']
encode("newer") → ['ne', 'w', 'e', 'r']
encode("slow") → ['s', 'low']
Constraints (assumed)
- Up to about 100,000 distinct words; a few thousand merges in the interview version.
- Characters as base symbols (byte-level is a follow-up).
- Words are already split on whitespace; no special tokens.
What this question tests
- Translating the algorithm into clean data structures (tuples, counters, ranks).
- Weighting pair counts by word frequency.
- Deterministic tie-breaking, so training is reproducible.
- Encoding consistently with training (merge order).
Questions to ask first
- Characters or bytes as the base alphabet? (Characters here.)
- Is there an end-of-word marker? (Not here; it changes how suffixes merge.)
- How should ties be broken? (Any deterministic rule; state it.)
- Do I need decoding (ids back to text)? (Concatenating tokens is enough here.)
- Is efficiency important, or clarity first? (Clarity, then discuss speed-ups.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.