DescriptionQ237
Q237FWDVASIC interview problem
Dynamic Connectivity with Disjoint Sets
TechniquesFWDVUnion-findAssociative arrayPath compression
DifficultyMedium
TopicAlgorithms
LanguageSystemVerilog
Requirements4 checkpoints
01
Problem
Track connectivity among sparsely numbered components as links are added over time. Queries should remain fast even after a long sequence of unions.
Class declarationSystemVerilog
class ConnectivityTracker;
bit add_node(int id);
bit connect(int a, int b);
bit connected(int a, int b);
int component_size(int id);
endclassExample input and output
Use this case to check your interpretationInput
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)Output
false, then trueExplanation
The final connection joins the two components; path compression and union by size preserve near-constant amortized operations.
02
Requirements (4)
- 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.