Shortest Unique Metric Tag

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
Airbnb

Problem

Return the shortest contiguous piece of each name in metrics that appears inside no other metric's name, one tag per metric in the same order as the input, taking the lexicographically smallest piece when several are equally short. The names are fully-qualified dashboard autocomplete keys like 'bookings.checkout.success_rate', so every character counts toward a piece, punctuation included.

One token per metric. Make it unambiguous.

Example 1

Input:

metrics = ["clicks","clocks","cluster"]

Output:

["i","o","e"]

Example 2

Input:

metrics = ["bookings","booking_id","books"]

Output:

["gs","_","ks"]

Worked solution and explanation

Why this problem exists in real interviews

This is a common DE phone-screen pattern. It tests whether you can scan substrings of one string against the rest of a collection, manage a tiebreak rule, and reason about the worst-case complexity of substring enumeration. The metrics-platform framing is incidental; the underlying skill is string scanning with a uniqueness predicate across a list.

Break down the requirements

Step 1: Per-metric scope: only substrings of metrics[i] matter

For metric m, you only care about substrings of m. The 'others' set is every other metric joined into a haystack. Substring containment in that haystack is the cheap predicate.

Step 2: Length-major enumeration enforces 'shortest then lex'

Loop length L from 1 to len(metric). At each L, build the set of substrings of that length, sort lexicographically, and pick the first one not present in the others-haystack. Length-major order plus lex sort enforces both rules in one pass.

Step 3: Build the others-haystack with a sentinel

Concatenate the other metrics with a sentinel character that cannot appear in metric names (e.g., a NUL byte). This prevents a candidate from matching a substring that straddles two metrics in the haystack.

Step 4: Handle the no-unique-substring case

Duplicate metrics, or a metric that is itself a substring of another, will exhaust every length without finding a unique substring. Return '' for those indices.

The solution

Length-major substring enumeration with lex tiebreak
def shortest_unique_metric_tag(metrics: list[str]) -> list[str]:
    result = []
    for i, m in enumerate(metrics):
        others = '\x00'.join(metrics[:i] + metrics[i+1:])
        found = ''
        for length in range(1, len(m) + 1):
            candidates = sorted({m[s:s+length] for s in range(len(m) - length + 1)})
            unique = next((c for c in candidates if c not in others), None)
            if unique is not None:
                found = unique
                break
        result.append(found)
    return result

Common follow-up questions