Software Engineer · Phone Screen · Coding

Anthropic — Software Engineer

Level: Senior-Level

Round: Phone Screen · Type: Coding · Difficulty: 6/10 · Duration: 60 min · Interviewer: Unfriendly

Topics: Trie, String Processing, Greedy Algorithm

Location: Mountain View, CA

Interview date: 2026-01-15

Summary

I was asked to implement a greedy string tokenization algorithm. Given a text string and a dictionary of tokens with their IDs, I needed to tokenize the text by scanning left to right, always choosing the longest matching token from the dictionary at each position. If no token matched, I had to output the single character as a literal token.

Details

The coding question I got was:

text = "applepiepear" dictionary = ["app:10", "apple:20", "pie:30"]

My task was to tokenize the input string into a sequence of outputs by scanning from left to right and applying a greedy longest-match strategy.

Tokenization Rules:

1. Maximum-Length Matching: At any index in text, consider all dictionary tokens that begin at that position. If multiple tokens match, always choose the one with the greatest length.

2. Greedy Advancement: After selecting a token, consume all of its characters and continue processing from the next position after the match.

3. Fallback to Literals: If no token matches at the current index, output the single character at that position as a literal token and move forward by one character.

4. Output Representation:

   • If a substring matches a dictionary token, output its corresponding id (as a string)
   • Otherwise, output the literal character itself

My approach:

1. I built a Trie data structure from the dictionary of tokens.
2. I scanned the input text string from left to right.
3. At each position, I used the Trie to find the longest matching token starting at that position.
4. If a match was found, I output the token's ID and advanced the scanner by the length of the token.
5. If no match was found, I output the character at the current position as a literal and advanced the scanner by one character.

`python from typing import List, Optional

class Trie: def init(self): self.children = {} self.id = None

class Solution: def tokenize(self, text: str, dictionary: List[str]) -> List[str]: root = self.buildTrie(dictionary) result = []

    i = 0
    while i < len(text):
        # Try to find longest match starting at position i
        node = root
        bestId = None
        bestEnd = i

        j = i
        while j < len(text):
            c = text[j]
            if c not in node.children:
                break
            node = node.children[c]
            j = j + 1

            # Track the last terminal node we've seen
            if node.id is not None:
                bestId = node.id
                bestEnd = j

        if bestId is not None:
            result.append(bestId)
            i = bestEnd
        else:
            # No match found, emit literal character
            result.append(str(text[i]))
            i = i + 1

    return result

def buildTrie(self, dictionary: List[str]) -> Trie:
    root = Trie()

    for entry in dictionary:
        colonIndex = entry.find(':')
        if colonIndex == -1:
            continue

        key = entry[:colonIndex]
        val = entry[colonIndex + 1:]

        node = root
        for i in range(len(key)):
            c = key[i]
            if c not in node.children:
                node.children[c] = Trie()
            node = node.children[c]
        # Last wins if duplicate keys
        node.id = val

    return root

`

Key insights:

• Using a Trie is essential for efficient longest-prefix matching.
• Handling overlapping tokens correctly is crucial for deterministic behavior.
• The greedy approach ensures that we always select the longest possible match at each step.