Videos at a Friendship Distance

Medium

A social network has n people numbered 0 to n - 1. watched[i] lists the videos person i has watched, and friends[i] lists their friends (friendship goes both ways). The distance between two people is the smallest number of friend-to-friend hops needed to get from one to the other. Your friends are at distance 1, friends of friends who aren't your friends are at distance 2, and so on. For person, gather every video watched by people at exactly distance from them and count how many times each video appears. Return the distinct videos sorted by count, lowest first, breaking ties alphabetically.

Example 1

watched=[["news", "jazz"], ["jazz"], ["film", "news"], ["film"]], friends=[[1], [0, 2], [1, 3], [2]], person=0, distance=2 → ['film', 'news']

The friends form a chain 0–1–2–3. Only person 2 is at distance 2 from person 0; they watched film and news once each, and equal counts go in alphabetical order.

Example 2

watched=[["news", "jazz"], ["jazz"], ["film", "news"], ["film"]], friends=[[1], [0, 2], [1, 3], [2]], person=1, distance=1 → ['film', 'jazz', 'news']

The direct friends of person 1 are 0 and 2. news shows up twice, film and jazz once each, so news comes last.

Constraints

2 ≤ n ≤ 100, len(watched) == len(friends) == n
1 ≤ len(watched[i]) ≤ 100
1 ≤ len(watched[i][j]) ≤ 20
0 ≤ friends[i][j] < n, nobody is their own friend, no repeats within a list
if j is in friends[i], then i is in friends[j]
0 ≤ person < n
1 ≤ distance < n

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Graph Array Hash Table Sorting

Similar problems

Merge Contact Cards Medium Rearrange Through Links Medium Rooms Open from the Hall Medium Expand a Template With Variables Medium Groups Linked by Shared Tags Medium

Input

watched=[["news", "jazz"], ["jazz"], ["film", "news"], ["film"]], friends=[[1], [0, 2], [1, 3], [2]], person=0, distance=2

Expected

['film', 'news']

Run checks the first 3 tests in your browser. Submit checks all 51 tests on the server, hidden ones included.