Maximum Employees to Be Invited to a Meeting

Maximum Employees to Be Invited to a Meeting

1. What is this problem about?

The Maximum Employees to Be Invited to a Meeting coding problem is a complex graph-based challenge. You are given a list of employees, where each employee has exactly one person they 'favorite'. You want to invite the maximum number of people to a round table such that every invited person sits next to their favorite person. This involves analyzing functional graphs where each node has exactly one outgoing edge.

2. Why is this asked in interviews?

This Hard-level question is frequently asked by top-tier companies like Google and Microsoft because it requires a deep understanding of graph structures, specifically cycles and chains. It tests a candidate's ability to handle two distinct cases: large cycles where everyone sits in a ring, and small cycles of size 2 where chains of people can be added to both sides of the pair. It's a masterclass in Topological Sort and Depth-First Search (DFS).

3. Algorithmic pattern used

The problem uses Graph interview patterns, specifically cycle detection and Topological Sort. The graph is a collection of components, each containing exactly one cycle.

1. Case 1: A cycle of length > 2. The maximum number of people is simply the cycle length.
2. Case 2: A cycle of length 2 (A likes B, and B likes A). Here, you can attach the longest path (chain) ending at A and the longest path ending at B. Multiple such '2-cycle components' can be combined at the same table. Topological sort is used to find the longest paths leading into the cycles.

4. Example explanation

Imagine 4 people:

• Person 0 likes 1
• Person 1 likes 0
• Person 2 likes 0
• Person 3 likes 2 Here, 0 and 1 form a 2-cycle. We can also invite 2 (who likes 0) and 3 (who likes 2). So the table could be: 3 -> 2 -> 0 <-> 1. Total people: 4. If we had another separate cycle of 3 people (4 likes 5, 5 likes 6, 6 likes 4), we would compare the size 4 (from the 2-cycle + chains) with size 3 and pick 4.

5. Common mistakes candidates make

The biggest mistake is failing to distinguish between the two cases (large cycles vs. 2-cycles with chains). Candidates often try to find the longest path in the entire graph, but a round table requires specific adjacency. Another common error is not summing up the results of all 2-cycle components, while only taking the maximum of the larger cycles.

6. Interview preparation tip

Practice identifying 'Functional Graphs' (where each node has out-degree 1). They always consist of components with exactly one cycle. Understanding how to use Kahn's algorithm (Topological Sort) to 'peel away' the nodes that aren't part of a cycle is a vital skill for these types of problems.