Recommend movies watched by friends and friends of friends

Recommend movies to a user from their social circle. Two helper calls are given: one returns a user's friends, the other the movies a user has watched. Return movie titles ordered by how many people in the user's circle watched them, where the circle is the user's friends and their friends' friends.

Interface

Unless you agree on a different interface with the interviewer, assume:

• Helper.get_friends(user: str) -> list[str] and Helper.get_movies_watched(user: str) -> list[str] — given.
• recommend_movies(user: str) -> list[str] — every movie watched by at least one person in the circle, most watched first, ties by title. The user is never part of their own circle, and each person counts once per movie.

Example

friends:  ana: ben, cy      ben: ana, dee     cy: ana, dee
          dee: ben, cy, eve eve: dee
watched:  ana: Up           ben: Heat, Up     cy: Heat, Jaws
          dee: Jaws, Alien  eve: Brazil

recommend_movies("ana")  ->  ["Heat", "Jaws", "Alien", "Up"]
# circle = ben, cy (friends) and dee (a friend of both); eve is three hops away
# Heat: ben, cy = 2   Jaws: cy, dee = 2   Alien: dee = 1   Up: ben = 1

Constraints

• Friendship is mutual. The helpers may be slow (think remote calls), so call each one as few times as you can.

Clarifying questions

• Should movies the user has already watched be left out?
• Does someone who is both a friend and a friend of a friend count once?
• Should a direct friend's view weigh more than a friend of a friend's?
• How are ties ordered, and how many results are wanted?
• Can a user's watch list repeat a movie?

What a strong answer covers

• A two-level BFS from the user with a visited set, so each person is counted once and the user and anyone further away are excluded.
• A counter over movies, with each person's list turned into a set first.
• Sorting by (-count, title), or a heap when only the top k are wanted: O(P + M log M) for P people and M distinct movies.
• Calling each helper once per person, and caching the results.
• Edge cases: no friends, friends with empty watch lists, cycles in the friend graph.

Follow-ups

• Leave out movies the user has seen and return only the top k.
• Weigh friends twice as much as friends of friends.
• Extend to any depth d, or compute recommendations for every user overnight.