Citation Highlighting

Problem Overview

You are given a document produced by an LLM and a list of source phrases. Your task is to find exact phrase matches in the document and wrap the matched regions in <yellow> and </yellow> tags.

This is usually asked in two parts:

1. First, find all matching phrases and merge overlapping or adjacent matches into highlighted regions.
2. Then, count how often each source appears across the entire document and add source citations to every highlighted region.

The core problem is interval merging. The follow-up tests whether you can preserve the relationship between merged intervals and the source phrases that contributed to them. [Source: darkinterview.com]

The core requirements are stable: exact word-level matching, merging overlaps, global source counts, and citations for merged regions. Details such as case sensitivity, punctuation rules, how adjacency is defined, and how frequency ties are ordered vary between interviewers, so confirm them before coding. The choices used by this write-up are stated below.

Part 1: Highlight Matching Phrases

Problem Statement

Implement a function:

def highlight_matches(document: str, sources: list[str]) -> str:
    pass

A source matches when its complete text occurs at word boundaries in document. [Source: darkinterview.com]

For the reference implementation in this write-up, assume:

• Matching is case-sensitive. Whether matching should ignore case is left open, so confirm with the interviewer.
• Every source is non-empty and begins and ends with a letter or digit.
• A source must match at word boundaries. For example, "blue" does not match the "blue" inside "blueprint".
• The same source may occur multiple times.
• Matches may overlap.
• Some interviewers also ask to merge adjacent matches. This implementation treats matches separated only by whitespace as adjacent.
• The original document, including its capitalization, punctuation, and whitespace, must be preserved.

Return the document with every merged matched region wrapped in <yellow> and </yellow> tags.

Example

document = "The quick brown fox jumps over the lazy dog."
sources = ["quick brown", "brown fox jumps"]

highlight_matches(document, sources)
# Returns:
# "The <yellow>quick brown fox jumps</yellow> over the lazy dog."

The two matches overlap on "brown", so they become one highlighted interval spanning "quick brown fox jumps". [Source: darkinterview.com]

Interval-Merging Solution

First, collect the interval for every valid source occurrence. Then sort the intervals by their starting position and merge them. Build the output only after all intervals have been merged so that inserting tags does not invalidate any recorded indices.

from dataclasses import dataclass


@dataclass(frozen=True)
class Match:
    start: int
    end: int
    source_id: int


@dataclass
class HighlightSpan:
    start: int
    end: int
    source_ids: set[int]


def is_word_character(character: str) -> bool:
    return character.isalnum() or character == "_"


def has_word_boundaries(document: str, start: int, end: int) -> bool:
    left_is_clear = start == 0 or not is_word_character(document[start - 1])
    right_is_clear = end == len(document) or not is_word_character(document[end])
    return left_is_clear and right_is_clear


def find_matches(document: str, sources: list[str]) -> list[Match]:
    matches = []

    for source_id, source in enumerate(sources):
        last_start = len(document) - len(source)
        for start in range(last_start + 1):
              document.startswith(source, start):
                

            end = start + (source)
             has_word_boundaries(document, start, end):
                matches.append(Match(start, end, source_id))

     matches


 () -> :
     next_start <= current_end:
         

    
    
     document[current_end:next_start].isspace()


 () -> [HighlightSpan]:
    matches.sort(key= : (.start, .end))
    spans = []

       matches:
          spans   should_merge(document, spans[-].end, .start):
            spans.append(
                HighlightSpan(.start, .end, {.source_id})
            )
            

        spans[-].end = (spans[-].end, .end)
        spans[-].source_ids.add(.source_id)

     spans


 () -> :
    output = []
    cursor = 

     span  spans:
        output.append(document[cursor:span.start])
        output.append()
        output.append(document[span.start:span.end])
        output.append()
        cursor = span.end

    output.append(document[cursor:])
     .join(output)


 () -> :
    matches = find_matches(document, sources)
    spans = merge_matches(document, matches)
     render_highlights(document, spans)

Edge Cases

• document = "blueprint", sources = ["blue"] produces no highlight because "blue" is not a complete word.
• A source that appears multiple times creates multiple matches.
• Duplicate source strings are still separate sources because citations use their positions in the input list.
• If no source matches, return the original document unchanged.

Complexity

Let N be the document length, L be the total number of characters across all source phrases, and K be the total number of valid matches.

• Time: O(N * L + K log K) for direct phrase comparisons and interval sorting
• Space: O(K + N) for the intervals and rendered output

Part 2: Add Global Counts And Citations

Follow-Up Prompt

Extend the solution so that each highlighted region identifies the sources that contributed to it. [Source: darkinterview.com]

For every source:

1. Count all of its valid occurrences across the entire document. Counts are global, not limited to a single highlighted region.
2. For each merged region, collect the indices of the sources with at least one match inside that region.
3. Order a region's source indices by descending global occurrence count. Tie-breaking is left open; this write-up breaks ties by smaller source index.
4. Append each zero-based source index after the closing tag using the format [source_id].

Return the tagged document, the global count for every source, and the citations attached to each highlighted region.

from dataclasses import dataclass


@dataclass
class CitationResult:
    tagged_document: str
    counts: dict[int, int]
    citations: list[list[int]]


def highlight_with_citations(
    document: str,
    sources: list[str],
) -> CitationResult:
    pass

Example

document = "The quick brown fox jumps over the quick blue fox."
sources = [
    "quick brown",      # source 0, one occurrence
    "brown fox jumps",  # source 1, one occurrence
    "quick",            # source 2, two occurrences
    "blue",             # source 3, one occurrence
]

result = highlight_with_citations(document, sources)

result.tagged_document
# "The <yellow>quick brown fox jumps</yellow>[2][0][1] over the "
# "<yellow>quick blue</yellow>[2][3] fox."

result.counts
# {0: 1, 1: 1, 2: 2, 3: 1}

result.citations
# [[2, 0, 1], [2, 3]]

Source 2 is listed first in both citation groups because it occurs twice globally. Sources with equal counts are ordered by their input index. [Source: darkinterview.com]

Extended Solution

The Match records from Part 1 already retain their source_id. Count those records before merging them. Each merged HighlightSpan keeps the set of source IDs that contributed to the span.

This solution reuses find_matches, merge_matches, HighlightSpan, and CitationResult from Part 1 and the follow-up prompt.

def render_with_citations(
    document: str,
    spans: list[HighlightSpan],
    citation_groups: list[list[int]],
) -> str:
    output = []
    cursor = 0

    for span, source_ids in zip(spans, citation_groups):
        output.append(document[cursor:span.start])
        output.append("<yellow>")
        output.append(document[span.start:span.end])
        output.append("</yellow>")

        for source_id in source_ids:
            output.append(f"[{source_id}]")

        cursor = span.end

    output.append(document[cursor:])
    return "".join(output)


def highlight_with_citations(
    document: str,
    sources: list[str],
) -> CitationResult:
    matches = find_matches(document, sources)

    counts = {source_id: 0 for source_id in range(len(sources))}
    for match in matches:
        counts[match.source_id] += 1

    spans = merge_matches(document, matches)
    citation_groups = [
        sorted(
            span.source_ids,
            key=lambda source_id: (-counts[source_id], source_id),
        )
        for span in spans
    ]

    tagged_document = render_with_citations(
        document,
        spans,
        citation_groups,
    )

    return CitationResult(tagged_document, counts, citation_groups)

Complexity

Let N be the document length, L be the total number of characters across all source phrases, S be the number of sources, and K be the total number of valid matches. [Source: darkinterview.com]

• Time: O(N * L + K log K + K log S)
• Space: O(K + S + N)

The final K log S term is a conservative bound for sorting the distinct source citations attached to all merged spans.