Medium

Google-styleMeta-style

Track Connectivity Across a Growing Network DSA Interview

Given a number of servers and a sequence of direct connection events between pairs of servers, answer whether two given servers are connected after each event, processing many union and query operations efficiently.

Mock Interview with AI

1. Problem Statement

You are given a number of servers labeled 0 to n-1. Implement connect(a, b) to record a direct connection, and isConnected(a, b) to report whether two servers are in the same connected group. Both operations will be called many times, interleaved.

2. Live Coding Format

Choose Python, JavaScript, Java, or C++, then solve while explaining your reasoning to the live interviewer.

Validation uses handwritten tests only. The MVP does not compile or run code, and it does not provide AI algorithm completion.

3. Key Focus Areas

1
Problem clarification and contract
2
Approach exploration and optimality
3
Think-aloud communication and pacing
4
Implementation correctness
5
Code quality and language fluency
6
Handwritten tests and dry run
7
Debugging and self-correction
8
Complexity analysis
9
Follow-up performance

4. What Strong Candidates Should Demonstrate

✓Clarify indexing, self-connections, and repeated-connection behavior before coding.
✓Explain a naive BFS-per-query baseline and improve to union-find with path compression and union by rank/size.
✓Think aloud while implementing careful find/union logic.
✓Validate with explicit expected outputs and a top-to-bottom handwritten dry run.
✓Analyze time and space complexity and handle a bounded follow-up modification.

Evaluation Guide

This is an evaluation framework, not a single model answer. Strong designs may make different choices when their assumptions and trade-offs are explicit.

Problem clarification and contract

10%

Senior signals

✓Clarifies server indexing (0-indexed vs 1-indexed), whether connect can be called on the same pair multiple times, and what connect(a, a) should do.
✓Confirms connect and isConnected can be interleaved in any order and both must be efficient, not just isConnected.

Staff-level signals

◆Asks about the expected number of servers and total operations to justify near-constant-time amortized operations.

Common red flags

×Codes immediately while assuming isConnected is called only once at the end without confirming interleaving.

Approach exploration and optimality

20%

Senior signals

✓Explains a naive baseline that runs BFS/DFS across the current adjacency structure for every isConnected call, identifies the repeated-traversal bottleneck, and improves to a union-find (disjoint set union) structure with path compression and union by rank or size.
✓Explains how path compression flattens the tree during find operations to keep future finds fast.

Staff-level signals

◆Discusses the near-constant amortized complexity argument (inverse Ackermann function) at a high level without needing a rigorous proof.

Common red flags

×Starts implementation without explaining an approach even after one interviewer prompt.
×Proposes union-find without path compression or union by rank/size, missing the performance justification.

Think-aloud communication and pacing

10%

Senior signals

✓Explains the plan before coding and narrates the find/union logic and compression step while implementing.
✓Paces the core solution to leave time for validation and the follow-up.

Common red flags

×Writes substantial code silently and cannot explain what the code is doing.

Implementation correctness

25%

Senior signals

✓Implements a correct union-find with a parent array, a find operation that compresses paths, and a union operation that attaches by rank or size, with isConnected comparing the roots of both servers.
✓Handles self-connections, repeated connect calls on the same pair, and isConnected queries before any connections are made.
✓Provides a convincing invariant argument for why two servers share a root exactly when they are connected.

Common red flags

×Implements find without path compression and union without rank/size, degrading to linear-chain behavior on adversarial input.
×Final code contains a material correctness bug that the candidate does not identify.

Code quality and language fluency

15%

Senior signals

✓Produces readable, language-appropriate code with clear parent and rank/size arrays and well-isolated find/union helper functions.

Common red flags

×Contains off-by-one indexing errors or syntax-level incoherence that prevents credible reasoning.

Handwritten validation, dry run, and debugging

10%

Senior signals

✓Provides explicit inputs and expected outputs before tracing the code from top to bottom, showing parent array changes after each operation.
✓Covers self-connections, repeated connections, queries before any connection, and transitive connectivity across multiple unions.
✓Finds and fixes an error independently, then re-validates the affected path.

Common red flags

×Claims the code works without a representative trace.

Complexity analysis and follow-up

10%

Senior signals

✓States near-constant amortized time per operation with path compression and union by rank/size, and linear auxiliary space for the parent and rank/size arrays, comparing this with the BFS-per-query baseline.

Staff-level signals

◆Discusses behavior without one of the two optimizations (path compression or union by rank/size) and why both together give the strongest guarantee.

Common red flags

×Cannot state the complexity of the implemented solution.
×Fails a reasonable follow-up despite having at least five minutes and receiving bounded clarification.

Trade-offs to articulate

Running BFS or DFS for every isConnected query is simple but costs time proportional to the network size on every single query.
Union-find without path compression or union by rank/size can degrade to linear-chain trees under adversarial connection order.
Union-find with both path compression and union by rank/size achieves near-constant amortized time per operation using linear auxiliary space.

Practice follow-up questions

1.Coding follow-up: extend the structure to also maintain and return the current number of distinct connected groups, updated incrementally as connections are made.
2.Verbal extension: how would the approach change if connections also needed to be removable (disconnecting two previously connected servers)?

Want interactive feedback?

Practice this problem in the live coding workspace while the interviewer probes your clarification, algorithm, implementation, complexity, and handwritten tests.

Start Interview

Core Concepts

Union-FindDisjoint Set UnionGraphsComplexity Analysis