Checking Existence of Edge Length Limited Paths II

Checking Existence of Edge Length Limited Paths II

What is this problem about?

This is a more advanced version of the previous problem. In this "Hard" variation, you must answer queries "Online," meaning you cannot sort them beforehand. You need a data structure that can efficiently answer if a path between $(u, v)$ exists using only edges with weight less than $L$, even as queries come in one by one.

Why is this asked in interviews?

Google and Oscar Health use this to test your knowledge of advanced tree structures like the Kruskal Reconstruction Tree or Persistent Union Find. It evaluates your ability to handle dynamic graph connectivity and your understanding of Minimum Spanning Trees (MST). This is a very high-level problem that tests the limits of a candidate's algorithmic toolkit.

Algorithmic pattern used

This problem is best solved using a Kruskal Reconstruction Tree. When building an MST using Kruskal's algorithm, instead of just connecting two nodes, you create a new "parent" node whose weight is the weight of the edge connecting them. The result is a tree where the "bottleneck" (maximum edge weight) on the path between any two original nodes is the value of their Lowest Common Ancestor (LCA). Queries then become a simple LCA check.

Example explanation

Edges: (A-B, 3), (B-C, 5).

1. Add (A-B, 3): Create node P1(val:3) as parent of A and B.
2. Add (B-C, 5): Create node P2(val:5) as parent of P1 and C.
3. Query(A, C, L:6):
   • LCA of A and C is P2.
   • P2.value is 5.
   • 5 < 6, so a path exists. Result: True.

Common mistakes candidates make

The main challenge is knowing the specific data structure needed. Without a Kruskal Reconstruction Tree or similar persistent structure, an "Online" version of this problem is nearly impossible to solve within time limits. Candidates might also struggle with implementing the Binary Lifting technique needed to find the LCA efficiently.

Interview preparation tip

Study the relationship between MSTs and the "Minimax Path" (the path that minimizes the maximum edge weight). This concept is the foundation for many advanced network and graph optimization problems.