Quick Overview

This question evaluates proficiency with set operations and similarity metrics (Jaccard), scalable algorithm design and complexity analysis for large datasets, and the ability to handle streaming updates and deterministic tie-breaking.

Find list pair with maximum overlap

Company: Pinterest

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given N labeled lists of items as a Python dict mapping list_name -> iterable of strings. Example input: {'L1': ['A','B','C'], 'L2': ['A','C','D'], 'L3': ['B','C','E'], 'L4': []}. Treat each list as a set (ignore duplicates). Write a function that returns the single unordered pair of list names with the largest overlap count (size of intersection), along with that overlap count and the Jaccard similarity (|A∩B| / |A∪B|). Tie-breakers: 1) higher Jaccard, 2) lexicographically smaller pair (by list name). For the example above, the expected result is ('L1','L2', overlap=2, jaccard=0.5). Constraints: up to 200,000 lists, 5,000,000 total items; items are case-sensitive strings; memory is limited so an O(N^2) all-pairs comparison is not acceptable. 1) Describe your algorithm at a high level (e.g., an inverted index over items) and analyze time/space complexity. 2) Implement it in Python. 3) Extend to return the top-k pairs efficiently. 4) Explain how you would adapt your solution if the input is a stream of (list_name, item) updates where lists can grow over time.

Quick Answer: This question evaluates proficiency with set operations and similarity metrics (Jaccard), scalable algorithm design and complexity analysis for large datasets, and the ability to handle streaming updates and deterministic tie-breaking.

Part 1: Inverted-Index Overlap Statistics

You are given a Python dict mapping list_name -> iterable of strings. Treat each list as a set, so duplicates inside the same list do not matter. Build the core statistics behind an inverted-index solution for overlap detection. Return: (1) membership_count = total number of distinct (list_name, item) memberships after deduplication, (2) unique_item_count = number of distinct items overall, (3) pair_updates = the total number of pair increments an inverted-index algorithm would perform, equal to the sum over items of C(f, 2) where f is the number of lists containing that item, and (4) pair_counts = all unordered list-name pairs with positive overlap, with their overlap counts, sorted lexicographically by pair.

Constraints

  • 1 <= number of lists <= 200000, but your algorithm should also handle empty input.
  • The total number of raw items across all iterables can be up to 5000000.
  • Items are case-sensitive strings.
  • Duplicates within the same list must be ignored.

Examples

Input: ({'L1': ['A', 'B', 'C'], 'L2': ['A', 'C', 'D'], 'L3': ['B', 'C', 'E'], 'L4': []},)

Expected Output: {'membership_count': 9, 'unique_item_count': 5, 'pair_updates': 5, 'pair_counts': [('L1', 'L2', 2), ('L1', 'L3', 2), ('L2', 'L3', 1)]}

Explanation: After deduplication there are 9 distinct memberships. Item frequencies are A:2, B:2, C:3, D:1, E:1, so pair_updates = 1 + 1 + 3 = 5.

Input: ({'A': ['x', 'x'], 'B': ['x', 'y', 'y'], 'C': []},)

Expected Output: {'membership_count': 3, 'unique_item_count': 2, 'pair_updates': 1, 'pair_counts': [('A', 'B', 1)]}

Explanation: Duplicates inside a list do not count. Only item x is shared.

Hints

  1. First deduplicate each individual list, then think item -> lists that contain it.
  2. If one item appears in f different lists, it contributes C(f, 2) pair updates.

Part 2: Maximum-Overlap List Pair

You are given a Python dict mapping list_name -> iterable of strings. Treat each list as a set, so duplicates inside the same list do not matter. Return the single unordered pair of list names with the largest overlap count, along with the overlap count and the Jaccard similarity. Tie-breakers are: (1) larger overlap count, (2) larger Jaccard similarity, (3) lexicographically smaller pair. If there are fewer than 2 lists, return None. Define the Jaccard similarity of two empty sets as 1.0.

Constraints

  • 1 <= number of lists <= 200000, but your function should also handle 0 or 1 list.
  • The total number of raw items across all iterables can be up to 5000000.
  • Items are case-sensitive strings.
  • An O(N^2) all-pairs comparison is not acceptable for large inputs.

Examples

Input: ({'L1': ['A', 'B', 'C'], 'L2': ['A', 'C', 'D'], 'L3': ['B', 'C', 'E'], 'L4': []},)

Expected Output: ('L1', 'L2', 2, 0.5)

Explanation: L1-L2 and L1-L3 both have overlap 2 and Jaccard 0.5, so lexicographic order picks ('L1', 'L2').

Input: ({'A': ['x', 'y'], 'B': ['x'], 'C': ['y', 'z']},)

Expected Output: ('A', 'B', 1, 0.5)

Explanation: A-B and A-C both overlap by 1, but A-B has the larger Jaccard score.

Hints

  1. Use an inverted index item -> list names to count only pairs that actually share at least one item.
  2. If no pair shares an item, handle the zero-overlap case separately.

Part 3: Top-K Overlapping List Pairs

You are given a Python dict mapping list_name -> iterable of strings and an integer k. Treat each list as a set, so duplicates inside the same list do not matter. Return the top k unordered pairs with positive overlap only, ordered by: (1) larger overlap count, (2) larger Jaccard similarity, (3) lexicographically smaller pair. If fewer than k pairs have positive overlap, return all of them. If k <= 0, return an empty list.

Constraints

  • 1 <= number of lists <= 200000, but your solution should also handle empty input.
  • The total number of raw items across all iterables can be up to 5000000.
  • Items are case-sensitive strings.
  • Only pairs with overlap_count > 0 should appear in the result.

Examples

Input: ({'L1': ['A', 'B', 'C'], 'L2': ['A', 'C', 'D'], 'L3': ['B', 'C', 'E'], 'L4': []}, 2)

Expected Output: [('L1', 'L2', 2, 0.5), ('L1', 'L3', 2, 0.5)]

Explanation: The two best positive-overlap pairs both have overlap 2 and Jaccard 0.5.

Input: ({'A': ['x', 'x', 'y'], 'B': ['x'], 'C': ['x', 'y'], 'D': ['z']}, 3)

Expected Output: [('A', 'C', 2, 1.0), ('A', 'B', 1, 0.5), ('B', 'C', 1, 0.5)]

Explanation: Duplicates are ignored. A-C is the only pair with overlap 2.

Hints

  1. First compute positive-overlap pair counts using an inverted index.
  2. A heap of size k can avoid fully sorting every candidate pair.

Part 4: Best Pair Under Streaming List Updates

Initially, no lists exist. You receive a stream of updates of the form (list_name, item), meaning that item is added to that list. Lists only grow over time. If the same (list_name, item) appears again, ignore it. After each update, return the current best unordered pair of existing list names ranked by: (1) larger overlap count, (2) larger Jaccard similarity, (3) lexicographically smaller pair. If fewer than 2 lists exist after an update, return None for that step. Because lists are created only by updates, every existing list is non-empty.

Constraints

  • 1 <= number of updates <= 300000, but your solution should also handle empty input.
  • Each update is a pair (list_name, item).
  • A duplicate update for an already-present (list_name, item) must not change the state.
  • A fully recomputed all-pairs scan after every update is too slow.

Examples

Input: ([('L1', 'A'), ('L2', 'B'), ('L2', 'B'), ('L1', 'B'), ('L2', 'A')],)

Expected Output: [None, ('L1', 'L2', 0, 0.0), ('L1', 'L2', 0, 0.0), ('L1', 'L2', 1, 0.5), ('L1', 'L2', 2, 1.0)]

Explanation: The duplicate update ('L2', 'B') does nothing. The best pair evolves as overlap grows.

Input: ([('L1', 'A'), ('L2', 'A'), ('L3', 'B'), ('L4', 'B'), ('L1', 'X'), ('L2', 'X')],)

Expected Output: [None, ('L1', 'L2', 1, 1.0), ('L1', 'L2', 1, 1.0), ('L1', 'L2', 1, 1.0), ('L3', 'L4', 1, 1.0), ('L1', 'L2', 2, 1.0)]

Explanation: Adding a unique item to L1 lowers the Jaccard score of L1-L2, so L3-L4 temporarily becomes the best pair.

Hints

  1. An update only changes overlap counts for lists that already had the same item, and it only changes Jaccard values for positive-overlap neighbors of the updated list.
  2. Use lazy heap entries: push new scores when something changes, and discard stale entries when they reach the top.

Loading coding console...