Redact Document Phrases with Simultaneous Replacement
Company: Airbnb
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A document contains words or phrases that must be replaced using a supplied mapping. Perform all replacements against the original document so text inserted by one replacement is not processed again.
Implement `redact_document(text: string, phrases: string[], replacements: string[]) -> string`. The two arrays have equal length; `phrases[i]` maps to `replacements[i]`.
### Constraints & Assumptions
- Matching is case-sensitive and literal, including internal spaces.
- For this practice version, a match must have whole-word boundaries. Word characters are ASCII letters, digits, and underscore; the characters immediately before and after a match, if present, must not be word characters.
- Phrases are distinct, nonempty, and begin and end with a word character. Replacement strings may be empty and are inserted verbatim.
- Scan the original text left to right. At each position with one or more valid matches, choose the longest phrase, emit its replacement, and continue after the matched original span. Distinct phrases of equal length cannot both exactly match the same span.
- If no phrase matches at a position, preserve the original character.
- Boundary, overlap-priority, and simultaneous-replacement rules are explicit practice choices; the source gives the replacement-map task but does not specify these edge cases.
- All text is ASCII. Text length is at most 10,000, there are at most 100 phrases, and each phrase and replacement has at most 100 characters.
### Examples
```text
text = "Person One emailed Person."
phrases = ["Person","Person One"]
replacements = ["word","name"]
result = "name emailed word."
```
```text
text = "red redwood blue"
phrases = ["red","blue"]
replacements = ["blue",""]
result = "blue redwood "
```
The inserted `blue` is not redacted again, and `red` does not match inside `redwood`.
```hint Separate original positions from output
Advance through the input according to the length of the original matched phrase. Appending replacement text should not change which source characters are considered next.
```
Overview: Redact document phrases with a replacement map, whole-word matching, longest-match overlap rules, and one-pass replacement of original text.
Read the full Airbnb Machine Learning Engineer interview experience this question came from
A document contains words or phrases that must be replaced using a supplied mapping. Perform all replacements against the original document so text inserted by one replacement is not processed again.
Implement `redact_document(text: string, phrases: string[], replacements: string[]) -> string`. The two arrays have equal length; `phrases[i]` maps to `replacements[i]`.
### Constraints & Assumptions
- Matching is case-sensitive and literal, including internal spaces.
- For this practice version, a match must have whole-word boundaries. Word characters are ASCII letters, digits, and underscore; the characters immediately before and after a match, if present, must not be word characters.
- Phrases are distinct, nonempty, and begin and end with a word character. Replacement strings may be empty and are inserted verbatim.
- Scan the original text left to right. At each position with one or more valid matches, choose the longest phrase, emit its replacement, and continue after the matched original span. Distinct phrases of equal length cannot both exactly match the same span.
- If no phrase matches at a position, preserve the original character.
- Boundary, overlap-priority, and simultaneous-replacement rules are explicit practice choices; the source gives the replacement-map task but does not specify these edge cases.
- All text is ASCII. Text length is at most 10,000, there are at most 100 phrases, and each phrase and replacement has at most 100 characters.
### Examples
```text
text = "Person One emailed Person."
phrases = ["Person","Person One"]
replacements = ["word","name"]
result = "name emailed word."
```
```text
text = "red redwood blue"
phrases = ["red","blue"]
replacements = ["blue",""]
result = "blue redwood "
```
The inserted `blue` is not redacted again, and `red` does not match inside `redwood`.
```hint Separate original positions from output
Advance through the input according to the length of the original matched phrase. Appending replacement text should not change which source characters are considered next.
```
Constraints
- All text is ASCII. Text length is at most 10000; at most 100 distinct nonempty phrases, with equal-length replacement array.
- Each phrase and replacement has at most 100 characters; phrases begin and end with an ASCII word character and replacements may be empty.
- Word characters are ASCII letters, digits and underscore. Adjacent original characters before and after a match must not be word characters.
- Matching is literal and case-sensitive, including spaces. Choose the longest valid phrase at each original position, proceeding left to right.
- Insert replacements verbatim and never match inserted text again; preserve original characters with no match.
Examples
Input: ('Person One emailed Person.', ['Person', 'Person One'], ['word', 'name'])
Expected Output: 'name emailed word.'
Explanation: The longest valid source phrase wins before a shorter prefix.
Input: ('red redwood blue', ['red', 'blue'], ['blue', ''])
Expected Output: 'blue redwood '
Explanation: Inserted text is not processed again and substrings inside words do not match.