588. Design In-Memory File System

At a Glance

Topic: system-design-coding
Pattern: Trie / prefix tree over path segments + per-node metadata (isFile, content)
Difficulty: Hard
Companies: Amazon, Google, Meta, Uber, Snap
Frequency: Medium
LeetCode: 588

Problem (one-liner)

Simulate an in-memory FS: ls (list immediate children or wrap a single file name), mkdir, addContentToFile (append, create path if needed), readContentFromFile.

Recognition Cues

Paths are absolute strings split by /
Prefix creation along path — trie of segment names (same spine as 208. Implement Trie, but each node may be directory or file)
ls on a file path returns only that file’s basename — distinguish leaf type

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Flat map[string][]string of full paths — works until you need partial listing without storing children lists per directory — awkward for ls /a/b.
Optimal — tree of nodes: children map[string]*node, flags isFile, content string; walk segments from root.

Optimal Solution

Go

package main

import "sort"

type fsNode struct {
	children map[string]*fsNode
	isFile   bool
	content  string
}

type FileSystem struct {
	root *fsNode
}

func Constructor() FileSystem {
	return FileSystem{
		root: &fsNode{children: make(map[string]*fsNode)},
	}
}

func splitPath(path string) []string {
	var segments []string
	start := 0
	for index := 0; index < len(path); index++ {
		if path[index] == '/' {
			if start < index {
				segments = append(segments, path[start:index])
			}
			start = index + 1
		}
	}
	if start < len(path) {
		segments = append(segments, path[start:])
	}
	return segments
}

func (filesystem *FileSystem) navigate(segments []string, create bool) *fsNode {
	current := filesystem.root
	for _, name := range segments {
		next, exists := current.children[name]
		if !exists {
			if !create {
				return nil
			}
			next = &fsNode{children: make(map[string]*fsNode)}
			current.children[name] = next
		}
		current = next
	}
	return current
}

func (filesystem *FileSystem) Ls(path string) []string {
	segments := splitPath(path)
	if len(segments) == 0 {
		return filesystem.listDirectory(filesystem.root)
	}
	parentSegments := segments[:len(segments)-1]
	basename := segments[len(segments)-1]
	var parent *fsNode
	if len(parentSegments) == 0 {
		parent = filesystem.root
	} else {
		parent = filesystem.navigate(parentSegments, false)
		if parent == nil {
			return []string{}
		}
	}
	target, exists := parent.children[basename]
	if !exists {
		return []string{}
	}
	if target.isFile {
		return []string{basename}
	}
	return filesystem.listDirectory(target)
}

func (filesystem *FileSystem) listDirectory(directory *fsNode) []string {
	names := make([]string, 0, len(directory.children))
	for name := range directory.children {
		names = append(names, name)
	}
	sort.Strings(names)
	return names
}

func (filesystem *FileSystem) Mkdir(path string) {
	segments := splitPath(path)
	filesystem.navigate(segments, true)
}

func (filesystem *FileSystem) AddContentToFile(filePath string, text string) {
	segments := splitPath(filePath)
	if len(segments) == 0 {
		return
	}
	parentSegments := segments[:len(segments)-1]
	basename := segments[len(segments)-1]
	var parent *fsNode
	if len(parentSegments) == 0 {
		parent = filesystem.root
	} else {
		parent = filesystem.navigate(parentSegments, true)
	}
	fileNode, exists := parent.children[basename]
	if !exists {
		fileNode = &fsNode{children: nil, isFile: true}
		parent.children[basename] = fileNode
	}
	fileNode.isFile = true
	fileNode.content += text
}

func (filesystem *FileSystem) ReadContentFromFile(filePath string) string {
	segments := splitPath(filePath)
	if len(segments) == 0 {
		return ""
	}
	parentSegments := segments[:len(segments)-1]
	basename := segments[len(segments)-1]
	var parent *fsNode
	if len(parentSegments) == 0 {
		parent = filesystem.root
	} else {
		parent = filesystem.navigate(parentSegments, false)
		if parent == nil {
			return ""
		}
	}
	fileNode, exists := parent.children[basename]
	if !exists || !fileNode.isFile {
		return ""
	}
	return fileNode.content
}

JavaScript

class FsNode {
	constructor() {
		this.children = new Map();
		this.isFile = false;
		this.content = '';
	}
}

var FileSystem = function () {
	this.root = new FsNode();
};

FileSystem.prototype._split = function (path) {
	if (path === '/') {
		return [];
	}
	return path.split('/').filter(Boolean);
};

FileSystem.prototype._navigate = function (segments, create) {
	let current = this.root;
	for (const name of segments) {
		if (!current.children.has(name)) {
			if (!create) {
				return null;
			}
			current.children.set(name, new FsNode());
		}
		current = current.children.get(name);
	}
	return current;
};

/**
 * @param {string} path
 * @return {string[]}
 */
FileSystem.prototype.ls = function (path) {
	const segments = this._split(path);
	if (segments.length === 0) {
		return this._listDir(this.root);
	}
	const parentSegments = segments.slice(0, -1);
	const basename = segments[segments.length - 1];
	const parent =
		parentSegments.length === 0 ? this.root : this._navigate(parentSegments, false);
	if (!parent) {
		return [];
	}
	const target = parent.children.get(basename);
	if (!target) {
		return [];
	}
	if (target.isFile) {
		return [basename];
	}
	return this._listDir(target);
};

FileSystem.prototype._listDir = function (directory) {
	return Array.from(directory.children.keys()).sort();
};

/**
 * @param {string} path
 * @return {void}
 */
FileSystem.prototype.mkdir = function (path) {
	const segments = this._split(path);
	this._navigate(segments, true);
};

/**
 * @param {string} filePath
 * @param {string} content
 * @return {void}
 */
FileSystem.prototype.addContentToFile = function (filePath, content) {
	const segments = this._split(filePath);
	if (segments.length === 0) {
		return;
	}
	const parentSegments = segments.slice(0, -1);
	const basename = segments[segments.length - 1];
	const parent =
		parentSegments.length === 0 ? this.root : this._navigate(parentSegments, true);
	if (!parent.children.has(basename)) {
		const fileNode = new FsNode();
		fileNode.isFile = true;
		parent.children.set(basename, fileNode);
	}
	const fileNode = parent.children.get(basename);
	fileNode.isFile = true;
	fileNode.content += content;
};

/**
 * @param {string} filePath
 * @return {string}
 */
FileSystem.prototype.readContentFromFile = function (filePath) {
	const segments = this._split(filePath);
	if (segments.length === 0) {
		return '';
	}
	const parentSegments = segments.slice(0, -1);
	const basename = segments[segments.length - 1];
	const parent =
		parentSegments.length === 0 ? this.root : this._navigate(parentSegments, false);
	if (!parent) {
		return '';
	}
	const fileNode = parent.children.get(basename);
	if (!fileNode || !fileNode.isFile) {
		return '';
	}
	return fileNode.content;
};

Walkthrough

mkdir /a/b, addContent /a/b/c "hello": walk creates a, b; under b create file leaf c with content. ls /a/b → ["c"]. ls /a/b/c → ["c"] (file listing rule).

Invariant: Every directory node has a nonempty children map when created; file nodes may keep children nil — always consult isFile before treating as directory.

Edge Cases

ls "/" — list root children sorted
Path is a file — ls returns single-element list with basename only
mkdir on nested path — intermediate dirs materialized
Empty content append — still creates file if missing

Pitfalls

Mixing full path strings as keys vs segment-wise trie — segment trie avoids false /ab vs /a/b collisions
Forgetting sort on directory listings — required by problem
Treating a file node as navigable for further mkdir under it — often invalid; clarify problem (usually files are leaves)

Variants

Hard/soft links — graph, not tree — cycle detection on resolve
mv / cp — subtree cut/paste with refcount or copy-on-write
Quota / eviction — LRU of file contents under byte budget

Mind-Map Tags

#trie #path-segments #tree-of-maps #sorted-ls #in-memory-fs