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

SeniorPrefer not to say

May 2026

Summary

DoorDash system design round where they had me build an in-memory hierarchical key-value store from scratch. Pretty open-ended, which I wasn't expecting for a coding-adjacent round. Had to cover data structures, complexity, testing, and then concurrency and persistence on top of it.

Questions Asked (1)

Design and implement an in-memory hierarchical key-value store using UNIX-style paths. The root node '/' starts with value '#'. Support Create, SetValue, GetValue, and Delete operations with appropriate constraints (parent must exist for create, no children allowed for delete, etc.). Define the class interface, pick your data structures, analyze time and space complexity, write unit tests, and explain how you'd add concurrency safety and optional disk persistence.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

This was basically the whole interview.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and defining the class interface with methods for Create, SetValue, GetValue, and Delete. Choose a tree-based data structure (e.g., trie) where each node represents a path component and stores a value, then implement operations with proper validation. Discuss time/space complexity, unit tests, and extensions like concurrency and persistence.

Pro tip: Explicitly handle edge cases like root path operations and path normalization (e.g., trailing slashes, redundant separators) to demonstrate production-level thinking. Also, mention that you'd use a read-write lock for concurrency, but discuss trade-offs like lock granularity and potential deadlocks.

1. Clarify Requirements and Define Interface

Ask clarifying questions about path format, value types, and constraints. Define a class with methods: create(path), setValue(path, value), getValue(path), delete(path). Specify that create requires parent to exist, delete requires no children, and root cannot be deleted.

2. Choose Data Structures and Design

Use a tree where each node has a map of child name to node and an optional value. Root node has value '#'. Paths are split by '/' and traversed. This supports efficient hierarchical operations.

3. Implement Operations with Validation

For create: traverse to parent, ensure it exists, then add child if not already present. For setValue: traverse to node, set value. For getValue: traverse and return value if exists. For delete: traverse to node, ensure it has no children, then remove from parent.

4. Analyze Complexity and Write Tests

Time complexity is O(k) where k is path depth (number of components). Space is O(total nodes). Write unit tests covering normal cases, edge cases (root, non-existent paths, duplicate creates, delete with children), and error conditions.

5. Discuss Concurrency and Persistence

For concurrency, use a read-write lock per node or a global lock with trade-offs. For persistence, serialize the tree to disk (e.g., JSON) on changes or periodically, and load on startup.

Key Points to Mention

Use a trie-like tree structure with each node storing a map of children and an optional value.
Path normalization: handle leading/trailing slashes, multiple slashes, and relative paths.
Time complexity: O(k) for operations where k is the number of path components; space O(n) for n nodes.
Unit tests should cover: create with missing parent, delete with children, get/set on non-existent paths, root operations.
Concurrency: use read-write locks for fine-grained locking, but consider deadlock avoidance and lock ordering.
Persistence: serialize to disk using JSON or a custom format, with options for write-through or periodic snapshots.

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