Co-occurring tags for a tag filter: Frontier Interview's solution

Question: Co-occurring tags for a tag filter

Companies: Netflix

Difficulty: Medium

Problem statement

Each title in a catalog carries a group of tags that were assigned together, for example ["drama", "british", "crime"]. You get all the groups as a list of lists of strings, groups, and a list of strings, filter_tags.

A group matches when it contains every tag in filter_tags. Return every tag that appears in at least one matching group and is not itself in filter_tags.

Implement:

def find_complement_tags(groups: list[list[str]], filter_tags: list[str]) -> list[str]: ...

Rules:

Each tag appears at most once in the output. Any order is accepted.
Tags are case-sensitive strings. A group or the filter may contain the same tag more than once.
An empty filter_tags matches every group.
Up to 10^5 groups, up to 50 tags per group, up to 20 filter tags.

Example 1

groups = [["drama", "period", "british"],
          ["drama", "british", "crime"],
          ["comedy", "british"]]
filter_tags = ["drama", "british"]
output: ["period", "crime"]

The first two groups contain both filter tags. The third has british but not drama.

Example 2

groups = [["drama", "crime"], ["comedy"]]
filter_tags = ["drama", "comedy"]
output: []

Both filter tags exist, but no single group has both.

Be ready to discuss what changes if the groups stay fixed and many different filters are queried against them.

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

Approach

Restate the task first: a group qualifies when the filter is a subset of the
group's tags. The answer is the union of all qualifying groups, minus the
filter tags, with each tag listed once.

Brute force. For each group, for each filter tag, scan the group list to see
whether the tag is there. That costs O(G · F · L) for G groups of length up to L
and F filter tags. It is correct but slow because list membership is linear.

One pass with sets (the expected answer).

Turn filter into a set need. Duplicates in the filter do not matter.
For each group, build tags = set(group) and check need <= tags.
Subset testing iterates the smaller set, so it costs O(F) per group after
O(L) to build the set.
For a qualifying group, add every tag that is not in need to the result.
Keep a seen set next to an output list so the output is distinct and in
first-seen order (deterministic, which makes tests easy even though any
order is allowed).

Invariants: seen always equals the set of tags in result; no tag in need
ever enters result; a group adds tags only after it has passed the subset
check.

Edge cases worth naming out loud: an empty filter makes every group qualify, so
the answer is every distinct tag; a filter tag that appears in no group means
nothing qualifies; duplicate tags inside a group must not produce duplicates in
the output; empty groups only qualify for an empty filter and add nothing.

Many queries over the same groups. If the interviewer says the groups are
fixed and filters arrive repeatedly, build an inverted index tag -> set of group ids once. A query intersects the posting sets of the filter tags,
starting from the smallest, and stops early when the intersection is empty.
Then it unions the tags of the surviving groups. That avoids touching groups
that cannot qualify. TagIndex below does this.

Code

from collections import defaultdict
from typing import Iterable


def find_complement_tags(groups: list[list[str]], filter_tags: list[str]) -> list[str]:
    """Distinct tags that appear in at least one group containing every filter
    tag, excluding the filter tags themselves. First-seen order."""
    need = set(filter_tags)
    seen: set[str] = set()
    result: list[str] = []
    for group in groups:
        tags = set(group)
        if not need <= tags:
            continue
        for tag in group:  # iterate the list to keep first-seen order
            if tag not in need and tag not in seen:
                seen.add(tag)
                result.append(tag)
    return result


class TagIndex:
    """Fixed groups, many filter queries. Inverted index: tag -> group ids."""

    def __init__(self, groups: Iterable[list[str]]) -> None:
        self._groups: list[list[str]] = []
        self._postings: dict[str, set[int]] = defaultdict(set)
        for group in groups:
            self.add_group(group)

    def add_group(self, group: list[str]) -> int:
        gid = len(self._groups)
        unique = list(dict.fromkeys(group))  # dedupe, keep order
        self._groups.append(unique)
        for tag in unique:
            self._postings[tag].add(gid)
        return gid

    def _matching_groups(self, need: set[str]) -> list[int]:
        if not need:
            return list(range(len(self._groups)))
        postings = []
        for tag in need:
            ids = self._postings.get(tag)
            if not ids:
                return []  # a filter tag nobody has: no group qualifies
            postings.append(ids)
        postings.sort(key=len)  # intersect smallest first
        survivors = set(postings[0])
        for ids in postings[1:]:
            survivors &= ids
            if not survivors:
                return []
        return sorted(survivors)

    def query(self, filter_tags: list[str]) -> list[str]:
        need = set(filter_tags)
        seen: set[str] = set()
        result: list[str] = []
        for gid in self._matching_groups(need):
            for tag in self._groups[gid]:
                if tag not in need and tag not in seen:
                    seen.add(tag)
                    result.append(tag)
        return result


if __name__ == "__main__":
    groups = [
        ["drama", "period", "british"],
        ["drama", "british", "crime"],
        ["comedy", "british"],
        ["drama", "crime", "korean"],
    ]
    assert find_complement_tags(groups, ["drama", "british"]) == ["period", "crime"]
    assert find_complement_tags(groups, ["crime"]) == ["drama", "british", "korean"]
    assert find_complement_tags(groups, ["anime"]) == []
    assert find_complement_tags(groups, []) == [
        "drama", "period", "british", "crime", "comedy", "korean"]
    assert find_complement_tags([["a", "a", "b"], ["a", "b", "b"]], ["a", "a"]) == ["b"]
    assert find_complement_tags([[], ["x"]], ["x"]) == []
    assert find_complement_tags([], ["x"]) == []
    index = TagIndex(groups)
    for f in (["drama", "british"], ["crime"], ["anime"], [], ["british"]):
        assert index.query(f) == find_complement_tags(groups, f), f
    print("ok")

Complexity

Let G be the number of groups, L the longest group, T the total number of tags
across all groups (T ≤ G · L), and F the number of filter tags.

find_complement_tags: O(F + T) time. Each group costs O(L) to turn into a
set plus O(min(F, L)) for the subset check, and each tag of a qualifying
group is handled once with O(1) set operations. Space O(F + U + L), where U is
the number of distinct tags in the output.
TagIndex.__init__ / add_group: O(T) total time and space for the stored
groups and posting sets.
TagIndex.query: O(F + P + S) time, where P is the size of the smallest
posting set (the intersection never grows past it; each later intersection
costs O(size of the smaller side)) and S is the total size of the matching
groups, plus O(M log M) to sort M matching ids for a stable order (drop the
sort if order does not matter). Space O(P + U).

Test cases

With groups = [["drama","period","british"], ["drama","british","crime"], ["comedy","british"], ["drama","crime","korean"]]:

filter ["drama","british"] → ["period","crime"] (groups 0 and 1 qualify).
filter ["crime"] → ["drama","british","korean"] (groups 1 and 3).
filter ["british"] → ["drama","period","crime","comedy"].
filter ["anime"] → [] (no group has the tag).
filter ["drama","comedy"] → [] (both tags exist, never together).
filter [] → every distinct tag: ["drama","period","british","crime","comedy","korean"].
Duplicates: groups [["a","a","b"],["a","b","b"]], filter ["a","a"] → ["b"].
A group that equals the filter adds nothing: groups [[],["x"]], filter ["x"] → [].
No groups: [] with any filter → [].

Follow-ups

Many queries, fixed groups. Build the inverted index once (TagIndex)
and intersect posting sets smallest first. With very large posting lists,
store them as sorted id arrays or bitmaps (roaring bitmaps) so intersection
is a fast merge or bitwise AND.
Rank the suggestions. Return the complement tags ordered by how many
qualifying groups contain them (top k). Count with a Counter while you
union, then use heapq.nlargest(k, ...), O(S + U log k). This is the
"related tags" or facet-count feature behind a catalog filter.
Richer filters. Support excluded tags (must_not) and any-of groups.
With the index: AND is intersection, OR is union, NOT is set difference
applied after the positive terms have narrowed the candidates. Reject a
query with only NOT terms or evaluate it against the full id range.
Groups change over time. Support add_group and remove_group. Removal
deletes the id from each of its tags' posting sets and leaves a tombstone in
the group list; compact the ids when tombstones pile up.
Data too big for one machine. Shard groups by id. Each shard runs the
query on its own groups and returns its complement set (or counts for the
ranked version); a coordinator merges with a union or a sum. Because the
subset test is per group, no cross-shard joins are needed.

Interviewer expectations

Mid-level (L4)

States the subset condition correctly and handles distinctness with a set.
Writes the one-pass set solution in O(T) and explains why list membership
makes the brute force slower.
Covers the empty filter, a missing filter tag and duplicate tags without
prompting after one hint.

Senior (L5)

Asks about query volume and data size before choosing between the scan and
an inverted index, and builds the index when filters repeat.
Intersects smallest posting set first and exits early on an empty result.
Adds ranking by co-occurrence count cleanly and gives correct complexity for
each operation.

Staff (L6+)

Frames it as faceted search over a tagged catalog and discusses posting-list
representations (sorted arrays, bitmaps) and their trade-offs.
Designs updates, deletes and sharding with a merge step, and notes that the
per-group subset test keeps shards independent.
Talks about caching hot filter combinations, latency budgets, and how to
test equivalence between the scan and the index (as the asserts do here).