Minimum Number of People to Teach

Minimum Number of People to Teach

1. What is this problem about?

The "Minimum Number of People to Teach" problem describes a scenario where a group of users speaks various languages, and there are friendship connections between them. A pair of friends can communicate if they share at least one common language. If they don't, you need to teach one or both of them a new language. The goal is to choose one language and teach it to the minimum number of people so that all current friendship pairs that cannot communicate will be able to do so using that single chosen language.

2. Why is this asked in interviews?

Companies like Amazon and Bloomberg use this problem to evaluate a candidate's ability to process relational data and apply greedy strategies. It requires handling multiple sets of data—user languages and friendship pairs—and identifying which friendships are "broken" (cannot communicate). The problem tests your skills in set operations, hash tables, and efficient iteration over constraints.

3. Algorithmic pattern used

The primary algorithmic pattern here is Greedy combined with Hash Tables. Since the goal is to find the minimum number of people to teach, you should focus only on the people involved in "broken" friendships. You iterate through each possible language, calculate how many people in those broken friendships don't speak it, and pick the language that yields the smallest count.

4. Example explanation

Suppose we have 3 users:

• User 1: {English}
• User 2: {French}
• User 3: {Spanish} Friendships: (1, 2) and (2, 3). None of these friends share a language.
• If we teach English: User 2 and User 3 need to learn it (2 people).
• If we teach French: User 1 and User 3 need to learn it (2 people).
• If we teach Spanish: User 1 and User 2 need to learn it (2 people). The minimum number of people to teach is 2.

5. Common mistakes candidates make

A common error is trying to teach multiple languages or overcomplicating the logic by including people who are already in "working" friendships. You only need to fix the broken ones. Another mistake is forgetting that if a person is part of multiple broken friendships, they only need to be taught the language once. Failing to use a set to track these unique individuals can lead to incorrect counts.

6. Interview preparation tip

When faced with set-based problems, always consider using bitmasks if the number of elements (like languages) is small. However, for this specific problem, a standard hash set is more intuitive. Practice identifying which parts of a dataset are actually relevant to the constraint—in this case, only the users in non-communicating friendships.