Problem Overview

This is a follow-up to the Movie History Friends problem. Each customer has a list representing the movies they've watched in the order they were viewed. In this variant, two customers are considered "friends" if at least m out of their last k movies are common (not necessarily in the same order or position).

Given a map of customer IDs to their movie watch history, and integers k and m (where m <= k), return all pairs of customer IDs that are friends.

Important Notes

• If a customer has fewer than k movies in their history, they cannot be friends with anyone

• The common movies don't need to be in the same order or at the same positions

• Return pairs in any order, but each pair should have the smaller ID first

• Each pair should appear only once in the result

Problem Requirements

Given a dictionary mapping customer IDs to their movie watch history (as a list of movie IDs), find all pairs of customers who share at least m common movies in their last k movies.

Example

` history = { 1: ["A", "B", "C", "D"], 2: ["X", "D", "B", "A"], 3: ["P", "Q", "R", "S"] } k = 3 m = 2

result = find_friends(history, k, m)

Returns [[1, 2]]

Explanation:

Customer 1's last 3: ["B", "C", "D"]

Customer 2's last 3: ["D", "B", "A"]

They share "B" and "D" (2 movies), which meets m=2

Customer 3 shares no movies with others

`

• Extract the last k movies for each customer

• For each pair of customers, count common movies (using set intersection)

• Only include pairs where the count of common movies is >= m

• Return pairs with smaller customer ID first

• Time complexity should be O(n^2 * k) where n is the number of customers

• Can customer IDs be non-consecutive integers?

• Should we handle duplicate movie IDs in a customer's history?

• What if k is larger than the history length for all customers?

• Should the result be sorted by customer IDs?