In any solution using union-find (disjoint set), can I approximate the 'find' operation is O(1) ?
Assuming you use path compression during find. In reality, even with path compression, it is the upper bound of some function, and something like a continuous stream of log's, but seems reasonable to approximate that as O(1) amortized. During interview, Is O(1) is a reasonable shortcut/approxmiation for the time complexity of "find with path compression"? (Assuming union find is only a part of the answer, and the question is not specifically to drill you into details of union find.)
You still have to use rank (size) optimization along with path compression to archive O(alpha(n)) where alpha() is inverse accerman function, which is not exactly O(1) but it’s extremely close to it (it’s like alpha(1e9)=25).
This
What if the particular problem does not need any rank? ie the union operation always joins left node parent with right node?
The amortized runtime is O(1)
Without rank or size optimization, you get logarithmic TC
Too hard, just use random%2 when merge.
O(TC)
it grows more slowly than iterated logs iirc, inverse ackerman function edit: with weighting