Count Unhappy Friends

Count Unhappy Friends

What is this problem about?

The Count Unhappy Friends interview question is a simulation-based problem that explores the dynamics of relationships and preferences within a group. You are given a group of $n$ friends, each with a ranked list of preferences for other friends. These friends are paired up into $n/2$ pairs. A person $x$ is considered "unhappy" if they were paired with $y$, but they actually prefer some person $u$ over $y$, AND that person $u$ also prefers $x$ over their own assigned partner $v$. The goal is to count how many such individuals exist in the current pairing configuration.

Why is this asked in interviews?

Bloomberg and other tech companies use the Count Unhappy Friends coding problem to assess a candidate's ability to handle multi-dimensional data structures and nested logic. It specifically tests how well you can translate complex English rules into efficient code. While it doesn't require advanced algorithms, it demands precise indexing and a clear understanding of the "Stable Marriage" concept in a simplified, non-bipartite setting.

Algorithmic pattern used

This problem primarily uses an Array and Simulation approach. To make the preference lookups efficient, a common Simulation interview pattern involves preprocessing the preference lists into a 2D matrix or a hash map. Instead of searching through a list each time to see if $x$ prefers $u$ over $y$, you can store the rank of each friend in a rank[x][u] matrix, where a smaller value indicates a higher preference.

Example explanation

Imagine four friends: 0, 1, 2, and 3.

• Preferences:
  • 0: [1, 2, 3]
  • 1: [3, 2, 0]
  • 2: [3, 1, 0]
  • 3: [1, 2, 0]
• Assigned pairs: (0, 1) and (2, 3). Friend 2 is paired with 3. However, looking at 2's list, 2 prefers 1 over 3. Now check friend 1: 1 is paired with 0, but 1 prefers 2 over 0. Since both 2 prefers 1 and 1 prefers 2 over their respective partners, friend 2 (and friend 1) are unhappy.

Common mistakes candidates make

• Overlooking Symmetry: Forgetting that if $x$ is unhappy because of $u$, $u$ might also be unhappy because of $x$. However, the question asks for the count of unhappy individuals, so you must count each person only once.
• Inefficient Searching: Performing a linear search on preference lists for every pair of friends, leading to O(n^3) complexity instead of the optimized O(n^2).
• Misinterpreting the Rule: Missing the second half of the condition—that the preferred person $u$ must also prefer $x$ over their own partner.

Interview preparation tip

Whenever a problem involves "preferences" or "rankings," try to convert those rankings into an O(1) lookup table immediately. Mapping friend_id to its index in a preference list is a standard trick to speed up comparison logic.