Count Servers that Communicate

Count Servers that Communicate

What is this problem about?

The "Count Servers that Communicate interview question" is a grid connectivity problem. You are given an $m imes n$ matrix representing a server map, where 1 means a server is present and 0 means it is not. Two servers can communicate if they are in the same row or the same column. You need to count the total number of servers that can communicate with at least one other server.

Why is this asked in interviews?

Meta, Oracle, and Google ask the "Count Servers that Communicate coding problem" to evaluate a candidate's ability to optimize a grid-based search. While you could use BFS or DFS, the problem can be solved much more efficiently using linear row and column counts. it tests "Array interview pattern" skills and the ability to find a minimal representation of grid properties.

Algorithmic pattern used

This problem is best solved using Row and Column Frequency Counting.

1. Pre-calculation: Create two arrays, rowCount of size $m$ and colCount of size $n$.
2. First Pass: Traverse the matrix. For every cell $(r, c)$ that contains a 1, increment rowCount[r] and colCount[c].
3. Second Pass: Traverse the matrix again. For every server at $(r, c)$:
   • Check if rowCount[r] > 1 OR colCount[c] > 1.
   • if either is true, the server can communicate. Increment the final count. This approach is $O(M imes N)$ time and $O(M + N)$ space.

Example explanation

Grid:

1 0
1 1

• Row counts: row0=1, row1=2.
• Col counts: col0=2, col1=1. Check servers:
• (0,0): row0=1, col0=2. communicating!
• (1,0): row1=2, col0=2. communicating!
• (1,1): row1=2, col1=1. communicating! Result: 3 servers.

Common mistakes candidates make

• Over-counting: Counting a pair of servers twice or counting "communication paths" instead of the number of servers.
• Inefficient Search: Using DFS/BFS for every server found, which is unnecessary since communication is strictly along rows and columns.
• Ignoring Connectivity: Only checking if there's one other server in the row, but forgetting to check the column.

Interview preparation tip

For grid problems where connectivity is based strictly on row/column alignment, avoid complex graph traversals. Use frequency arrays to store the "server density" of each axis. This is a common "Matrix interview pattern" optimization.