To solve this problem, we can perform a BFS from the given user's id to identify friends up to the specified level. Then, we collect all the videos watched by these friends, count their frequencies, and sort them in ascending order. If frequencies are the same, the videos are sorted alphabetically.
Problem Statement
In this problem, you are given two arrays: watchedVideos and friends. watchedVideos[i] is the list of videos watched by person i, and friends[i] is the list of friends for person i. You are also given a specific person’s id and a level, representing the number of hops away from the id that friends should be considered.
The task is to find the list of videos watched by the friends of the specified person up to the given level. The videos should be ordered by their frequency of appearance, in increasing order. If multiple videos have the same frequency, they should be ordered alphabetically.
Examples
Example 1
Input: watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1
Output: ["B","C"]
You have id = 0 (green color in the figure) and your friends are (yellow color in the figure): Person with id = 1 -> watchedVideos = ["C"] Person with id = 2 -> watchedVideos = ["B","C"] The frequencies of watchedVideos by your friends are: B -> 1 C -> 2
Example 2
Input: watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2
Output: ["D"]
You have id = 0 (green color in the figure) and the only friend of your friends is the person with id = 3 (yellow color in the figure).
Constraints
- n == watchedVideos.length == friends.length
- 2 <= n <= 100
- 1 <= watchedVideos[i].length <= 100
- 1 <= watchedVideos[i][j].length <= 8
- 0 <= friends[i].length < n
- 0 <= friends[i][j] < n
- 0 <= id < n
- 1 <= level < n
- if friends[i] contains j, then friends[j] contains i
Solution Approach
Breadth-First Search (BFS)
Use BFS to find all friends at the specified level. Start from the given user's id, and explore their friends in levels. Collect the friends at the given level and gather the videos they have watched.
Count Video Frequencies
Once the relevant friends are found, count the frequency of each video they watched using a hash map. This allows us to efficiently track how often each video appears among the friends.
Sorting the Videos
Sort the collected videos first by their frequency, then alphabetically. This ensures that the output meets the problem's requirement of sorted videos.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n * m), where n is the number of people and m is the average number of videos watched by each person. BFS takes O(n) time, and counting frequencies and sorting the videos takes additional time proportional to the number of videos.
What Interviewers Usually Probe
- Strong understanding of graph traversal algorithms like BFS is demonstrated.
- Clear understanding of hash tables to track video frequencies.
- Proper implementation of sorting with multiple criteria (frequency, then lexicographically).
Common Pitfalls or Variants
Common pitfalls
- Misunderstanding the BFS algorithm and incorrectly calculating the level of friends.
- Failing to correctly count the frequency of videos watched by friends at the right level.
- Not sorting the videos in both frequency order and lexicographically for ties.
Follow-up variants
- Find videos watched by friends up to a different level (e.g., level 3).
- Return the result sorted by different criteria, such as descending frequency.
- Optimize the solution for larger inputs, handling the constraints more efficiently.
How GhostInterview Helps
- Guides you through the process of implementing BFS for graph traversal and managing video collections effectively.
- Assists in optimizing your approach to count video frequencies and implement sorting.
- Clarifies common pitfalls such as misunderstanding level calculations or sorting errors.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
How do I approach solving the "Get Watched Videos by Your Friends" problem?
Start by applying BFS to identify friends at the given level, then count the frequencies of their watched videos, and finally sort the results as required.
What data structures should I use for the "Get Watched Videos by Your Friends" problem?
Use a hash table to count video frequencies and a queue for BFS to track levels of friends.
What is the time complexity of the "Get Watched Videos by Your Friends" problem?
The time complexity is O(n * m), where n is the number of people and m is the average number of videos watched.
How does BFS help in solving the "Get Watched Videos by Your Friends" problem?
BFS helps find all friends up to the given level, ensuring you correctly explore the social network at the specified depth.
What are some common mistakes when solving the "Get Watched Videos by Your Friends" problem?
Common mistakes include miscalculating friend levels, failing to count video frequencies correctly, or sorting videos incorrectly.
Need direct help with Get Watched Videos by Your Friends instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Get Watched Videos by Your Friends from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the lexicographically smallest string by swapping characters in given pairs of indices.
Open problem page#928 Minimize Malware Spread IIMinimize Malware Spread II asks to minimize the spread of malware in a network of nodes by removing one infected node.
Open problem page#924 Minimize Malware SpreadIdentify which single infected node to remove to minimize total malware spread in a connected network graph efficiently.
Open problem page