Movie History Friends
MediumHash Tables · Netflix
Netflix wants to suggest "watch buddies": pairs of active users with similar taste.
Each entry of histories is [user_id, movies], where user_id is a unique integer and movies is that user's viewing history as a list of movie id strings. A history can contain the same movie more than once (a rewatch).
- A user is active if their history has at least
kentries. Rewatches count here:["m1", "m1", "m2"]is 3 entries. - Two active users are buddies if at least
mdistinct movie ids appear in both of their histories. Rewatches do not count twice here.
Return every buddy pair as [a, b] with a < b, and sort the list of pairs in ascending order (by a, then by b). Return [] if there are none.
Example 1
- Input:
- histories = [[3, ["dune", "heat", "up", "heat"]], [1, ["heat", "up", "jaws"]], [2, ["dune", "up"]], [4, ["heat", "up"]]], k = 3, m = 2
- Output:
- [[1, 3]]
- Explanation
- Users 3 (4 entries) and 1 (3 entries) are active; users 2 and 4 have only 2 entries, so they are skipped even though user 4 shares
heatandupwith both. Users 1 and 3 shareheatandup, which meetsm = 2, and the pair is written smaller id first.
Example 2
- Input:
- histories = [[10, ["a", "a", "a"]], [20, ["a", "b", "c"]]], k = 2, m = 2
- Output:
- []
- Explanation
- Both users are active (3 entries each), but they share only one distinct movie,
a, so they are not buddies even though user 10 watched it three times.
Example 3
- Input:
- histories = [[5, ["x", "y"]], [2, ["x", "z"]], [9, ["x", "y"]]], k = 1, m = 1
- Output:
- [[2, 5], [2, 9], [5, 9]]
- Explanation
- Everyone shares
x, so all three pairs qualify. They are returned as[2, 5],[2, 9],[5, 9].
Constraints
- 0 ≤ histories.length ≤ 2000
- User ids are distinct integers in
[1, 10^6]. - The total number of history entries across all users is at most
2 * 10^4. - 0 ≤ k ≤ 100
- 1 ≤ m ≤ 100