Uber SDE 2 Phone Interview: Union Find Graph Optimization Challenge

Problem overview from real interview of Uber:

An SDE 2 candidate shares their Uber phone screen experience, detailing a struggle with optimizing a Union-Find graph problem from O(N*M) to O(N) complexity.