How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding 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 Coding 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.

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.

Input: (2, 2, [[0, 1], [1, 0]])

Expected Output: [0, 1]

Explanation: Users split 1-1 on songs 0 and 1, so count_pref is exactly half (2*1==2==n). The tie is broken by x<y, so song 0 beats song 1. Beat counts [1,0].

Input: (1, 1, [[0]])

Expected Output: [0]

Explanation: Single song, single user. No pairs to compare; the only song is returned.

Input: (4, 3, [[0, 1, 2], [1, 2, 0], [2, 0, 1], [0, 2, 1]])

Expected Output: [0, 1, 2]

Explanation: Beat counts work out to [2,1,0]: song 0 beats both others, song 1 beats song 2, song 2 beats none. Final order 0,1,2.

Input: (2, 4, [[3, 2, 1, 0], [3, 2, 1, 0]])

Expected Output: [3, 2, 1, 0]

Explanation: Both users share the identical ranking, so every pairwise comparison is unanimous. Beat counts [0,1,2,3] for songs 0..3, producing the reversed order 3,2,1,0.

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.

Quick Overview

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.