Count Connected Friend Groups

Question

This question asks the candidate to implement a solution to count the number of connected friend groups in a social network represented as a graph.

Codemia · Accepted Answer

To solve the problem of counting connected friend groups, we can represent the social network as an undirected graph where each person is a node and each friendship is an edge. Our goal is to find all connected components in this graph, where each connected component represents a friend group.

We can use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore the graph. Starting from an unvisited node, we will traverse all reachable nodes, marking them as visited. Each time we initiate a new traversal from an unvisited node, we increment our friend group count.

Here is a Python implementation using DFS:

```python
def count_friend_groups(friends):
    def dfs(person):
        stack = [person]
        while stack:
            current = stack.pop()
            for neighbor in friends[current]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)

visited = set()
    group_count = 0
    for person in friends:
        if person not in visited:
            dfs(person)
            group_count += 1
    return group_count
```
This function takes a dictionary where keys are people and values are lists of their friends.

The time complexity of this algorithm is O(V + E), where V is the number of vertices (people) and E is the number of edges (friendships). This is because we visit each node and edge exactly once. The space complexity is O(V) due to the storage of the visited set and the stack used in DFS.

We should consider edge cases such as an empty graph (no people), which should return 0 groups, or a graph where each person has no friends, which should return the number of people as the number of groups. Testing these scenarios ensures our solution is robust.

Count Connected Friend Groups

OpenAI

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Framing

Approach

Submit Your Answer

OpenAI Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string