Quick Overview

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

Design dynamic connectivity with alive nodes

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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.

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

Simulate alive-node graph operations and return outputs for connectivity/count queries.

Constraints

  • Inputs are Python literals matching the function signature.
  • Return a deterministic exact-match value.

Examples

Input: (4, [['activate',0],['activate',1],['connect',0,1],['isConnected',0,1],['countComponents'],['deactivate',1],['isConnected',0,1],['countComponents']])

Expected Output: [None, None, None, True, 1, None, False, 1]

Explanation: Alive filtering.

Input: (3, [['connect',0,1],['activate',0],['activate',1],['isConnected',0,1]])

Expected Output: [None, None, None, False]

Explanation: Connect ignored while endpoints dead.

Hints

  1. Use deterministic tie-breaking for prompts with multiple valid outputs.
  2. For design-style APIs, simulate operations with explicit inputs.

Loading coding console...