Count Pairs of Connectable Servers in a Weighted Tree Network

Count Pairs of Connectable Servers in a Weighted Tree Network

What is this problem about?

The "Count Pairs of Connectable Servers in a Weighted Tree Network interview question" is a graph problem focused on topological properties and paths. You are given an undirected weighted tree representing a network of servers. Two servers $a$ and $b$ are "connectable" through a central server $c$ if $c$ lies on the unique path between $a$ and $b$, and the distances from $c$ to $a$ and $c$ to $b$ are both divisible by a given signalSpeed. Your goal is to find, for every server in the network, how many pairs of distinct servers it can connect.

Why is this asked in interviews?

Companies like UBS and Thoughtspot use the "Count Pairs of Connectable Servers coding problem" to evaluate a candidate's mastery of tree traversals and combinatorics. It requires understanding that in a tree, any node can be treated as a "root" to analyze its subtrees. It tests your ability to perform efficient "Depth-First Search interview pattern" explorations and apply the "Product Rule" of counting to independent sub-groups of nodes.

Algorithmic pattern used

This problem follows the Tree DFS and Combinatorial Counting patterns.

1. Root Centricity: For each node i in the tree, treat it as the central server.
2. Subtree Exploration: Perform a DFS from i into each of its direct neighbors.
3. Distance Calculation: During DFS, count how many nodes in that specific subtree have a distance from node i that is divisible by signalSpeed.
4. Pairing: If node i has multiple subtrees, the number of pairs it connects is the sum of products of the counts from different subtrees (e.g., if subtrees have $x, y, z$ valid nodes, the total pairs for that root are $x \cdot y + x \cdot z + y \cdot z$).
5. Optimization: Maintain a running total of valid nodes seen so far to compute the products in linear time for each root.

Example explanation

Suppose node 0 is connected to node 1 (weight 2) and node 2 (weight 4), and signalSpeed = 2.

• Treating node 0 as root:
  • Subtree via neighbor 1: Node 1 is at distance 2 (valid). Count = 1.
  • Subtree via neighbor 2: Node 2 is at distance 4 (valid). Count = 1.
• Total pairs for node 0: $1 imes 1 = 1$. The only connectable pair through 0 is (1, 2).

Common mistakes candidates make

• Treating it as a general graph: Forgetting that trees have a unique path between any two nodes, which simplifies the "lying on the path" condition to just "being in different subtrees."
• Recalculating distances: Using an $O(N^2)$ distance matrix instead of performing a fresh DFS for each candidate central server.
• Double counting: Counting the pair $(a, b)$ and $(b, a)$ as distinct when the problem asks for unique pairs.

Interview preparation tip

Practice "Root-Change" or "Centroid" style tree problems. The ability to visualize a tree from the perspective of any node is a vital "Tree interview pattern" skill. Also, brush up on counting principles—specifically how to count pairs from distinct sets.