Count Connected Groups in a Relationship Matrix

Question

The question asks the candidate to count the number of connected groups in a relationship matrix, where each group represents individuals that are directly or indirectly connected.

Codemia · Accepted Answer

To count the number of connected groups in a relationship matrix, we can treat the matrix as an undirected graph where each person is a node and a relationship represents an edge. The goal is to traverse the graph and count how many distinct connected components exist.

We can use either Depth-First Search (DFS) or Breadth-First Search (BFS) to explore the graph. Here's a simple outline of the algorithm:
1. Initialize a visited array to keep track of visited nodes.
2. Iterate through each node in the matrix.
3. If a node has not been visited, perform a DFS/BFS starting from that node, marking all reachable nodes as visited.
4. Each time we start a new DFS/BFS from an unvisited node, we increment our connected group count.

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 (relationships). The space complexity is O(V) due to the visited array and the recursion stack (in case of DFS).

Here is a Python implementation of the above approach:
```python
def count_connected_groups(matrix):
    def dfs(node):
        for neighbor in range(len(matrix)):
            if matrix[node][neighbor] == 1 and not visited[neighbor]:
                visited[neighbor] = True
                dfs(neighbor)

visited = [False] * len(matrix)
    group_count = 0

for i in range(len(matrix)):
        if not visited[i]:
            visited[i] = True
            dfs(i)
            group_count += 1

return group_count
```
This function takes a relationship matrix as input and returns the count of connected groups.

When implementing this solution, consider edge cases such as an empty matrix (no relationships) or a matrix where everyone is connected (one large group). These cases will help ensure the robustness of your solution.

Count Connected Groups in a Relationship Matrix

Visa

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Visa 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