Rank songs by pairwise user preferences
Company: Confluent
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given preference rankings for `n` users over `m` songs. Each song is labeled from `0` to `m - 1`.
For each user `i` (0-indexed), you are given an array `pref[i]` of length `m` that is a permutation of `[0, 1, ..., m-1]`. This array represents user `i`'s ranking of all songs:
- If song `a` appears before song `b` in `pref[i]`, then user `i` prefers song `a` over song `b`.
Using these preference lists, define the following:
1. **Song x beats y**:
- Let `count_pref_x` be the number of users who prefer `x` over `y`.
- Song `x` beats song `y` if either:
- `count_pref_x` is strictly greater than half of all users (i.e., `count_pref_x > n / 2`), or
- `count_pref_x` is exactly half of all users (i.e., `count_pref_x * 2 == n`) **and** `x < y` (by song ID).
2. **Song x is more popular than y**:
- For each song, define its **beat count** as the number of *distinct* other songs it beats according to rule (1).
- Song `x` is more popular than song `y` if:
- The beat count of `x` is greater than the beat count of `y`, or
- The beat counts are equal and `x < y` (by song ID).
**Task**: Given `n`, `m`, and all preference lists `pref[0..n-1]`, compute the popularity ranking of all songs. Return a list of all song IDs from most popular to least popular, sorted by the `"more popular than"` relation defined above.
Assume:
- `1 <= m <= M_max`, `1 <= n <= N_max` (choose reasonable constraints if implementing).
- All `pref[i]` are valid permutations of `[0, ..., m-1]`.
Your function should output an array of length `m` containing the song IDs in descending order of popularity. Break ties using the song ID (smaller ID is considered more popular when beat counts are equal).
Quick Answer: This question evaluates the ability to aggregate pairwise user preferences, implement majority-based comparison rules with deterministic tie-breakers, and compute a global ranking via beat counts.
You are given preference rankings for `n` users over `m` songs, where songs are labeled `0` to `m - 1`.
For each user `i` (0-indexed), `pref[i]` is an array of length `m` that is a permutation of `[0, 1, ..., m-1]` representing that user's ranking: if song `a` appears before song `b` in `pref[i]`, user `i` prefers `a` over `b`.
Define the following relations:
**Song x beats y** — Let `count_pref_x` be the number of users who prefer `x` over `y`. Song `x` beats `y` if either:
- `count_pref_x * 2 > n` (a strict majority prefer `x`), or
- `count_pref_x * 2 == n` (exactly half) **and** `x < y` by song ID.
**Song x is more popular than y** — The **beat count** of a song is the number of distinct other songs it beats. Song `x` is more popular than `y` if `x`'s beat count is greater, or the beat counts are equal and `x < y`.
**Task:** Given `n`, `m`, and the preference lists `pref`, return an array of all `m` song IDs ordered from most popular to least popular. Break ties by smaller song ID.
Constraints
- 1 <= n (number of users)
- 1 <= m (number of songs)
- Each pref[i] is a permutation of [0, 1, ..., m-1]
- Song IDs are 0-indexed (0 to m-1)
Examples
Input: (3, 3, [[0, 1, 2], [0, 2, 1], [1, 0, 2]])
Expected Output: [0, 1, 2]
Explanation: Song 0 is preferred over both 1 and 2 by a majority (beats 2). Song 1 beats song 2. Beat counts [2,1,0] give order 0,1,2.
Input: (1, 3, [[2, 0, 1]])
Expected Output: [2, 0, 1]
Explanation: With a single user, x beats y whenever that user ranks x before y. The popularity order mirrors the single preference list: 2, 0, 1.
Hints
- Precompute, for each user, the position (rank index) of every song so you can answer 'does user i prefer x over y?' in O(1) by comparing positions.
- To decide if x beats y, count how many users place x before y; compare 2*count against n to handle strict-majority and exact-half cases without floating point. The exact-half case is broken by x < y.
- Once you have each song's beat count (number of distinct songs it beats), sort song IDs by (-beat_count, id) to order from most to least popular with ID as the tie-breaker.