Count Connected Clusters of Two-Dimensional Points

Question

The question asks the candidate to implement an algorithm that counts the number of connected clusters formed by a set of two-dimensional points.

Codemia · Accepted Answer

To count the connected clusters of points, we can treat each point as a node in a graph and create edges between points that are directly connected. We can use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all connected points starting from any unvisited point, marking them as visited. Each time we start a new DFS/BFS from an unvisited point, we increment our cluster count.

1. Initialize a set to keep track of visited points.
2. Define a helper function for DFS/BFS that will explore all connected points from a given starting point.
3. Loop through each point in the list:
   - If the point is unvisited, call the DFS/BFS function and increment the cluster count.
4. Return the total count of clusters.

Here is a Python implementation:
```python
def count_clusters(points):
    visited = set()
    def dfs(point):
        stack = [point]
        while stack:
            p = stack.pop()
            for neighbor in get_neighbors(p):
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)

cluster_count = 0
    for point in points:
        if point not in visited:
            visited.add(point)
            dfs(point)
            cluster_count += 1
    return cluster_count
```

The time complexity of this algorithm is O(N), where N is the number of points, since we visit each point once. The space complexity is O(N) as well, due to the storage of the visited set and the recursion stack (in case of DFS). This makes the algorithm efficient for reasonably sized datasets.

It is important to consider edge cases such as:
- Points that are exactly the same (duplicates).
- Points that are far apart and should not be connected.
- An empty list of points, which should return 0 clusters. These cases should be handled in the implementation to ensure robustness.

Interviewers are looking for a clear understanding of how to approach the problem, the ability to write clean and efficient code, and the capability to analyze the solution's performance. They also appreciate candidates who can discuss potential improvements and edge cases, demonstrating a comprehensive understanding of the problem.

Count Connected Clusters of Two-Dimensional Points

Google

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

Google 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