Get Watched Videos by Your Friends

Get Watched Videos by Your Friends

What is this problem about?

The Get Watched Videos by Your Friends interview question asks you to find the videos watched by your friends at a specific "level" of connection. Level 1 friends are your direct friends. Level 2 friends are the friends of your Level 1 friends (excluding yourself and Level 1 friends). You need to return a list of all videos watched by people at exactly the given level, sorted by their frequency of occurrence (ascending), and then alphabetically by video name.

Why is this asked in interviews?

Amazon uses this Graph interview pattern to test your ability to perform a constrained Breadth-First Search (BFS). It evaluates if you know how to stop a search at a specific depth and how to avoid cycles (not revisiting friends). It also tests your ability to aggregate and sort data using custom comparators.

Algorithmic pattern used

This problem combines BFS, Hash Table Counting, and Sorting.

1. BFS: Start from the given id. Use a queue and a visited set to perform a level-by-level BFS. Stop when you reach the target level.
2. Collect: Once at the target level, all nodes currently in the queue are the target friends.
3. Count: Iterate through the watchedVideos of these target friends and count their frequencies using a Hash Map.
4. Sort: Convert the map to a list of pairs and sort them using the specific rules (first by frequency, then alphabetically).

Example explanation

id = 0, level = 2 Friends graph: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3. Videos: [ ["A"], ["B"], ["C"], ["D", "B"] ]

1. Level 0: Queue contains [0]. Visited {0}.
2. Level 1: Pop 0. Add neighbors 1, 2. Queue [1, 2]. Visited {0, 1, 2}.
3. Level 2: Target level reached! Pop 1 (adds 3), Pop 2 (3 is visited). Queue is [3].
4. Friends at Level 2: Person 3.
5. Videos for Person 3: "D", "B".
6. Frequencies: {"D": 1, "B": 1}.
7. Sort by freq (1), then alphabetically: "B", "D". Result: ["B", "D"].

Common mistakes candidates make

• Level Management: Not processing the BFS queue level-by-level correctly, leading to mixing friends from different levels.
• Re-visiting Friends: Forgetting the visited set, which causes infinite loops or incorrectly placing a Level 1 friend into the Level 3 bucket because of a cycle.
• Sorting Logic: Implementing the custom sort incorrectly, especially the tie-breaker rule (alphabetical sorting).

Interview preparation tip

When BFS requires stopping at a specific level, always use a for loop inside your while(queue) loop that runs exactly queue.size() times. This perfectly captures all nodes at the current depth before moving to the next.