Leetcode 1166. Design File System
Asked at:
Capital One
Anchorage Digital
Uber
DESCRIPTION
Implement an in-memory file system that stores path-value pairs with strict hierarchical constraints. The createPath(path, value) operation must only succeed if the immediate parent path already exists and the path itself is new. The get(path) operation returns the stored value or -1 if the path doesn't exist. For example, createPath("/a/b/c", 5) should fail unless /a/b already exists.
Input:
createPath("/a", 1) createPath("/a/b", 2) get("/a/b") createPath("/a/b/c", 3) get("/a/b/c")
Output:
true true 2 true 3
Explanation: Each path creation succeeds because its parent exists. /a has no parent (root case), /a/b's parent /a exists, and /a/b/c's parent /a/b exists.
Constraints:
- Paths are absolute Unix-style strings starting with /
- Path components are separated by / (e.g., /a/b/c has parent /a/b)
- createPath must fail if the path already exists or if the immediate parent doesn't exist
- get returns the integer value stored at the path, or -1 if not found
- Optimize for efficient parent existence checks and path lookups
Understanding the Problem
The core challenge is efficiently validating parent-child relationships in a hierarchical structure while preventing duplicates. A naive approach using string manipulation to check parent existence on every insert would be slow. The key insight is to use a trie-like structure where each node represents a path component, allowing O(depth) parent validation by traversing the tree. We must also handle the root path edge case (paths like /a have no explicit parent) and ensure atomic existence checks to prevent race conditions in the data structure.
Building Intuition
A naive approach using a hash map with string keys requires parsing each path to extract the parent (e.g., /a/b/c → /a/b), then checking if the parent exists—this involves string manipulation on every operation. A better approach uses a nested map structure (trie) where each node stores its children as a map, enabling direct traversal: split the path into components, navigate node-by-node, and validate parent existence during traversal. For example, creating /a/b/c involves navigating to /a, then /a/b, confirming it exists, then adding c as a child.
This pattern appears in file systems, URL routing, and organizational hierarchies where parent-child relationships must be enforced. Efficient path validation is critical for systems handling thousands of nested resources. The trie structure also enables prefix-based queries (like listing all files under /a/b) which are common in real-world applications.
Common Pitfalls
Implementation
Trie Node Structure and Path Parsing
Define a TrieNode class to represent each path component, storing a value (integer or null) and a children map (string → TrieNode). Implement a path parsing utility that splits a path string into components, filtering out empty strings from leading/trailing slashes. For example, /a/b/c becomes ['a', 'b', 'c']. This foundation enables hierarchical navigation in subsequent operations.
class TrieNode:def __init__(self):self.value = Noneself.children = {}def parse_path(path):return [component for component in path.split('/') if component]
Create Path with Parent Validation
Implement createPath(path, value) by traversing the trie using parsed components. Navigate to the parent node by iterating through all components except the last, returning false if any intermediate node is missing. Once at the parent, check if the final component already exists as a child—if so, return false (duplicate). Otherwise, create a new child node with the given value. For example, creating /a/b/c requires navigating to the node representing /a/b, then adding c as a child.
def createPath(root, path, value):components = parse_path(path)if not components:return Falsecurrent = rootfor component in components[:-1]:if component not in current.children:return Falsecurrent = current.children[component]last_component = components[-1]if last_component in current.children:return Falsecurrent.children[last_component] = TrieNode()current.children[last_component].value = valuereturn True
Get Path Value Retrieval
Implement get(path) by traversing the trie using all parsed components. Navigate node-by-node through the children maps, returning -1 if any component is missing. If the full path exists, return the node's stored value (or -1 if the node exists but has no value set). For example, get("/a/b") navigates to the a node, then to its child b, and returns b's value.
def get(root, path):components = parse_path(path)if not components:return -1current = rootfor component in components:if component not in current.children:return -1current = current.children[component]return current.value if current.value is not None else -1
Complete File System Integration
Combine the TrieNode structure (Section 1), createPath logic (Section 2), and get logic (Section 3) into a unified FileSystem class. Initialize with a root TrieNode representing the file system's base. Expose createPath and get as public methods that use the shared path parsing utility and trie traversal logic. For example, instantiate FileSystem fs = new FileSystem(), then call fs.createPath("/a", 1) and fs.get("/a") to interact with the hierarchical structure.
class FileSystem:def __init__(self):self.root = TrieNode()def createPath(self, path, value):return createPath(self.root, path, value)def get(self, path):return get(self.root, path)
What We've Learned
- Pattern: Use a trie (prefix tree) to model hierarchical paths, enabling `O(depth)` parent validation and lookups without string manipulation
- Use Case: Apply to file systems, URL routers, and organizational charts where parent-child constraints must be enforced efficiently
- Edge Case: Handle root-level paths (e.g., `/a`) by treating the root node as an implicit parent that always exists
- Optimization: Store children in hash maps for `O(1)` component lookup, avoiding linear scans through sibling nodes
Problems to Practice
Tries are tree-based data structures specifically designed for efficient string/path prefix operations, which directly relates to the hierarchical path structure in the file system problem. Understanding trie fundamentals will help with implementing the parent-path validation logic.
medium
This problem involves implementing a trie data structure with insert and search operations, which mirrors the createPath and get operations in the file system. Both require maintaining a tree structure with path/prefix-based lookups and ensuring proper parent-child relationships.
medium
This problem focuses on prefix-based queries in a trie, which is essential for validating parent path existence in the file system. The pattern of checking if a prefix exists before allowing operations is directly applicable to the parent-existence constraint.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early July, 2026
Anchorage Digital
Senior
Late June, 2026
Capital One
Senior
Late January, 2026
Capital One
Senior
Hello Interview Premium
Your account is free and you can post anonymously if you choose.