PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep
|Home/Coding & Algorithms/DoorDash

Design dynamic connectivity with alive nodes

Last updated: May 3, 2026

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.

  • Medium
  • DoorDash
  • Coding & Algorithms
  • Software Engineer

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.

Related Interview Questions

  • Validate a Shopping Cart - DoorDash (medium)
  • Calculate Driver Payments - DoorDash (medium)
  • Implement Timeout Refund Workflow - DoorDash (medium)
  • Maximize Chef Assignment Profit - DoorDash (medium)
  • Compute Courier Delivery Pay - DoorDash (easy)
DoorDash logo
DoorDash
Sep 6, 2025, 12:00 AM
Software Engineer
Onsite
Coding & Algorithms
6
0

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.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More DoorDash•More Software Engineer•DoorDash Software Engineer•DoorDash Coding & Algorithms•Software Engineer Coding & Algorithms
PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.