Skip to main content
Talentd

Design In-Memory File System - Solution & Explanation

HardPremiumFree on FleetCodeHash TableStringDesignTrie7 min readAsked at: Amazon, Microsoft, Meta +13
Practice this problem

Problem Statement

Design a data structure that simulates an in-memory file system.

Implement the FileSystem class:

  • FileSystem() Initializes the object of the system.
  • List<String> ls(String path)
    • If path is a file path, returns a list that only contains this file's name.
    • If path is a directory path, returns the list of file and directory names in this directory.
    The answer should in lexicographic order.
  • void mkdir(String path) Makes a new directory according to the given path. The given directory path does not exist. If the middle directories in the path do not exist, you should create them as well.
  • void addContentToFile(String filePath, String content)
    • If filePath does not exist, creates that file containing given content.
    • If filePath already exists, appends the given content to original content.
  • String readContentFromFile(String filePath) Returns the content in the file at filePath.

 

Example 1:

Input
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]

Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/"); // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/"); // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"

 

Constraints:

  • 1 <= path.length, filePath.length <= 100
  • path and filePath are absolute paths which begin with '/' and do not end with '/' except that the path is just "/".
  • You can assume that all directory names and file names only contain lowercase letters, and the same names will not exist in the same directory.
  • You can assume that all operations will be passed valid parameters, and users will not attempt to retrieve file content or list a directory or file that does not exist.
  • You can assume that the parent directory for the file in addContentToFile will exist.
  • 1 <= content.length <= 50
  • At most 300 calls will be made to ls, mkdir, addContentToFile, and readContentFromFile.

Approach Overview

Problem Overview: Design a file system that runs entirely in memory. You must support directory listing (ls), creating directories (mkdir), adding content to files (addContentToFile), and reading file content (readContentFromFile) while maintaining lexicographically sorted directory listings.

Approach 1: HashMap-Based Directory Tree (Trie Structure) (Time: O(p + k log k), Space: O(n))

Treat the file system as a tree where each directory is a node and edges represent path segments. Split the path by / and traverse the tree one segment at a time. Each node stores a hash map of children (name → node), a flag indicating whether it is a file, and a string builder for file content. Directory operations like mkdir simply create missing nodes during traversal. For ls, return the file name if the path is a file, otherwise collect child keys and sort them lexicographically. Traversal takes O(p) where p is the number of path components, and sorting the directory listing costs O(k log k) where k is the number of entries.

This approach behaves like a simplified Trie where each level represents a folder name instead of a character. Using a hash table for children ensures constant-time lookup during traversal. File content appends are efficient because you only modify the node representing the file.

Approach 2: Trie with File Metadata and Lazy Sorting (Time: O(p) average, O(k log k) for listing, Space: O(n))

Another implementation models directories and files explicitly with a Trie node class containing metadata such as isFile, content, and a children map. Path traversal works the same way: split the path, iterate through segments, and create nodes when necessary. Instead of sorting every time ls is called, some implementations maintain directory entries in sorted containers or cache sorted results when modifications occur. This reduces repeated sorting overhead when directories are listed frequently.

The Trie structure naturally represents hierarchical file paths, making operations predictable and easy to reason about. String parsing of paths relies on standard string operations, and node traversal handles all file system operations consistently.

Recommended for interviews: The HashMap-backed Trie is the expected solution. It directly models the hierarchical file system and keeps each operation near O(p). Interviewers mainly check whether you design a clean node structure, correctly parse paths, and handle the lexicographic ordering requirement for ls. A simpler map-only idea can show understanding, but the Trie-style directory tree demonstrates solid system design thinking.

Solution

Code

PythonJavaGo

Python

Java

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap Directory Tree (Trie)O(p + k log k)O(n)General case; simple design with fast path traversal and flexible directory growth
Trie with Cached/Ordered ChildrenO(p) average, O(k log k) for listingO(n)When directories are listed frequently and sorting repeatedly becomes expensive

Video Solution

DESIGN IN-MEMORY FILE SYSTEM | LEETCODE # 588 | PYTHON SOLUTION • Cracking FAANG • 17,341 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Design In-Memory File System easy or hard?
Design In-Memory File System is considered a Hard problem because it combines data structure design, path parsing, and multiple operations that must interact correctly. Implementing the Trie-like structure and handling edge cases for files versus directories requires careful coding.
Design In-Memory File System Python/Java solution
Both Python and Java implementations follow the same idea: define a node class with a children map, a file flag, and file content storage. Split the input path by '/', traverse or create nodes, append content for files, and sort child names when returning directory listings.
How to solve Design In-Memory File System in O(n)?
Store the file system as a tree (Trie) where each node represents a directory or file. Traverse the path segments to reach the target node and create missing nodes during mkdir or file creation. Each operation processes path components once, making traversal O(p) while storing nodes takes O(n) total space.
What is the best approach for Design In-Memory File System?
The most common solution uses a Trie-like directory tree where each node stores a hash map of child names to nodes. Paths are split by '/' and traversed sequentially. This structure supports mkdir, file creation, and content appending efficiently while allowing lexicographic sorting of directory entries during ls operations.
Is Design In-Memory File System asked at Google/Amazon/Meta?
Design-style data structure problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. The question tests object-oriented design, Trie structures, and handling hierarchical data with efficient lookups.
What data structure is used in Design In-Memory File System?
A Trie-style tree combined with hash maps is typically used. Each node represents a directory or file and stores a map from name to child node, along with file metadata such as content and a file flag. This structure mirrors how hierarchical file paths work.
What is the time complexity of Design In-Memory File System?
Most operations run in O(p) time where p is the number of path segments. The ls operation may require sorting directory entries, which adds O(k log k) where k is the number of files or subdirectories in that directory. Space complexity is O(n) for storing all files and directories.

Ready to solve this problem?

Practice Design In-Memory File System with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design Log Storage System

Next

LFU Cache