Evaluate Division (Union-Find)
Given a set of equations $A/B = k$ and queries $C/D = ?$, calculate the result of the queries. Use a Graph (or Union-Find) to represent the division relationships.
Why Interviewers Ask This
Google interviewers use this problem to assess a candidate's ability to model real-world relationships as graph structures and select the optimal algorithmic approach. They specifically evaluate your understanding of Disjoint Set Union (Union-Find) with path compression and rank optimization, testing if you can handle dynamic connectivity problems efficiently rather than just solving isolated equations.
How to Answer This Question
1. Clarify requirements: Confirm edge cases like division by zero or disconnected variables immediately.
2. Model the problem: Explain that each variable is a node and an equation A/B=k creates a weighted directed edge from A to B with weight k, while B/A has weight 1/k.
3. Choose the strategy: Propose using Union-Find where each node tracks its parent and the ratio relative to that parent, allowing O(α(n)) amortized time for operations.
4. Implement logic: Detail how 'find' compresses paths and updates ratios, and how 'union' merges sets by attaching one root to another while calculating the new scaling factor.
5. Handle queries: Describe traversing the path to find roots; if roots differ, return -1, otherwise compute the result by dividing the accumulated weights.
6. Analyze complexity: Explicitly state O(N + Q * α(N)) time and O(N) space complexity to demonstrate depth of understanding expected at Google.
Key Points to Cover
- Modeling the problem as a weighted graph where edges carry multiplicative values
- Implementing Union-Find with path compression that maintains cumulative ratios
- Handling disconnected components by returning -1 when roots differ
- Achieving O(N + Q * α(N)) time complexity through optimized union-find
- Demonstrating awareness of edge cases like division by zero or missing variables
Sample Answer
To solve the Evaluate Division problem, I would model the variables as nodes in a weighted graph where edges represent the division results. For instance, if we have A/B = 2.0, we create a directed edge from A to B with…
Common Mistakes to Avoid
- Failing to update the ratio value during path compression, leading to incorrect query results
- Ignoring the need for bidirectional edges (A/B vs B/A) when building the initial structure
- Not handling disconnected variables, causing runtime errors or infinite loops in traversal
- Using simple BFS/DFS without memoization, resulting in TLE for large numbers of queries
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.