Design dynamic connectivity with alive nodes

Q: Design dynamic connectivity with alive nodes

This is a Coding & Algorithms interview question from DoorDash for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Design a data structure to maintain an undirected graph of N nodes, where each node has a boolean 'alive' flag. Support the following operations efficiently for up to 100,000 operations: (

activate(i) / deactivate(i) to toggle a node's alive status; (
connect(u, v) that adds an edge only if both endpoints are currently alive; (
disconnect(u, v) to remove an existing edge; (
isConnected(u, v) that returns whether u and v are in the same connected component considering only alive nodes; and (
countComponents() over alive nodes. Describe data structures, time/space complexities, and how you would handle deletions and node deactivations (e.g., lazy deletion vs. fully dynamic connectivity). Discuss any concurrency considerations if these operations are called from multiple threads.

Design dynamic connectivity with alive nodes

Comments (0)