How should I practice Longest-Match Tokenizer with Unknown Symbols?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Anthropic onsite interview problems in FastPrep.

Is Longest-Match Tokenizer with Unknown Symbols associated with Anthropic?

FastPrep tags this as a Anthropic onsite interview coding practice problem when the problem catalog has that company and stage context.

Longest-Match Tokenizer with Unknown Symbols

Anthropic● MediumFULLTIMEONSITE INTERVIEW

Problem statement

A vocabulary maps each nonempty string in vocabulary to the integer at the same position in ids. Implement both independent directions in tokenCodec.

Encode the text

For this exercise, assume encoding scans text from left to right. At the current position, choose the longest complete vocabulary string that matches there, append its ID, and advance by its entire length. If no complete vocabulary string matches, append -1 and consume exactly one character. A partial vocabulary prefix at the end is not a match. Continue until every text character has been consumed.

This is greedy longest-prefix matching at each position. It does not search for a globally minimum token count. The vocabulary and IDs stay unchanged. Strings are case-sensitive; spaces and punctuation are ordinary characters.

Decode the supplied tokens

Independently decode tokens by concatenating the vocabulary string for each known ID. Every -1 contributes the literal string <UNK>. Input tokens are guaranteed to be known IDs or -1. The supplied tokens need not equal the encoding of text.

Return exactly two strings: first the encoded integer list in compact JSON form, such as [7,-1,2], with commas and no spaces; second the decoded text. Empty encoding is []; empty decoding is the empty string.

For this exercise, assume -1 is a reserved unknown ID outside the vocabulary mapping. Ordinary vocabulary entries such as UNK are not special. Unknown encoding is deliberately lossy: it retains one unknown marker per uncovered character, not that character's original value. Decoding an encoded unknown therefore produces <UNK>, so exact round-trip recovery is not promised.

Function

tokenCodec(vocabulary: String[], ids: int[], text: String, tokens: int[]) → String[]

Examples

Example 1

vocabulary = ["a","b","cd"]ids = [1,2,3]text = "acdebe"tokens = [1,3,-1,2,-1]return = ["[1,3,-1,2,-1]","acd<UNK>b<UNK>"]

Encoding selects a, cd, one unknown e, b, and one unknown e, producing [1,3,-1,2,-1]. Decoding the supplied list produces acd<UNK>b<UNK>; the unknown letters are not recoverable.

Example 2

vocabulary = ["a","abc","bcd"]ids = [4,8,6]text = "abcd"tokens = [4,6]return = ["[8,-1]","abcd"]

At position0, abc is the longest match, so encoding is [8,-1]. The alternative a followed by bcd is not chosen by this greedy rule. The independent decode input[4,6]produces abcd.

Example 3

vocabulary = ["abcd","b"]ids = [10,20]text = "ab"tokens = [-1,20]return = ["[-1,20]","<UNK>b"]

abcd is only a partial prefix of the remaining text, so a consumes one unknown position. b then matches20, giving [-1,20]. Decoding gives <UNK>b.

Constraints

0 <= vocabulary.length <= 100.
ids.length == vocabulary.length.
Each vocabulary string has between 1 and 20 characters.
0 <= ids[i] <= 1000000.
Vocabulary strings are pairwise distinct, and IDs are pairwise distinct.
0 <= text.length <= 2000.
0 <= tokens.length <= 2000.
-1 <= tokens[i] <= 1000000, and every supplied token is -1 or an ID in ids.
Every text and vocabulary character is printable ASCII with code from 32 through 126.