Debug Tokenization and Detokenization
Company: Anthropic
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: hard
Interview Round: Onsite
# Debug Tokenization and Detokenization
The source reports a debugging exercise with buggy tokenization and detokenization functions but does not include the exact code. The snippet and strict unknown-text policy below are a practice reconstruction. Preserve both public signatures and their ID-only return/input types.
```python
def tokenize(text, vocabulary):
out = []
i = 0
while i < len(text):
for token, token_id in vocabulary.items():
if text.startswith(token, i):
out.append(token_id)
i += len(token)
break
else:
i += 1
return out
def detokenize(ids, vocabulary):
inverse = {token_id: token for token, token_id in vocabulary.items()}
return "".join(inverse[token_id] for token_id in ids)
```
Repair the functions under this contract:
- `vocabulary` maps nonempty token strings to unique integer IDs. Reject an empty token or duplicate ID with `ValueError`.
- `tokenize` uses longest-prefix matching at every position. Because dictionary keys are unique, no separate equal-length tie is possible.
- The public stream contains IDs only. Therefore arbitrary unknown text cannot be reconstructed. Preserve the interface by raising `ValueError` at the first position with no matching token instead of dropping text or adding a payload type.
- `detokenize` raises `ValueError` for an ID not present in the validated vocabulary.
- Empty text maps to `[]`, and detokenizing `[]` returns `""`.
For every text accepted by the longest-match tokenizer, `detokenize(tokenize(text, vocabulary), vocabulary)` must equal the original text.
### Clarifying Questions to Ask
- Must the ID-only public interface remain unchanged?
- Is exact round-trip behavior required for unknown input, or may unknown text be rejected?
- Are empty tokens or duplicate IDs valid vocabulary data?
- How large are the vocabulary and maximum token length?
### What a Strong Answer Covers
- The iteration-order bug, silent unknown-character loss, and duplicate-ID inversion bug.
- A deterministic repair that preserves `list[int]` and the original function signatures.
- An explicit explanation of why exact arbitrary-unknown round trips are impossible with IDs alone.
- Focused tests for overlapping tokens, unknown input, duplicate IDs, empty tokens, empty input, and unknown IDs.
- Baseline and trie-based complexity.
### Follow-up Questions
1. What interface change would support lossless arbitrary unknown substrings?
2. How would a trie change construction cost and per-character work?
3. How would byte-level tokenization change the Unicode contract?
Quick Answer: Debug Python tokenization and detokenization functions while preserving their ID-only public interface. Repair iteration-order matching, reject unknown text instead of silently dropping it, validate duplicate IDs and empty tokens, and guarantee exact round trips for accepted input.