Highlight categorized phrases in a review: Frontier Interview's solution

Question: Highlight categorized phrases in a review

Companies: Airbnb

Difficulty: Hard

Problem statement

Reviews on a travel site should show key phrases with their category. Write a function that marks every mapped phrase in a review.

def highlight(review: str, mapping: list[tuple[str, str]]) -> str: ...

mapping is a list of (phrase, category) pairs. Return the review with each matched span replaced by [category]{matched_text}, where matched_text is the text exactly as it appears in the review.

Rules

Whole words only. Letters and digits are word characters; everything else, and the ends of the string, are boundaries. A match must start at the start of a word and end at the end of a word. For example, "pool" matches in "pool!" but not in "pools" or "carpool".
Case-insensitive. "wifi" matches "WiFi", and the output keeps WiFi.
Phrases can span words. "ocean view" matches "Ocean view". Spaces and punctuation inside a phrase must match exactly.
Longest match, left to right, no overlaps. Scan from the left. Where several phrases start at the same place, use the longest one. After a match, continue after it.
If the same phrase appears more than once in mapping, use the first category listed. Ignore empty phrases.

Constraints: review length up to 10^5; up to 10^4 phrases, each up to 100 characters.

Example 1

review  = "Great Ocean View, but the pool was cold."
mapping = [("ocean view", "scenery"), ("ocean", "nature"), ("pool", "amenity")]
output  = "Great [scenery]{Ocean View}, but the [amenity]{pool} was cold."

Example 2

review  = "Ocean breeze, no pools, carpool only."
mapping = [("ocean view", "scenery"), ("ocean", "nature"), ("pool", "amenity")]
output  = "[nature]{Ocean} breeze, no pools, carpool only."

"ocean view" does not fit, so the shorter "ocean" is used. "pools" and "carpool" are not whole-word matches.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

The output is the review with some spans wrapped. So the job is to pick which spans get wrapped, then rebuild the string once. Three rules decide the spans, and you should say them out loud before you code:

Whole words only. A match must start where a word starts and end where a word ends. A "word character" is a letter or a digit; anything else (space, punctuation, hyphen, end of string) is a boundary. "san" matches in "san?" but not in "sandbox" or "xsan".
Case-insensitive match, original text kept. "wifi" matches "WiFi", and the output shows WiFi, not the phrase from the mapping.
Longest match wins, scanning left to right, no overlaps. At a given start, if both "golden gate" and "golden gate bridge" fit, take the longer one. Once a span is wrapped, scanning continues after it, so wrapped spans never overlap or nest.

Ask about duplicates: if one phrase appears twice with different categories, pick a rule. This solution keeps the first one listed.

Brute force. Walk the review. At each word start, try every phrase: compare it to the text there (ignoring case) and check that the next character is a boundary. Keep the longest phrase that fits. That is O(n · P · L) for review length n, P phrases and phrase length L. It is correct and a fine first answer, but every word start re-reads every phrase.

Optimal: a trie over the phrases. Insert each phrase, lowercased, one character per edge. Mark the node where a phrase ends with its category. Then scan the review:

At a word start i, walk down the trie with review[i], review[i+1], ... (lowercased). Each time you reach a marked node and the next review character is a boundary, record that end as the best so far. Stop when the trie has no child for the next character.
If a best end exists, emit [category]{review[i:end]} and jump to end.
If not, copy the whole word and jump past it. This matters: without the jump you would try a match at "s" inside "xsan".
At a non-word character, copy it and move on.

One trie walk finds every phrase that starts at i, so you get the longest one in a single pass instead of P comparisons. Phrases that contain spaces or punctuation ("san francisco", "pet-friendly") need no special code: they are just characters in the trie. The separators must match exactly, so "pet-friendly" does not match "pet friendly".

Invariants.

i only ever points at a word start or at a non-word character, never at the middle of a word.
Every character of the review is copied to the output exactly once, either inside a wrapped span or on its own.
A wrapped span always starts at a word start and ends at a word end.

Code

from typing import Dict, List, Optional, Tuple


class _Node:
    __slots__ = ("children", "category")

    def __init__(self) -> None:
        self.children: Dict[str, "_Node"] = {}
        self.category: Optional[str] = None  # set when a phrase ends here


def _is_word_char(ch: str) -> bool:
    return ch.isalnum()


def build_trie(mapping: List[Tuple[str, str]]) -> _Node:
    root = _Node()
    for phrase, category in mapping:
        if not phrase:
            continue  # an empty phrase would match everywhere
        node = root
        for ch in phrase.lower():
            node = node.children.setdefault(ch, _Node())
        if node.category is None:  # first mapping for a phrase wins
            node.category = category
    return root


def highlight(review: str, mapping: List[Tuple[str, str]]) -> str:
    root = build_trie(mapping)
    n = len(review)
    out: List[str] = []
    i = 0
    while i < n:
        at_word_start = _is_word_char(review[i]) and (
            i == 0 or not _is_word_char(review[i - 1])
        )
        if at_word_start:
            # Walk the trie; remember the longest phrase that ends on a word end.
            node = root
            best_end, best_cat = -1, None
            j = i
            while j < n:
                node = node.children.get(review[j].lower())
                if node is None:
                    break
                j += 1
                if node.category is not None and (
                    j == n or not _is_word_char(review[j])
                ):
                    best_end, best_cat = j, node.category
            if best_end != -1:
                out.append(f"[{best_cat}]{{{review[i:best_end]}}}")
                i = best_end
                continue
            # No match: copy the whole word, so we never start inside it.
            j = i
            while j < n and _is_word_char(review[j]):
                j += 1
            out.append(review[i:j])
            i = j
            continue
        out.append(review[i])
        i += 1
    return "".join(out)

Example:

mapping = [("san francisco", "city"), ("san", "word"), ("golden gate", "park")]
highlight("Loved San Francisco! san? sandbox", mapping)
# 'Loved [city]{San Francisco}! [word]{san}? sandbox'

Complexity

Let n be the review length, P the number of phrases, and S the total length of all phrases.

Building the trie: O(S) time, O(S) space.
Highlighting: each word start walks the trie at most L characters, where L is the longest phrase. Time is O(n · L) in the worst case, and close to O(n) in practice, because most walks stop after one or two characters. The output and the list of pieces are O(n) extra space.
Brute force for comparison: O(n · P · L) time, O(1) extra space beyond the output.

Test cases

With m = [("san francisco", "city"), ("san", "word"), ("golden gate bridge", "landmark"), ("golden gate", "park"), ("wifi", "amenity")]:

"Loved San Francisco!" → "Loved [city]{San Francisco}!" (longest match, case kept).
"san? sandbox" → "[word]{san}? sandbox" (punctuation is a boundary; no partial word).
"xsan san" → "xsan [word]{san}" (a match cannot start inside a word).
"Golden Gate Bridge view" → "[landmark]{Golden Gate Bridge} view".
"Golden Gate Park" → "[park]{Golden Gate} Park" (falls back to the shorter phrase).
"San Franciscans" → "[word]{San} Franciscans" (the long phrase fails the end boundary, so the short one wins).
"no WiFi, no wifi2" → "no [amenity]{WiFi}, no wifi2" (digits are word characters).
"" with any mapping → "".
"abc" with an empty mapping → "abc".
"wifi wifi" with [("wifi", "a"), ("wifi", "b")] → "[a]{wifi} [a]{wifi}" (first mapping wins, every occurrence wrapped).
"pet-friendly" with [("pet-friendly", "policy"), ("pet", "animal")] → "[policy]{pet-friendly}"; "pet friendly" with the same mapping → "[animal]{pet} friendly".

Follow-ups

Flexible separators. "Treat any run of spaces or punctuation inside a phrase as equal." Tokenize the review into words with their spans, and build the trie over lowercased words instead of characters. A match is then a path of words, and the span runs from the first word's start to the last word's end. Whole-word matching becomes automatic, because you only start at word tokens.
Already-formatted or HTML input. "The review may already contain [x]{...} or HTML tags." Skip protected regions while scanning: tokenize the input into text and markup, and only run the matcher on text pieces. Also escape [, ], {, } in matched text if the output format must be parseable.
Many reviews, one mapping. Build the trie once and reuse it; the per-review cost is then O(n · L). For very large phrase sets, convert the trie to an Aho–Corasick automaton so one pass finds every candidate in O(n + matches), then pick the longest non-overlapping ones left to right with the word-boundary filter.
Nested or overlapping categories. "Show every category, not just the longest." Collect all (start, end, category) matches from the trie walks, then either output nested tags (sort by start, then by length descending, and use a stack) or return the list of spans for the client to render.
Stemming or plurals. "hotel should match hotels." Normalize both sides with the same function (lowercase, strip a plural s, or a real stemmer) and keep a map from normalized positions back to the original text so the output still shows the reviewer's words.

Interviewer expectations

Mid-level (L4)

Asks about case, punctuation, and overlap before coding, then states the three rules.
Writes a correct brute force with a clear word-boundary check, including the start-of-word check.
Gets the longest-match rule right and passes the "sandbox" and "Golden Gate Park" cases.

Senior (L5)

Moves to a trie without prompting and explains why it removes the factor of P.
Handles the edge cases cleanly: empty phrases, duplicate phrases, phrases with punctuation, match at the end of the string, digits as word characters.
Builds the output in one pass with a list and join, not repeated string replace (which breaks on overlaps and on case).

Staff (L6+)

Discusses the character-trie versus word-trie trade-off and which one fits the product (exact separators versus flexible ones).
Raises Aho–Corasick for large dictionaries and many reviews, and how to keep the longest-match, whole-word rule on top of it.
Thinks about the real feature: escaping the output format, protecting existing markup, Unicode word characters, and returning spans instead of a formatted string so the UI decides how to render.