Popularity Ranking of Songs - Expedia Online Assessment

Problem Preview

"A music streaming platform wants to rank songs based on user preferences. There are **n** users and **m** songs. Each user provides a preference list `pref[i]`, which is a permutation of song IDs from `0` to `m - 1`. If `a < b`, then user `i` prefers song `pref[i][a]` over song `pref[i][b]`. A song ranking is determined using the following rules: 1. **Song `x` beats song `y` if:** * More than half of the users prefer `x` over `y`, or * Exactly half of the users prefer `x` over `y`, and `x < y`. 2. **Song `x` is more popular than song `y` if `x` beats more songs than `y`.** 3. **If two songs beat the same number of songs, the song with the smaller ID ranks higher.** Return the song IDs sorted from **most popular** to **least popular**. --- ## Function Description Complete the function: ```cpp vector<int> getPopularityOrder(vector<vector<int>> song_preferences) ``` ### Parameters * `song_preferences[i]`: the preference list of the `i`-th user. ### Returns * `vector<int>`: the song IDs sorted in decreasing order of popularity. --- ## Example ``` n = 3 m = 3 song_preferences = [ [0, 1, 2], [0, 2, 1], [1, 2, 0] ] ``` ### User Preferences | User | Preference | | ---- | ---------- | | 0 | 0 > 1 > 2 | | 1 | 0 > 2 > 1 | | 2 | 1 > 2 > 0 | ### Pairwise Results * Song 0 beats Song 1. * Song 0 beats Song 2. * Song 1 beats Song 2. Number of songs beaten: | Song | Beats | | ---- | ----: | | 0 | 2 | | 1 | 1 | | 2 | 0 | ### Output ``` [0, 1, 2] ``` --- "