Q237FreeFirmware
Dynamic Connectivity with Disjoint Sets
Interview prompt
Question
Track connectivity among sparsely numbered components as links are added over time. Queries should remain fast even after a long sequence of unions.
Starting point
Question code
class ConnectivityTracker;
bit add_node(int id);
bit connect(int a, int b);
bit connected(int a, int b);
int component_size(int id);
endclassReviewed example
Trace one case
Input
add_node(0); add_node(1); add_node(2); add_node(3); connect(0,1); connect(2,3); connected(0,3); connect(1,2); connected(0,3)Expected output
false, then trueThe final connection joins the two components; path compression and union by size preserve near-constant amortized operations.
What to cover
Requirements
- Reject or clearly define operations on unknown node IDs.
- Duplicate links and self-links must not corrupt component sizes.
- Use path compression and union by rank or size.
- connect returns 1 only when two previously separate components are joined.