Find list pair with maximum overlap
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.
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.