← Motive Interview Insights

Motive·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jul 2026

Summary

Motive software engineer interview with a pretty focused DSU question. Nothing too wild but they pushed hard on the complexity analysis and thread-safety parts, which I was not fully ready for.

Questions Asked (1)

Q1

Implement a Disjoint Set Union (Union-Find) data structure with union by rank and path compression. The API should support union(a, b), connected(a, b), and a count() method returning the number of connected components. Given n nodes and a stream of operations, return the result of each connected query and the component count after each union. Also analyze time and space complexity and discuss thread-safety.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs
Author's notes

I got the core implementation down fine, path compression and union by rank are pretty standard once you've seen them.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clearly defining the DSU class with parent and rank arrays, then implement union by rank and path compression. Walk through the API methods, explaining how count() is maintained. Finally, analyze time and space complexity and discuss thread-safety considerations.

Pro tip: Mention that path compression alone gives amortized O(log n) per operation, but combining it with union by rank yields near O(1) amortized time (inverse Ackermann). Also, note that thread-safety can be achieved with fine-grained locking or by using a concurrent DSU variant, but often a global lock suffices for simplicity.

1. Define the data structure

Explain that you'll use two arrays: parent (to track representatives) and rank (to keep tree shallow). Initialize each node as its own parent and rank 0, and set component count to n.

2. Implement find with path compression

Describe the recursive or iterative find operation that traverses to the root and compresses the path by updating parent pointers to the root.

3. Implement union by rank

Explain how to merge two components by attaching the tree with smaller rank under the root of the larger rank, updating rank if equal, and decrementing the component count.

4. Implement connected and count

connected(a, b) simply checks if find(a) == find(b). count() returns the maintained component count.

5. Analyze complexity and thread-safety

State that with both optimizations, each operation is amortized O(α(n)) time, and space is O(n). For thread-safety, discuss locking strategies (e.g., global lock, fine-grained locks) and trade-offs.

Key Points to Mention

  • Path compression: flattens the tree by making nodes point directly to the root.
  • Union by rank: attaches smaller tree to larger tree to keep depth logarithmic.
  • Amortized time complexity: O(α(n)) per operation, where α is the inverse Ackermann function.
  • Space complexity: O(n) for parent and rank arrays.
  • Component count maintenance: decrement on successful union.
  • Thread-safety: use locks (global or per-node) or concurrent data structures; note that read operations may need synchronization if writes are concurrent.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.