DoorDash·Software Engineer·Onsite - System Design / Architecture·Senior

Senior

Jun 2026

Summary

DoorDash system design round for a software engineering role. One meaty graph problem that went pretty deep into dynamic connectivity, concurrency, and tradeoffs. Not a casual screen.

Questions Asked (1)

Design a data structure for an undirected graph of N nodes where each node has an 'alive' flag. Support toggling node status, adding edges only between alive nodes, removing edges, checking if two nodes are in the same connected component among alive nodes, and counting connected components over alive nodes. Discuss time/space complexity, how you'd handle deletions and deactivations (lazy vs fully dynamic), and concurrency if multiple threads call these operations simultaneously.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This one took me a while to even get my footing.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a baseline solution using Union-Find with lazy deletion for deactivations, and discuss how to extend it for edge removals. Compare trade-offs between lazy and fully dynamic approaches, and address concurrency with locking or lock-free techniques.

Pro tip: Emphasize that in practice, lazy deletion is often sufficient and simpler; for full dynamism, consider Euler Tour Trees or Link-Cut Trees but note their complexity. Also, mention that concurrency can be handled by sharding or read-write locks, but be prepared to discuss performance implications.

1. Clarify Requirements and Constraints

Ask about expected operation frequencies, graph size, and concurrency needs to tailor the solution. Confirm whether edge additions/removals are frequent and if nodes can be reactivated.

2. Propose a Baseline with Union-Find

Use Union-Find (Disjoint Set Union) to track connected components among alive nodes. For deactivations, mark nodes as dead and lazily ignore them in queries; for edge removals, note that Union-Find doesn't support deletions, so consider rebuilding or using a dynamic connectivity structure.

3. Discuss Handling Deletions and Deactivations

Compare lazy vs fully dynamic approaches: lazy deletion is simple but may degrade over time; fully dynamic structures like Euler Tour Trees or Link-Cut Trees support all operations in polylog time but are complex. Suggest a hybrid or periodic rebuild.

4. Address Concurrency

For multi-threaded access, propose using fine-grained locks per component, read-write locks, or lock-free techniques with atomic operations. Discuss trade-offs between consistency and performance.

5. Analyze Complexity and Trade-offs

Summarize time/space complexity for each operation in the chosen approach, and highlight trade-offs between simplicity, performance, and scalability.

Key Points to Mention

Union-Find with path compression and union by rank for near O(1) amortized operations.
Lazy deletion: mark nodes as dead and skip them in queries, but handle edge cases like counting components correctly.
Fully dynamic connectivity: Euler Tour Trees or Link-Cut Trees for O(log n) per operation, but complex to implement.
Concurrency: use locks (e.g., per-component locks) or lock-free data structures; consider read-heavy vs write-heavy workloads.
Trade-offs: lazy deletion may lead to stale data and require periodic cleanup; fully dynamic structures have higher overhead.
Edge cases: adding edges between dead nodes should be disallowed; removing edges may split components; reactivation of nodes.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.