Rank songs by pairwise user preferences
Song Popularity Ranking
You are tasked with ranking m songs based on the collective preferences of n users. Each song is identified by an integer ID from 0 to m - 1.
For each user i (0-indexed), you are provided with a preference list pref[i]. This list is an array of length m and represents a permutation of [0, 1, ..., m-1]. The order within pref[i] signifies user i's preference: if song a appears before song b in pref[i], then user i prefers song a over song b.
Using these individual user preferences, you need to define and compute the following:
1. Song X Beats Y
A song x is considered to "beat" another song y based on the following rules:
- Let
count_pref_xbe the total number of users who prefer songxover songy. - Song
xbeats songyif either:count_pref_xis strictly greater than half of the total number of users (i.e.,count_pref_x > n / 2), ORcount_pref_xis exactly half of the total number of users (i.e.,count_pref_x * 2 == n) AND songxhas a smaller ID than songy(i.e.,x < y).
2. Song X is More Popular Than Y
The popularity of a song is determined by its "beat count".
- For each song, its beat count is defined as the number of distinct other songs it beats according to the rule defined in (1).
- Song
xis considered "more popular" than songyif either:- The beat count of
xis greater than the beat count ofy, OR - Their beat counts are equal AND song
xhas a smaller ID than songy(i.e.,x < y).
- The beat count of
Task
Given the total number of users n, the total number of songs m, and all user preference lists pref[0..n-1], your task is to compute the popularity ranking of all songs.
Return a list of all song IDs, ordered from the most popular to the least popular, according to the "more popular than" relation defined above.
Assumptions
1 <= m <= M_maxand1 <= n <= N_max. You should choose reasonable constraints forM_maxandN_maxif implementing this solution.- All
pref[i]arrays are guaranteed to be valid permutations of[0, ..., m-1].
Your final output should be an array of length m containing the song IDs in descending order of popularity. Ties in popularity (equal beat counts) should be broken by preferring the song with the smaller ID.
AI interview prep
Core dilemma
The central engineering conflict is balancing the computational efficiency (time and space complexity) of processing pairwise preferences for all songs across all users, especially under large-scale data (large 'n' and 'm'), against the strict correctness requirements of the ranking rules and tie-breakers.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Rank songs by pairwise user preferences
Song Popularity Ranking
You are tasked with ranking m songs based on the collective preferences of n users. Each song is identified by an integer ID from 0 to m - 1.
For each user i (0-indexed), you are provided with a preference list pref[i]. This list is an array of length m and represents a permutation of [0, 1, ..., m-1]. The order within pref[i] signifies user i's preference: if song a appears before song b in pref[i], then user i prefers song a over song b.
Using these individual user preferences, you need to define and compute the following:
1. Song X Beats Y
A song x is considered to "beat" another song y based on the following rules:
- Let
count_pref_xbe the total number of users who prefer songxover songy. - Song
xbeats songyif either:count_pref_xis strictly greater than half of the total number of users (i.e.,count_pref_x > n / 2), ORcount_pref_xis exactly half of the total number of users (i.e.,count_pref_x * 2 == n) AND songxhas a smaller ID than songy(i.e.,x < y).
2. Song X is More Popular Than Y
The popularity of a song is determined by its "beat count".
- For each song, its beat count is defined as the number of distinct other songs it beats according to the rule defined in (1).
- Song
xis considered "more popular" than songyif either:- The beat count of
xis greater than the beat count ofy, OR - Their beat counts are equal AND song
xhas a smaller ID than songy(i.e.,x < y).
- The beat count of
Task
Given the total number of users n, the total number of songs m, and all user preference lists pref[0..n-1], your task is to compute the popularity ranking of all songs.
Return a list of all song IDs, ordered from the most popular to the least popular, according to the "more popular than" relation defined above.
Assumptions
1 <= m <= M_maxand1 <= n <= N_max. You should choose reasonable constraints forM_maxandN_maxif implementing this solution.- All
pref[i]arrays are guaranteed to be valid permutations of[0, ..., m-1].
Your final output should be an array of length m containing the song IDs in descending order of popularity. Ties in popularity (equal beat counts) should be broken by preferring the song with the smaller ID.