Checking Existence of Edge Length Limited Paths

Checking Existence of Edge Length Limited Paths

What is this problem about?

You are given an undirected graph with weighted edges and a set of queries. Each query consists of two nodes $(u, v)$ and a weight limit $L$. You need to determine if there is a path between $u$ and $v$ such that every edge on the path has a weight strictly less than $L$. This is a "Hard" problem because there can be many queries with different limits.

Why is this asked in interviews?

Google asks this to test your ability to use "Offline Query Processing" and the Union Find data structure. The key is to realize that if you sort both the edges and the queries by weight, you can build the graph incrementally and answer queries without repeating work. It evaluates your skill in optimizing graph connectivity problems.

Algorithmic pattern used

This problem uses the Union Find (Disjoint Set Union) pattern with an Offline Processing strategy. You sort the edges by weight and the queries by their weight limit. You iterate through the sorted queries. For each query, you add all edges from the sorted edge list that have a weight less than the query's limit to the Union Find structure. Then, you use find(u) == find(v) to answer the query.

Example explanation

Edges: (0-1, w:3), (1-2, w:5), (0-2, w:10) Queries: Q1(0, 2, L:6), Q2(0, 2, L:4)

1. Sort Edges: [(0-1, 3), (1-2, 5), (0-2, 10)]
2. Sort Queries: [Q2(L:4), Q1(L:6)]
3. For Q2 (L:4): Add edge (0-1, 3). 0 and 2 are not connected. Result: False.
4. For Q1 (L:6): Add edge (1-2, 5). Now 0-1-2 are connected. Result: True.

Common mistakes candidates make

The most common mistake is trying to solve each query independently using BFS or DFS, which results in $O(Q imes E)$ complexity and Time Limit Exceeded. Another error is forgetting to sort the queries while keeping track of their original indices so you can return the answers in the correct order.

Interview preparation tip

"Offline Processing" is a powerful technique for query-based problems. If you have many queries, ask yourself: "Can I sort the queries to make the problem easier?" Sorting by a constraint (like time or weight) often allows you to use a simpler data structure.