new paste || ipv4:js fail, n/a or broken? | ipv6:js fail, n/a or broken? ||

paste 35916/f046 | 10 views since 2026-11-07 23:27:23 | text/plain | wrap || empty reply | copy reply | quote reply
js:(
# Union Find Connected (Practice 4364): Drill

Interviewers love union find connected because it checks whether you can state the invariant before coding. Here is a compact rehearsal note.

## Approach

Path-compressed parents; unite by rank.

```python
class DSU:
    def __init__(self, n):
        self.p = list(range(n)); self.r = [0]*n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]; x = self.p[x]
        return x
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b: return False
        if self.r[a] < self.r[b]: a, b = b, a
        self.p[b] = a
        if self.r[a] == self.r[b]: self.r[a] += 1
        return True
```

## Complexity

Linear in the dominant input size for the scan; heap/tree variants add a log factor.

## Interview pitfalls

State the invariant out loud, name the complexity, then code. Skipping the invariant is the usual fail mode.

## Practicing out loud

Narrate the approach, complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see [Linkjob.ai](https://www.linkjob.ai/).