How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Confluent.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Confluent during technical interviews.

Rank songs by pairwise user preferences | Confluent Interview Question

Q: Rank songs by pairwise user preferences

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. 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:

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).
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).