# Interview questions: union find solutions

· by Xianjin YE · Read in about 5 min · (2229 Words)
algorithms coursera job-interview

# Question 1

Social network connectivity. Given a social network containing N members and a log file containing M timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend … of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be MlogN or better and use extra space proportional to N.

## 问题分析

1. 一开始所有人都只是跟自己是朋友 -> Union Find数据初始化
2. $t_i$时刻, $m_i$和$m_j$成为朋友 -> connect($m_i$, $m_j$)
3. 判断网络是否联通 -> Union Find中的count == 1

# Question 2

Union-find with specific canonical element. Add a method find() to the union-find data type so that find(i) returns the largest element in the connected component containing i. The operations, union(), connected(), and find() should all take logarithmic time or better.

# Question 3

Successor with delete. Given a set of N integers S={0,1,…,N−1} and a sequence of requests of the following form: 1. Remove x from S 2. Find the successor of x: the smallest y in S such that y≥x.

design a data type so that all operations (except construction) should take logarithmic time or better.

## 问题分析

1. remove完全是为find服务的.remove的最终动作可能只是个更改flag位,以便于让find能够确定该元素是否被删除
2. find(x)的结果只受到了remove(y)的影响,其中y >= x.

## 问题解决

remove(x) => connect(x, x+1)

find(x) => find(x) // return the largest element

# Question 4

Union-by-size. Develop a union-find implementation that uses the same basic strategy as weighted quick-union but keeps track of tree height and always links the shorter tree to the taller one. Prove a lgN upper bound on the height of the trees for N sites with your algorithm.

## 算法时间复杂度证明

h(0) = 1 // 高度为0, 也即只有一个节点..

h(1) = 2 // 高度为1,至少有两个节点