We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Get Watched Videos by Your Friends

Number: 1436

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a group of people where each person has a list of watched videos and a list of friends, determine the list of videos watched at a specific friendship level starting from a given person id. Level 1 consists of direct friends, level 2 of friends of friends, and so on. The returned video list should be sorted by frequency (increasing order) and lexicographically if frequencies are equal.

Key Insights

  • Utilize Breadth-First Search (BFS) to traverse the friendship graph starting from the given person.
  • Track visited persons to avoid cycles in the graph.
  • Stop the BFS once the target friendship level is reached.
  • Count the frequency of each video from persons at the target level.
  • Sort the videos first by frequency and then alphabetically.

Space and Time Complexity

Time Complexity: O(n + m + k log k), where n is the number of persons, m is the number of friendship relationships, and k is the number of unique videos at the target level.
Space Complexity: O(n + v), where n is for BFS queues and visited tracking, and v is for storing video frequency counts.

Solution

We perform a BFS starting from the given person id to the required level, recording each person encountered at that level. Next, we count the frequency of each video that has been watched by these persons. Finally, we return the videos sorted by their frequency (in increasing order) and then by lexicographic order if there is a tie. The solution uses a queue for BFS, a set (or boolean array) for visited nodes, and a hash table (or dictionary/map) for counting video frequencies.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java.

from collections import deque, defaultdict

def watchedVideosByFriends(watchedVideos, friends, id, level):
    # Initialize BFS with starting id
    visited = set([id])
    queue = deque([id])
    current_level = 0
    
    # Perform BFS until we reach the desired level
    while queue and current_level < level:
        level_size = len(queue)
        for _ in range(level_size):
            person = queue.popleft()
            for friend in friends[person]:
                if friend not in visited:
                    visited.add(friend)
                    queue.append(friend)
        current_level += 1
    
    # Count video frequencies from persons at the target level
    video_count = defaultdict(int)
    for person in queue:
        for video in watchedVideos[person]:
            video_count[video] += 1

    # Sort videos by frequency and then lexicographically
    result = sorted(video_count.keys(), key=lambda x: (video_count[x], x))
    return result

# Example usage:
watchedVideos = [["A","B"], ["C"], ["B","C"], ["D"]]
friends = [[1,2], [0,3], [0,3], [1,2]]
print(watchedVideosByFriends(watchedVideos, friends, 0, 1))
← Back to All Questions