Skills101
← All practice quizzes

Quiz: Union-Find (Disjoint Set Union)

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

Keep track of groups that keep merging, and answer "are these two in the same group?" in nearly constant time. The parent array, find and union, path compression, union by rank, and the classic problems it solves.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    In Union-Find, two elements are in the same set exactly when:

  2. Question 2

    What does this print?

    parent = list(range(5))
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    def union(a, b):
        parent[find(a)] = find(b)
    union(0, 1)
    union(2, 3)
    union(1, 3)
    print(find(0) == find(2), find(4))
    
  3. Question 3

    What does path compression do?

  4. Question 4

    What does union by rank (or size) prevent?

  5. Question 5

    With both path compression and union by rank, the cost of one operation is:

🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →