Embercode: AI-powered software engineer course

1. A union-find forest uses union by size. The counting argument says a tree with depth d holds at least 2^d elements. With 100,000 elements, what is the largest depth any element can have?

71716100000

2. Which statements about path halving in find are true?

Pick every answer that is true.

It needs a second pass over the path after the root is foundEach step sets parent[x] to parent[parent[x]], so x skips one levelOn its own, it keeps every tree depth at most log2 nIt makes every element on the path point straight at the root in one stepIt makes later find calls on the same elements cheaper

3. What does this program print? ``

python
parent = [1, 2, 3, 4, 5, 5]

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

print(find(1))
print(parent)

``

prints 5, then [1, 3, 3, 5, 5, 5]prints 3, then [1, 3, 3, 5, 5, 5]prints 5, then [1, 2, 3, 4, 5, 5]prints 5, then [2, 3, 3, 5, 5, 5]

4. Which statement about this union is correct? ``

python
def union(a, b):
    parent[a] = b

`



Here

a and b are element numbers and parent` is the list from the lesson.

It is correct, because a and b are both roots after each callIt raises a TypeError, because parent is a list and b is an intIt only breaks when a equals b, which never happensIt skips find, so if a already has a parent, its old group loses its link to that root

5. What does this program print? ``

python
uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(0, 2)
print(uf.find(3) == uf.find(1), uf.find(1) == uf.find(4), uf.find(4))

`



Use the

UnionFind` class from the accounts-merge program in this lesson.

True False 4True True 4False False 4True False 0

Union-find