PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches
|Home/Coding & Algorithms/Google

Implement Longest-Match Text Replacement

Last updated: May 19, 2026

Quick Overview

This question evaluates string processing, pattern matching, greedy algorithm reasoning, and data structure design for efficient longest-prefix token replacement, and is categorized under Coding & Algorithms.

  • hard
  • Google
  • Coding & Algorithms
  • Software Engineer

Implement Longest-Match Text Replacement

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a text string and a dictionary of replacement entries. Each dictionary entry has the form `token:id`, where `token` is a string pattern and `id` is the value that should be emitted when that token is matched. Implement a function that scans the text from left to right and produces an output sequence using greedy longest-prefix matching: 1. At the current text position, find all dictionary tokens that match the substring starting at that position. 2. If at least one token matches, choose the longest matching token, append its corresponding `id` to the output, and advance by the length of that token. 3. If no token matches, append the original character at the current position to the output and advance by one character. 4. Continue until the entire text has been processed. Example: ```text text = "abcdxyz" dictionary = { "ab": "1", "abc": "2", "xy": "3" } ``` Output: ```text ["2", "d", "3", "z"] ``` Explanation: At index `0`, both `"ab"` and `"abc"` match, so choose the longest token `"abc"` and output `"2"`. Then `"d"` has no match, so output it literally. Then `"xy"` matches and outputs `"3"`. Finally, `"z"` is output literally. Follow-up: How would you adapt your design if the matching priority changed from longest match to a configurable priority rule, such as dictionary insertion order, highest score, or a custom comparator?

Quick Answer: This question evaluates string processing, pattern matching, greedy algorithm reasoning, and data structure design for efficient longest-prefix token replacement, and is categorized under Coding & Algorithms.

Related Interview Questions

  • Solve Flower Placement and Directory Deletion - Google (medium)
  • Compute Turnstile Crossing Times - Google (hard)
  • Simulate In-Place Cellular State Updates - Google (hard)
  • Determine Whether a Word Exists in a Graph - Google (medium)
  • Implement Checksums and Feature Rollout Evaluation - Google (medium)
Google logo
Google
Jan 20, 2026, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
0
0

You are given a text string and a dictionary of replacement entries. Each dictionary entry has the form token:id, where token is a string pattern and id is the value that should be emitted when that token is matched.

Implement a function that scans the text from left to right and produces an output sequence using greedy longest-prefix matching:

  1. At the current text position, find all dictionary tokens that match the substring starting at that position.
  2. If at least one token matches, choose the longest matching token, append its corresponding id to the output, and advance by the length of that token.
  3. If no token matches, append the original character at the current position to the output and advance by one character.
  4. Continue until the entire text has been processed.

Example:

text = "abcdxyz"
dictionary = {
  "ab": "1",
  "abc": "2",
  "xy": "3"
}

Output:

["2", "d", "3", "z"]

Explanation: At index 0, both "ab" and "abc" match, so choose the longest token "abc" and output "2". Then "d" has no match, so output it literally. Then "xy" matches and outputs "3". Finally, "z" is output literally.

Follow-up: How would you adapt your design if the matching priority changed from longest match to a configurable priority rule, such as dictionary insertion order, highest score, or a custom comparator?

Comments (0)

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Google•More Software Engineer•Google Software Engineer•Google Coding & Algorithms•Software Engineer Coding & Algorithms
PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.