← Meta Interview Insights

Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jul 2026Remote

Summary

Meta SWE coding round, one question the whole time: implement Union Find with path compression and rank-based union. Pretty focused session, no fluff.

Questions Asked (1)

Q1

Implement a Union Find (Disjoint Set) data structure supporting find with path compression and union by rank, then use it to process a sequence of union and find operations.

Algorithms & Data Structures
Author's notes

I knew Union Find going in but blanked on the exact rank logic mid-implementation.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and constraints, then explain the Union-Find data structure with path compression and union by rank, including their time complexities. Implement the class with parent and rank arrays, and demonstrate processing the operations with a dry run or code.

Pro tip: Mention that path compression alone gives amortized O(log n) per operation, but combining it with union by rank achieves nearly O(1) amortized time (inverse Ackermann). This shows deep understanding and can impress the interviewer.

1. Clarify requirements and constraints

Ask about the number of elements, types of operations, and expected time complexity. Confirm if the operations are online or offline, and if there are any memory constraints.

2. Explain the data structure design

Describe using two arrays: parent to track representatives and rank (or size) to guide union. Explain path compression during find and union by rank during union.

3. Implement the class

Write the constructor to initialize parent[i] = i and rank[i] = 0. Implement find with recursion or iteration and path compression, and union that attaches smaller rank tree under larger rank tree.

4. Process operations and analyze complexity

Iterate through the given operations, calling union or find as needed. State that with both optimizations, each operation runs in amortized O(α(n)) time, which is nearly constant.

5. Test with examples and edge cases

Walk through a small example to verify correctness, and mention edge cases like union of already connected elements, find on root, and large inputs.

Key Points to Mention

  • Path compression: flatten the tree during find by making nodes point directly to the root.
  • Union by rank: attach the tree with smaller rank under the root of the larger rank tree to keep trees shallow.
  • Time complexity: amortized O(α(n)) per operation, where α is the inverse Ackermann function, effectively constant.
  • Space complexity: O(n) for parent and rank arrays.
  • Use cases: connected components, Kruskal's MST, dynamic connectivity.
  • Implementation details: recursive vs iterative find, handling 0-indexed vs 1-indexed elements.

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