⌘K

Tutor

Leetcode 588. Design In-Memory File System

Asked at:

Snowflake

Uber

DESCRIPTION

Implement an in-memory file system that supports hierarchical directory structures with operations for creating directories (mkdir), listing contents (ls), creating/appending to files (addContentToFile), and reading file contents (readContentFromFile). The system must handle path parsing (e.g., /a/b/c), distinguish between files and directories, and return listings in lexicographical order. For example, calling mkdir("/a/b/c") should create nested directories, and addContentToFile("/a/b/file.txt", "hello") should create the file with content.

Input:

mkdir("/a/b/c")
addContentToFile("/a/b/file.txt", "hello")
ls("/a/b")
readContentFromFile("/a/b/file.txt")

Output:

["c", "file.txt"]
"hello"

Explanation: Create nested directories, add a file with content, list directory contents in lexicographical order, and read the file content

Constraints:

All paths are absolute (start with /)
Path components contain only alphanumeric characters, dots, and underscores
File and directory names are case-sensitive
ls on a file path returns a list containing only that filename
ls on a directory returns all direct children in lexicographical order
mkdir creates all intermediate directories if they don't exist
addContentToFile creates the file and parent directories if they don't exist, otherwise appends content

Understanding the Problem

The core challenge is designing a tree structure that efficiently represents the file system hierarchy while distinguishing files from directories. You must implement path parsing to traverse from root to target nodes, handle implicit directory creation for operations like mkdir and addContentToFile, and maintain file contents as strings. The ls operation requires lexicographical sorting of children, which influences whether to use hash maps (requiring sorting) or tree maps (maintaining order). Correctly handling edge cases like listing a file path versus a directory path is critical.

Building Intuition

A naive approach uses nested hash maps where each node stores children in a Map<String, Node>, requiring sorting on every ls call. A better approach uses a trie-like tree where each node contains a TreeMap<String, Node> to maintain children in sorted order automatically, plus a boolean isFile flag and String content field. For example, path /a/b/c.txt creates nodes a → b → c.txt where c.txt has isFile=true and stores content.

File systems are fundamental to operating systems, databases, and cloud storage (S3, Google Drive). Understanding hierarchical data structures with mixed node types (files vs directories) applies to DOM trees, organizational charts, and package managers. Efficient path traversal and sorted listings are critical for autocomplete, file explorers, and search indexing.

Common Pitfalls

Pitfall: Treating files and directories identically → Fix: Use isFile flag; files cannot have children

Pitfall: Forgetting to create intermediate directories → Fix: Traverse path and create missing nodes in mkdir and addContentToFile

Pitfall: Inefficient sorting on every ls call → Fix: Use TreeMap to maintain sorted order automatically

Pitfall: Not handling ls on file paths → Fix: If target node is a file, return list with only its filename

Implementation

Node Structure and Path Parsing

Define a Node class representing both files and directories with a TreeMap<String, Node> for children (maintains lexicographical order), a boolean isFile flag, and a StringBuilder content for file data. Implement a path parsing helper that splits paths by /, skips empty strings, and traverses/creates nodes as needed. For example, parsing /a/b/c returns ["a", "b", "c"], and traversal creates missing intermediate nodes. This foundation enables all file system operations.

Solution

class Node:
    def __init__(self):
        self.children = {}  # dict maintains insertion order in Python 3.7+, use sorted() for lex order
        self.is_file = False
        self.content = []
def parse_path(path):
    return [part for part in path.split('/') if part]
def traverse_or_create(root, parts, create=True):
    node = root
    for part in parts:
        if part not in node.children:
            if not create:
                return None
            node.children[part] = Node()
        node = node.children[part]
    return node

Directory Operations (mkdir and ls)

Implement mkdir by parsing the path and creating all intermediate nodes with isFile=false. Implement ls by parsing the path to find the target node: if it's a file, return a list containing only the filename (last path component); if it's a directory, return all children keys from the TreeMap (already sorted). For example, ls("/a/b") on a directory returns ["c", "file.txt"], while ls("/a/b/file.txt") returns ["file.txt"]. These operations use the path parser from Section 1.

Solution

class FileSystem:
    def __init__(self):
        self.root = Node()
    def mkdir(self, path):
        parts = parse_path(path)
        traverse_or_create(self.root, parts, create=True)
    def ls(self, path):
        parts = parse_path(path)
        if not parts:
            return sorted(self.root.children.keys())
        node = traverse_or_create(self.root, parts, create=False)
        if node is None:
            return []
        if node.is_file:
            return [parts[-1]]
        return sorted(node.children.keys())

File Content Operations

Implement addContentToFile by parsing the path, creating intermediate directories and the target file node if missing (set isFile=true), then appending content to the node's StringBuilder. Implement readContentFromFile by parsing the path, navigating to the file node, and returning content.toString(). For example, calling addContentToFile("/a/b/c.txt", "hello") twice with different content appends both strings. These operations leverage the path parser and node structure from previous sections.

Solution

    def addContentToFile(self, path, content):
        parts = parse_path(path)
        if not parts:
            return
        node = traverse_or_create(self.root, parts, create=True)
        node.is_file = True
        node.content.append(content)
    def readContentFromFile(self, path):
        parts = parse_path(path)
        if not parts:
            return ""
        node = traverse_or_create(self.root, parts, create=False)
        if node is None or not node.is_file:
            return ""
        return ''.join(node.content)

Complete File System Integration

Combine the Node structure, path parser, directory operations, and file operations into a unified FileSystem class with a root node initialized as a directory. The class exposes public methods mkdir, ls, addContentToFile, and readContentFromFile that coordinate the components. For example, instantiate FileSystem fs = new FileSystem(), then call fs.mkdir("/a/b") (uses Section 2), fs.addContentToFile("/a/b/file.txt", "data") (uses Section 3), and fs.ls("/a/b") (uses Section 2) to demonstrate the complete workflow from path parsing through operation execution.

Solution

# All components already integrated in previous sections
# Demonstration of complete workflow:
fs = FileSystem()
fs.mkdir("/a/b/c")
fs.addContentToFile("/a/b/file.txt", "hello")
fs.addContentToFile("/a/b/file.txt", " world")
print(fs.ls("/a/b"))  # ['c', 'file.txt']
print(fs.readContentFromFile("/a/b/file.txt"))  # 'hello world'
print(fs.ls("/a/b/file.txt"))  # ['file.txt']

What We've Learned

Pattern: Use trie-like trees with TreeMap for hierarchical data requiring sorted traversal and mixed node types
Use Case: File systems, DOM manipulation, package dependency trees, organizational hierarchies
Optimization: `TreeMap` maintains sorted order automatically, avoiding O(n log n) sorting on every query
Design: Separate path parsing logic from operations for cleaner code and reusability across methods

Problems to Practice

Overview

Lesson

Trie

Tries are tree-based data structures specifically designed for efficient prefix-based operations and hierarchical string storage, which directly parallels the file system's hierarchical path structure. This lesson covers the fundamental trie concepts needed to implement the file system's directory tree.

Learn

Implement Trie Methods

medium

Trie

This problem requires implementing core trie operations (insert, search, startsWith) which are essential building blocks for the file system design. The path parsing and directory traversal in the file system problem uses the same tree navigation patterns as trie operations.

Practice

Prefix Matching

medium

Trie

File system paths are essentially prefix-based hierarchies where each directory level represents a prefix. This problem reinforces the prefix matching and traversal skills needed to navigate and query the file system's tree structure efficiently.

Practice

Question Timeline

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

Company

Level

Region

Mid December, 2025

Snowflake

Senior

Early April, 2025

Uber

Senior

Early August, 2024

Uber

Mid-level

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 588. Design In-Memory File System

DESCRIPTION

Understanding the Problem

Building Intuition

Common Pitfalls

Implementation

Node Structure and Path Parsing

Directory Operations (mkdir and ls)

File Content Operations

Complete File System Integration

What We've Learned

Problems to Practice

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact