Graph Connectivity With Threshold

Graph Connectivity With Threshold

What is this problem about?

The Graph Connectivity With Threshold interview question asks you to determine if there is a path between various pairs of nodes in a graph. The graph consists of nodes numbered from $1$ to $n$. Two nodes $u$ and $v$ share an undirected edge if and only if they share a common divisor strictly greater than a given threshold. You are given an array of queries [u, v], and for each query, you must return a boolean indicating if $u$ and $v$ are connected.

Why is this asked in interviews?

Uber asks this Hard difficulty Math and Graph problem to test a candidate's mastery of the Union Find (Disjoint Set) data structure combined with Number Theory. A brute-force approach (checking the GCD of every possible pair to build the graph) takes $O(n^2)$, which is too slow. It evaluates if you can use the Sieve of Eratosthenes concept to build the graph connections in $O(n \log n)$ time.

Algorithmic pattern used

This problem uses Union Find with Multiples (Sieve Pattern).

1. Initialize a Union Find structure for nodes 1 to $n$.
2. Iterate through all possible divisors $z$ starting from threshold + 1 up to $n$.
3. For each divisor $z$, you know that all its multiples ($z, 2z, 3z, 4z \dots$) share the common divisor $z$ (which is $>$ threshold).
4. Union all these multiples together (e.g., union(z, 2z), union(2z, 3z)).
5. After building the connected components, answer each query in $O(1)$ time by checking if find(u) == find(v).

Example explanation

n = 6, threshold = 2.

1. Valid divisors to check: $z \ge 3$.
2. Check $z = 3$: Multiples are 3, 6. union(3, 6). (Nodes 3 and 6 are now connected).
3. Check $z = 4$: Multiples are 4. (Nothing to union).
4. Check $z = 5$: Multiples are 5. (Nothing to union).
5. Check $z = 6$: Multiples are 6. (Nothing to union). If a query asks [3, 6], they have the same root. Return True. If a query asks [1, 5], they have different roots. Return False.

Common mistakes candidates make

• $O(N^2)$ Edge Building: Trying to check gcd(i, j) > threshold for every pair $(i, j)$. This results in a Time Limit Exceeded (TLE) error.
• Inefficient Union Find: Not implementing path compression and union by rank/size, which slows down the find operations.
• Threshold Boundary: Starting the divisor loop at threshold instead of threshold + 1.

Interview preparation tip

Whenever a problem involves connecting numbers based on common divisors, immediately think of iterating over divisors and grouping their multiples. It's the most efficient way to build such "math-based" graphs.