Design In-Memory File System - Practice Coding Problems

Design In-Memory File System - Problem

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 be 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

Input & Output

Example 1 — Basic File System Operations

$ Input: operations = ["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"] parameters = [[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/a/b/c"], ["/a/b/c/d"]]

› Output: [null, [], null, null, ["d"], "hello"]

💡 Note: Initialize file system, list root (empty), create directory /a/b/c, add file /a/b/c/d with content "hello", list /a/b/c contents (shows file "d"), read file content (returns "hello")

Example 2 — File Content Append

$ Input: operations = ["FileSystem", "addContentToFile", "readContentFromFile", "addContentToFile", "readContentFromFile"] parameters = [[], ["/a", "hello"], ["/a"], ["/a", " world"], ["/a"]]

› Output: [null, null, "hello", null, "hello world"]

💡 Note: Create file /a with "hello", read it (returns "hello"), append " world" to /a, read again (returns "hello world")

Example 3 — Directory Listing

$ Input: operations = ["FileSystem", "mkdir", "mkdir", "addContentToFile", "ls"] parameters = [[], ["/a"], ["/b"], ["/c.txt", "content"], ["/"]]

› Output: [null, null, null, null, ["a", "b", "c.txt"]]

💡 Note: Create directories /a and /b, create file /c.txt, then list root directory contents in lexicographic order

Constraints

1 ≤ operations.length ≤ 300
1 ≤ path.length, filePath.length ≤ 100
1 ≤ content.length ≤ 50
All paths are absolute paths starting with '/'
All inputs consist of lowercase English letters, digits, '/', and '.'
You can assume that all operations are valid

Visualization

Tap to expand

Understanding the Visualization

Input Operations

Sequence of file system commands like mkdir, ls, addContentToFile

Trie Structure

Build tree where nodes are directories/files with parent-child relationships

Output Results

Return appropriate responses: null for void operations, lists for ls, strings for read

Key Takeaway

🎯 Key Insight: Use trie structure where each node has a hash map of children for O(1) lookup and efficient path navigation

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to use a trie (prefix tree) data structure where each node represents a directory or file. The optimal approach uses hash maps at each node for O(1) child lookup while maintaining lexicographic order through sorting. Time: O(m) per operation where m is path length, Space: O(n×m) for storing all paths in the trie.

Common Approaches

Approach	Time	Space	Notes
✓ Trie-based File System	O(m)	O(n×m)	Use trie (prefix tree) structure to efficiently represent the file system hierarchy
String-based Storage	O(n×m)	O(n×m)	Store all paths as strings and parse them for each operation

Trie-based File System — Algorithm Steps

Create trie node with children map and content field
Navigate path by following trie edges
Store files and directories as trie nodes with appropriate flags

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Trie

Each directory becomes a trie node with children map

Navigate Path

Follow trie edges to reach target node

Fast Access

O(path_length) time for all operations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CHILDREN 1000
#define MAX_NAME_LEN 100
#define MAX_CONTENT_LEN 10000

typedef struct TrieNode {
    struct TrieNode* children[MAX_CHILDREN];
    char childNames[MAX_CHILDREN][MAX_NAME_LEN];
    int childCount;
    int isFile;
    char content[MAX_CONTENT_LEN];
} TrieNode;

TrieNode* createTrieNode() {
    TrieNode* node = malloc(sizeof(TrieNode));
    node->childCount = 0;
    node->isFile = 0;
    node->content[0] = '\0';
    return node;
}

typedef struct {
    TrieNode* root;
} FileSystem;

FileSystem* fileSystemCreate() {
    FileSystem* fs = malloc(sizeof(FileSystem));
    fs->root = createTrieNode();
    return fs;
}

char** solution(char** operations, int ops_size, char*** parameters, int* returnSize) {
    *returnSize = ops_size;
    return malloc(ops_size * sizeof(char*));
}

int main() {
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m)

Operations take O(m) where m is the path length, as we traverse the trie depth

✓ Linear Growth

Space Complexity

O(n×m)

Trie stores all paths, with n nodes and average path depth m

⚡ Linearithmic Space

28.0K Views

High Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Trie-based File System — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler