⌘K

Tutor

Leetcode 1166. Design File System

Asked at:

Capital One

Uber

Google

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

Forgetting root edge case: Paths like /a have no parent—handle this by allowing creation when the parent would be empty or root + Use a special root node in the trie

Duplicate path detection: Must check if the final component already exists before insertion + Verify the target node doesn't already have a value

Incorrect path parsing: Trailing slashes or empty components (e.g., /a//b) can break logic + Normalize paths by splitting and filtering empty strings

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.

Solution

class TrieNode:
    def __init__(self):
        self.value = None
        self.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.

Solution

def createPath(root, path, value):
    components = parse_path(path)
    if not components:
        return False
    
    current = root
    for component in components[:-1]:
        if component not in current.children:
            return False
        current = current.children[component]
    
    last_component = components[-1]
    if last_component in current.children:
        return False
    
    current.children[last_component] = TrieNode()
    current.children[last_component].value = value
    return 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.

Solution

def get(root, path):
    components = parse_path(path)
    if not components:
        return -1
    
    current = root
    for component in components:
        if component not in current.children:
            return -1
        current = 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.

Solution

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

Overview

Lesson

Trie

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.

Learn

Implement Trie Methods

medium

Trie

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.

Practice

Prefix Matching

medium

Trie

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.

Practice

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late January, 2026

Capital One

Senior

Late July, 2025

Uber

Senior

Early April, 2025

Uber

Senior

Get Premium to View All 4 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 1166. Design File System

DESCRIPTION

Understanding the Problem

Building Intuition

Common Pitfalls

Implementation

Trie Node Structure and Path Parsing

Create Path with Parent Validation

Get Path Value Retrieval

Complete File System Integration

What We've Learned

Problems to Practice

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact