How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Determine Threshold-Constrained Connectivity

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given an undirected weighted graph with `n` nodes labeled from `0` to `n - 1` and a list of edges, where each edge is represented as `(u, v, w)` meaning there is an edge between nodes `u` and `v` with weight `w`. You are also given multiple queries. Each query is represented as `(a, b, k)`. For each query, determine whether there exists a path from node `a` to node `b` such that **every edge on the path has weight greater than or equal to `k`**. Return a list of boolean values, where the `i`-th value indicates whether such a path exists for the `i`-th query.

Quick Answer: This question evaluates understanding of graph algorithms and constrained connectivity, testing skills in reasoning about weighted undirected graphs, path feasibility under edge-weight thresholds, and efficient query processing.

You are given an undirected weighted graph with n nodes labeled from 0 to n - 1 and a list of edges. Each edge is represented as (u, v, w), meaning there is an undirected edge between u and v with weight w. You are also given multiple queries. Each query is represented as (a, b, k). For each query, determine whether there exists a path from node a to node b such that every edge on that path has weight greater than or equal to k. Return a list of boolean values in the same order as the queries. The i-th result should be True if such a path exists for the i-th query, otherwise False. A node is always considered reachable from itself, even without using any edges.

Constraints

1 <= n <= 200000
0 <= len(edges) <= 200000
0 <= len(queries) <= 200000
0 <= u, v, a, b < n
-10^9 <= w, k <= 10^9
The graph is undirected and may contain multiple edges between the same pair of nodes

Examples

Input: (5, [(0, 1, 4), (1, 2, 3), (2, 3, 5), (3, 4, 2), (0, 4, 1)], [(0, 2, 3), (0, 4, 3), (1, 3, 4), (0, 4, 1)])

Expected Output: [True, False, False, True]

Explanation: For threshold 3, nodes 0 and 2 are connected through 0-1-2. Node 4 is not reachable from 0 with threshold 3. With threshold 4, nodes 1 and 3 are separated. With threshold 1, all edges are allowed, so 0 and 4 are connected.

Input: (4, [(0, 1, 10), (1, 2, 8), (0, 2, 6), (2, 3, 6)], [(0, 3, 7), (0, 3, 6), (3, 3, 100), (1, 2, 9)])

Expected Output: [False, True, True, False]

Explanation: With threshold 7, node 3 is isolated. With threshold 6, all edges are usable and 0 can reach 3. A node is always reachable from itself, so (3, 3, 100) is True. With threshold 9, edge (1, 2, 8) cannot be used, so 1 and 2 are not connected.

Input: (3, [], [(0, 1, 0), (2, 2, 5)])

Expected Output: [False, True]

Explanation: With no edges, different nodes cannot be connected, but a node is still reachable from itself.

Input: (3, [(0, 1, 2), (0, 1, 5), (1, 2, 4)], [(0, 2, 5), (0, 2, 4), (0, 1, 3)])

Expected Output: [False, True, True]

Explanation: For threshold 5, only the edge (0, 1, 5) is usable, so 2 is unreachable. For threshold 4, edges (0, 1, 5) and (1, 2, 4) form a valid path from 0 to 2. For threshold 3, 0 and 1 are connected.

Hints

For a fixed threshold k, only edges with weight >= k are usable. What happens if you process queries from larger k to smaller k?
Use a Disjoint Set Union (Union-Find) structure to maintain connected components as you add eligible edges.

Quick Overview

This question evaluates understanding of graph algorithms and constrained connectivity, testing skills in reasoning about weighted undirected graphs, path feasibility under edge-weight thresholds, and efficient query processing.