Crack Meta Software Engineering Interviews: Top 5 Disjoint Set Questions with Python Solutions

When you're gunning for a software engineering role at Meta (formerly known as Facebook), you'll come across a plethora of data structures, and one of the intriguing ones is the disjoint set, also known as union-find. This powerful data structure is perfect for solving problems related to connectivity, network building, and partitioning sets. In this article, we'll dive into the top 5 questions related to disjoint sets that you can expect in Meta's software engineering interviews, along with Python solutions for each.

Consider ByteByteGo’s popular System Design Interview Course for your next interview!

1. Friend Circles

Question:

Given an N x N matrix M representing a list of friendships, where M[i][j] is 1 if i and j are friends, find the number of friend circles.

def find_circle_num(M):
    def find(i, parent):
        if parent[i] == -1:
            return i
        return find(parent[i], parent)
    
    def union(x, y, parent):
        x_set = find(x, parent)
        y_set = find(y, parent)
        if x_set != y_set:
            parent[x_set] = y_set
    
    n = len(M)
    parent = [-1] * n
    
    for i in range(n):
        for j in range(i, n):
            if M[i][j] == 1:
                union(i, j, parent)
                
    return len(set(find(i, parent) for i in range(n)))

Grokking the Coding Interview: Patterns for Coding Questions

Don’t forget to get your copy of Designing Data Intensive Applications, the single most important book to read for system design interview prep!

2. Number of Islands II

Question:

Given a grid of size m x n, perform a list of k operations that add a new island at location (x, y). Return the number of islands after each addition.

def num_islands2(m, n, positions):
    parent = {}
    
    def find(i, parent):
        if parent.setdefault(i, i) == i:
            return i
        parent[i] = find(parent[i], parent)
        return parent[i]
    
    def union(x, y, parent):
        parent[find(x, parent)] = find(y, parent)
        
    islands = 0
    res = []
    
    for x, y in positions:
        cur = x * n + y
        parent[cur] = cur
        islands += 1
        
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nb = (x + dx) * n + (y + dy)
            if nb in parent and find(nb, parent) != find(cur, parent):
                union(cur, nb, parent)
                islands -= 1
                
        res.append(islands)
        
    return res

Get a leg up on your competition with the Grokking the Advanced System Design Interview course and land that dream job! Don’t waste hours on Leetcode. Learn patterns with the course Grokking the Coding Interview: Patterns for Coding Questions.

Deep dive into mastering dynamic programming interview questions

3. Redundant Connection

Question:

Given a list of connections edges representing an undirected graph, find an edge that can be removed so that the graph contains no cycle.

def find_redundant_connection(edges):
    parent = {}
    
    def find(u, parent):
        if parent.setdefault(u, u) == u:
            return u
        parent[u] = find(parent[u], parent)
        return parent[u]
    
    for u, v in edges:
        if find(u, parent) == find(v, parent):
            return [u, v]
        parent[find(u, parent)] = find(v, parent)

Grokking Machine Learning Design

4. Accounts Merge

Question:

Given a list of accounts, where each account has a name and a list of emails, merge the accounts that belong to the same person.

from collections import defaultdict

def accounts_merge(accounts):
    parent = {}
    
    def find(u):
        if parent.setdefault(u, u) == u:
            return u
        parent[u] = find(parent[u])
        return parent[u]
    
    email_to_name = {}
    for name, *emails in accounts:
        for email in emails:
            email_to_name[email] = name
            
    for name, *emails in accounts:
        for email in emails[1:]:
            parent[find(emails[0])] = find(email)
            
    merged = defaultdict(list)
    for email in email_to_name.keys():
        merged[find(email)].append(email)
        
    return [[email_to_name[k]] + sorted(v) for k, v in merged.items()]

Interviewing? Buy one month access to our best-selling course for Java Multithreading Interviews to get ahead of the competition.

5. Number of Connected Components in an Undirected Graph

Question:

Given n nodes labeled from 0 to n-1 and a list of undirected edges, find the number of connected components.

def count_components(n, edges):
    parent = list(range(n))
    
    def find(v):
        if parent[v] == v:
            return v
        parent[v] = find(parent[v])
        return parent[v]
    
    for u, v in edges:
        parent[find(u)] = find(v)
        
    return len(set(find(v) for v in range(n)))

By mastering the use of disjoint sets in Python, you're equipping yourself with a potent tool that could be the key to unlocking your dream job at Meta. Keep practicing these questions, and you'll be well on your way to acing your next interview.

Land a higher salary with Grokking Comp Negotiation in Tech.

Photo by Yancy Min on Unsplash