Rank Songs by Popularity
Expedia● MediumINTERNOAProblem statement
As part of enhancing a music streaming platform's user experience, implement a feature that ranks songs by their popularity. Given n users and m songs, each user i has a preference list, pref[i], which is a permutation of numbers 0 to m-1, indicating the user's preference for a song. If a < b, the user prefers song pref[i][a] over song pref[i][b].
To rank the songs, use the following approach. Song x is said to beat song y if x is preferred over y by more than half of the users or if exactly half of the users prefer x over y, and x has a smaller id. Song x is considered more popular than song y if x beats more songs than y. If x and y beat the same number of songs, select the song with a lower id.
Function
rankSongsByPopularity(n: int, m: int, pref: int[][]) → int[]Examples
Example 1
n = 3m = 3pref = [[0, 1, 2], [0, 2, 1], [1, 2, 0]]return = [0, 1, 2]User Song Preference 0 Song 0 > Song 1 > Song 2 1 Song 0 > Song 2 > Song 1 2 Song 1 > Song 2 > Song 0
Comparisons: Song Pair Users who prefer Song 0 > Song 1 0, 1 Song 0 > Song 2 0, 1 Song 1 > Song 2 0, 2
It is established that Song 0 > Song 1 > Song 2. Hence the answer is [0, 1, 2].
Constraints
🐭