Find list pair with maximum overlap

Q: Find list pair with maximum overlap

This is a Coding & Algorithms interview question from Pinterest for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Find list pair with maximum overlap

Comments (0)