Count Pairs of Connectable Servers in a Weighted Tree Network
Asked at Rippling
Problem
Given a weighted tree with n servers (0 to n-1) and edges [a, b, weight], count for each server i the number of pairs (a, b) where a and b are in different branches of i, and the combined distance from i to a and i to b is divisible by signalSpeed.
Asked At
| Company | Difficulty | |
|---|---|---|
| Rippling | Medium | View all Rippling questions → |
How to Think About It
For each center server i, remove i to get a forest of subtrees. For each subtree, collect the distances from i to every node in that subtree, modulo signalSpeed.
Two nodes a and b are connectable through i if they are in different subtrees (different first-edge branches from i) and (dist(i,a) + dist(i,b)) % signalSpeed == 0.
Efficient counting: for each subtree, maintain a frequency array of (distance % signalSpeed). For each new subtree, count pairs with already-seen subtrees using the complement: seen[(signalSpeed - r) % signalSpeed] gives the count of nodes in previous subtrees where adding this node makes the sum divisible.
Visual walkthrough: i=0, signalSpeed=2, subtree1 has nodes with distances [1,3] (both odd -> mod 2 = 1), subtree2 has [2] (even -> mod 2 = 0). Pairs: (1,2) -> 1+0=1 (odd, not divisible). (3,2) -> 1+0=1 (not divisible). Answer for i=0: 0.
Algorithm for each center: DFS into each neighbor branch to collect distance mods. For each branch, count cross-branch pairs using the complement formula, then merge the branch into the seen set.
Total complexity: O(n^2) because for each of n centers, we do O(n) work (DFS + pair counting). This is acceptable since n <= 1000.
Optimal Approach
Step 1: Build adjacency list for the tree.
Step 2: For each server i (center):
a. For each neighbor j of i, DFS through j to collect distances from i. Build a frequency array of (distance % signalSpeed).
b. For each new subtree, count cross-branch pairs: for each remainder r in the subtree, add seen[(signalSpeed - r) % signalSpeed] to the answer.
c. Merge the subtree frequencies into the running seen set.
Step 3: Return the answers array.
Walkthrough for n=4, edges=[[0,1,3],[1,2,1],[1,3,4]], signalSpeed=2:
- Center 1: DFS into 0 (dist=3, mod=1), 2 (dist=1, mod=1), 3 (dist=4, mod=0).
- Subtree 0: mod 1 count=1. Pairs with seen: seen[1]=0. Total=0. Merge: seen[1]=1.
- Subtree 2: mod 1 count=1. Pairs with seen: seen[1]=1. Total+=1. Merge: seen[1]=2.
- Subtree 3: mod 0 count=1. Pairs with seen: seen[0]=0. Total+=0. Merge: seen[0]=1.
- Answer[1] = 1.
- Center 0: one subtree (via 1). No cross-branch pairs. Answer[0] = 0.
- Similarly for centers 2 and 3: answer = [0,1,0,0].
Time: O(n^2) - for each center, DFS is O(n) and pair counting is O(n). Space: O(n) for DFS recursion and frequency arrays.
What Trips People Up in Real Interviews
Counting pairs within the same subtree. Connectable pairs must be in DIFFERENT subtrees (different first-edge branches from i).
Forgetting that the tree is weighted. Distances are accumulated edge weights, not just hop counts. Use the actual weight when computing dist(i, child).
Wrong modular arithmetic. (dist_a + dist_b) % s == 0 means dist_a % s and dist_b % s are complements: (r_a + r_b) % s == 0.
Missing that the result is an array, not a single number. Each server i gets its own count of connectable pairs.
Double-counting pairs. Each pair (a,b) is counted once when processing center i. Do not count (a,b) and (b,a) separately.
Solution Code
class Solution:
def countPairsOfConnectableServers(self, edges, signalSpeed):
n = len(edges) + 1
g = [[] for _ in range(n)]
for a, b, w in edges:
g[a].append((b, w))
g[b].append((a, w))
def branch_counts(center):
counts = []
for v, w in g[center]:
cnt = [0] * signalSpeed
stack = [(v, center, w)]
while stack:
u, p, d = stack.pop()
cnt[d % signalSpeed] += 1
for nb, ww in g[u]:
if nb != p:
stack.append((nb, u, d + ww))
counts.append(cnt)
return counts
ans = [0] * n
for c in range(n):
seen = [0] * signalSpeed
for cnt in branch_counts(c):
for r in range(signalSpeed):
ans[c] += cnt[r] * seen[(signalSpeed - r) % signalSpeed]
for r in range(signalSpeed):
seen[r] += cnt[r]
return ansFrequently Asked Questions
What is the Count Pairs of Connectable Servers in a Weighted Tree Network problem?
Given a weighted tree with n servers (0 to n-1) and edges [a, b, weight], count for each server i the number of pairs (a, b) where a and b are in different branches of i, and the combined distance from i to a and i to b is divisible by signalSpeed.
How do you solve Count Pairs of Connectable Servers in a Weighted Tree Network?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Count Pairs of Connectable Servers in a Weighted Tree Network?
Count Pairs of Connectable Servers in a Weighted Tree Network is asked at Rippling. It is a medium difficulty problem.
What are common mistakes on Count Pairs of Connectable Servers in a Weighted Tree Network?
- Counting pairs within the same subtree. Connectable pairs must be in DIFFERENT subtrees (different first-edge branches from i).
- Forgetting that the tree is weighted. Distances are accumulated edge weights, not just hop counts. Use the actual weight when computing dist(i, child).
- Wrong modular arithmetic. (dist_a + dist_b) % s == 0 means dist_a % s and dist_b % s are complements: (r_a + r_b) % s == 0.
- Missing that the result is an array, not a single number. Each server i gets its own count of connectable pairs.
- Double-counting pairs. Each pair (a,b) is counted once when processing center i. Do not count (a,b) and (b,a) separately.