Katkat
Back

Design dynamic connectivity with alive nodes

DoorDashSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of dynamic graph data structures, connectivity algorithms, state management for node activation/deactivation, complexity analysis, and concurrent operation considerations.

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: (

  1. activate(i) / deactivate(i) to toggle a node's alive status; (
  2. connect(u, v) that adds an edge only if both endpoints are currently alive; (
  3. disconnect(u, v) to remove an existing edge; (
  4. isConnected(u, v) that returns whether u and v are in the same connected component considering only alive nodes; and (
  5. 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.