FastPrepLongest Dictionary Tokenization
Problems/Longest Dictionary Tokenization

Longest Dictionary Tokenization

Google logoGoogle● MediumFULLTIMENEW GRADPHONE SCREEN

Updated Oct 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The source gives the longest-match tokenizer and directly clarifies the follow-up with tokens abcd, abc, and ab: when ab has the highest priority, ab must win. It omits numeric priority direction, tie order, bounds, and the portable function signature; this practice uses higher integers first, then longer tokens, then earlier dictionary order. The judged core matches the visible source at about 90%.

You are given a text string, a dictionary of token-to-id mappings, and one integer priority for each dictionary entry. Starting at the beginning of text, repeatedly choose among all dictionary tokens that match the current position.

Choose the matching entry with the highest priority. If several entries have the same priority, choose the longest token. If priority and token length both tie, choose the earliest dictionary entry. Emit the chosen entry's id and advance by its token length. If no dictionary token matches, emit the current character itself and advance by one character.

Return the sequence of emitted ids and literal characters. When all priorities are equal, this is the original longest-match tokenizer.

Function

encodeWithDictionary(text: String, dictionary: String[][], priorities: int[]) → String[]

Examples

Example 1

text = "applepie"dictionary = [["app","B"],["apple","A"],["pie","P"]]priorities = [0,0,0]return = ["A","P"]

All priorities tie, so apple is preferred over app by token length.

Example 2

text = "xabcd"dictionary = [["ab","1"],["abc","2"],["bc","3"]]priorities = [0,0,0]return = ["x","2","d"]

The first character has no match. At index 1, abc wins the equal-priority tie because it is longer than ab.

Example 3

text = "abcdx"dictionary = [["abcd","4"],["abc","3"],["ab","2"]]priorities = [1,5,10]return = ["2","c","d","x"]

ab has the highest priority, so it overrides the longer matching tokens. The remaining characters have no matches and are emitted literally.

Constraints

  • 1 <= text.length <= 100000; text and every token contain lowercase English letters.
  • 1 <= dictionary.length == priorities.length <= 10000.
  • Each dictionary entry is [token, id]; tokens are nonempty and ids are nonempty printable ASCII strings of length at most 100.
  • The total length of all dictionary tokens is at most 100000.
  • -1000000000 <= priorities[i] <= 1000000000.
  • The total length of all returned strings is at most 1000000.

More Google Phone Screen questions

  • Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
  • Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
  • Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Logger Rate Limiter with Every-Arrival HistoryPHONE SCREEN · Seen Nov 2026
  • Minimum Total Layover WaitPHONE SCREEN · Seen Nov 2026
  • Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026

Similar questions at other companies

  • Longest-Match Tokenizer with Unknown SymbolsAnthropic · ONSITE INTERVIEWAnthropic interview questions
  • Remove K DigitsProcol · PHONE SCREEN
  • Reorderable Task Scheduler With CooldownWaymo · PHONE SCREENWaymo interview questions
  • Reorganize a StringAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Valid Parenthesis StringOracle · PHONE SCREENOracle interview questions
  • Shortest Way to Form a Target StringPinterest · PHONE SCREENPinterest interview questions
  • Maximize Workday EarningsCitadel · OA · PHONE SCREEN · ONSITE INTERVIEWCitadel interview questions
  • Minimum Removal for Balanced ParenthesesMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
  • Largest Number Below N from Reusable DigitsByteDance · PHONE SCREENByteDance interview questions
  • Biggest Number From Gluing Numbers TogetherAdobe · PHONE SCREENAdobe interview questions

Interview reports that mention this question

  • Google New Grad R1, Dictionary Tokenization: 1 Experience

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public String[] encodeWithDictionary(String text, String[][] dictionary, int[] priorities) {
        // write your code here
    }
}
Checking account…