When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach here means we will look at each person individually and see if they are unhappy. To determine if a person is unhappy, we will examine all possible alternative pairings they could have with others.
Here's how the algorithm would work step-by-step:
def count_unhappy_friends_brute_force(
number_of_friends,
pairs,
preference
):
unhappy_friends_count = 0
for friend_index in range(number_of_friends):
is_unhappy = False
partner_index = pairs[friend_index]
# Iterate through preferred friends to check unhappiness
for preferred_friend_index in preference[friend_index]:
if preferred_friend_index == partner_index:
break
partner_of_preferred_friend =
pairs[preferred_friend_index]
# Check if the preferred friend also prefers the current friend
for friend_in_preferred_friend_preference in \
preference[preferred_friend_index]:
if (friend_in_preferred_friend_preference ==
friend_index):
# If preferred friend prefers current friend and current friend prefers the preferred friend
# then mark current friend as unhappy
if friend_in_preferred_friend_preference !=
partner_of_preferred_friend:
is_unhappy = True
break
elif (friend_in_preferred_friend_preference ==
partner_of_preferred_friend):
break
if is_unhappy:
unhappy_friends_count += 1
break
return unhappy_friends_countThe problem asks us to find unhappy friends based on their preferences and pairings. The key is to directly check the conditions for unhappiness for each person, instead of exhaustively searching for unhappy pairs.
Here's how the algorithm would work step-by-step:
def count_unhappy_friends(number_of_friends, preferences, pairs):
paired_with = [0] * number_of_friends
for pair in pairs:
person1, person2 = pair
paired_with[person1] = person2
paired_with[person2] = person1
unhappy_count = 0
for person in range(number_of_friends):
for preferred_friend in preferences[person]:
# If the preferred friend is the current partner, move on
if preferred_friend == paired_with[person]:
break
preferred_friend_partner = paired_with[preferred_friend]
# Check if the preferred friend also prefers the person over their partner
for potential_better_match in preferences[preferred_friend]:
# If the potential match is their current partner, move on.
if potential_better_match == preferred_friend_partner:
break
# If the preferred friend prefers the person, the person is unhappy
if potential_better_match == person:
unhappy_count += 1
# Count each person only once
break
# Count each person only once
if unhappy_count > 0 and paired_with[person] in preferences[person]:
continue
return unhappy_count| Case | How to Handle |
|---|---|
| n = 1: Only one friend exists. | Return 0, as a single person cannot be unhappy since pairings require two people. |
| Empty 'preferences' or 'pairs' arrays. | Return 0 since without preferences or pairs, no unhappy friends can be determined. |
| preferences[i] is empty for some i. | Treat an empty preference list as if the friend prefers nobody, thereby having no unhappy friends due to that preference. |
| pairs contains duplicate pairs (e.g., [1, 2] and [2, 1]). | The algorithm should treat [1,2] and [2,1] as the same pairing, and the implementation should avoid double-counting or creating inconsistencies. |
| preferences[i] does not contain all other friends. | The algorithm should handle cases where not all friends are included in the preference list as if those missing friends are the least preferred. |
| A friend is paired with themselves (e.g., [x, x]). | The algorithm should handle this by appropriately not considering the friend to be unhappy in such a case as preference still exist toward others. |
| n is large, and the 'preferences' array has long lists for each friend. | The algorithm should be optimized to avoid excessive looping or copying of the 'preferences' data (e.g. use efficient lookup). |
| Friend index is out of range (e.g., an index >= n appears in 'preferences' or 'pairs'). | The algorithm should handle this by throwing an exception or treating as invalid data, and the interviewer should define what the correct behavior is. |