Design In-Memory File System — DSA

Problem#

Design a file system with ls, mkdir, addContentToFile, readContentFromFile. Paths are absolute ("/a/b/c"). ls on a file returns a single-element list with the file name; on a directory, the sorted children.

Examples#

mkdir("/a/b/c"); ls("/") → ["a"].
addContentToFile("/a/b/c/d", "hello"); readContentFromFile("/a/b/c/d") → "hello".

Constraints#

Up to 300 calls.

Approach#

Trie node: children map (name → node), file content string. Walk the path component-by-component creating directories as needed. ls on a file returns just its name; on a dir, sorted children.

Solution#

class FileSystem {
    struct Node {
        map<string, Node*> children;
        string content;
        bool isFile = false;
    };
    Node* root = new Node();
    vector<string> split(const string& path) {
        vector<string> parts;
        string cur;
        for (char c : path) {
            if (c == '/') { if (!cur.empty()) { parts.push_back(cur); cur.clear(); } }
            else cur.push_back(c);
        }
        if (!cur.empty()) parts.push_back(cur);
        return parts;
    }
    Node* walk(const vector<string>& parts, bool create) {
        Node* cur = root;
        for (auto& p : parts) {
            if (!cur->children.count(p)) {
                if (!create) return nullptr;
                cur->children[p] = new Node();
            }
            cur = cur->children[p];
        }
        return cur;
    }
public:
    vector<string> ls(string path) {
        auto parts = split(path);
        Node* n = walk(parts, false);
        if (!n) return {};
        if (n->isFile) return { parts.back() };
        vector<string> out;
        for (auto& [k, _] : n->children) out.push_back(k);
        return out;
    }
    void mkdir(string path) { walk(split(path), true); }
    void addContentToFile(string filePath, string content) {
        auto parts = split(filePath);
        Node* n = walk(parts, true);
        n->isFile = true;
        n->content += content;
    }
    string readContentFromFile(string filePath) {
        Node* n = walk(split(filePath), false);
        return n ? n->content : "";
    }
};

import (
    "sort"
    "strings"
)

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

func newFsNode() *fsNode {
    return &fsNode{children: map[string]*fsNode{}}
}

type FileSystem struct {
    root *fsNode
}

func Constructor() FileSystem {
    return FileSystem{root: newFsNode()}
}

func splitPath(path string) []string {
    parts := []string{}
    for _, p := range strings.Split(path, "/") {
        if p != "" {
            parts = append(parts, p)
        }
    }
    return parts
}

func (fs *FileSystem) walk(parts []string, create bool) *fsNode {
    cur := fs.root
    for _, p := range parts {
        if _, ok := cur.children[p]; !ok {
            if !create {
                return nil
            }
            cur.children[p] = newFsNode()
        }
        cur = cur.children[p]
    }
    return cur
}

func (fs *FileSystem) Ls(path string) []string {
    parts := splitPath(path)
    n := fs.walk(parts, false)
    if n == nil {
        return []string{}
    }
    if n.isFile {
        return []string{parts[len(parts)-1]}
    }
    out := make([]string, 0, len(n.children))
    for k := range n.children {
        out = append(out, k)
    }
    sort.Strings(out)
    return out
}

func (fs *FileSystem) Mkdir(path string) {
    fs.walk(splitPath(path), true)
}

func (fs *FileSystem) AddContentToFile(filePath, content string) {
    n := fs.walk(splitPath(filePath), true)
    n.isFile = true
    n.content += content
}

func (fs *FileSystem) ReadContentFromFile(filePath string) string {
    n := fs.walk(splitPath(filePath), false)
    if n == nil {
        return ""
    }
    return n.content
}

from typing import List, Optional

class _Node:
    __slots__ = ('children', 'content', 'is_file')

    def __init__(self):
        self.children: dict[str, '_Node'] = {}
        self.content: str = ''
        self.is_file: bool = False

class FileSystem:
    def __init__(self):
        self.root = _Node()

    def _split(self, path: str) -> List[str]:
        return [p for p in path.split('/') if p]

    def _walk(self, parts: List[str], create: bool) -> Optional[_Node]:
        cur = self.root
        for p in parts:
            if p not in cur.children:
                if not create:
                    return None
                cur.children[p] = _Node()
            cur = cur.children[p]
        return cur

    def ls(self, path: str) -> List[str]:
        parts = self._split(path)
        n = self._walk(parts, False)
        if n is None:
            return []
        if n.is_file:
            return [parts[-1]]
        return sorted(n.children.keys())

    def mkdir(self, path: str) -> None:
        self._walk(self._split(path), True)

    def addContentToFile(self, filePath: str, content: str) -> None:
        n = self._walk(self._split(filePath), True)
        assert n is not None
        n.is_file = True
        n.content += content

    def readContentFromFile(self, filePath: str) -> str:
        n = self._walk(self._split(filePath), False)
        return n.content if n else ''

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

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

FileSystem.prototype._split = function(path) {
    return path.split('/').filter(p => p.length > 0);
};

FileSystem.prototype._walk = function(parts, create) {
    let cur = this.root;
    for (const p of parts) {
        if (!cur.children.has(p)) {
            if (!create) return null;
            cur.children.set(p, new FsNode());
        }
        cur = cur.children.get(p);
    }
    return cur;
};

FileSystem.prototype.ls = function(path) {
    const parts = this._split(path);
    const n = this._walk(parts, false);
    if (!n) return [];
    if (n.isFile) return [parts[parts.length - 1]];
    return [...n.children.keys()].sort();
};

FileSystem.prototype.mkdir = function(path) {
    this._walk(this._split(path), true);
};

FileSystem.prototype.addContentToFile = function(filePath, content) {
    const n = this._walk(this._split(filePath), true);
    n.isFile = true;
    n.content += content;
};

FileSystem.prototype.readContentFromFile = function(filePath) {
    const n = this._walk(this._split(filePath), false);
    return n ? n.content : '';
};

class FsNode {
    TreeMap<String, FsNode> children = new TreeMap<>();
    String content = "";
    boolean isFile = false;
}

class FileSystem {
    private FsNode root = new FsNode();

    private List<String> split(String path) {
        List<String> parts = new ArrayList<>();
        for (String p : path.split("/")) {
            if (!p.isEmpty()) parts.add(p);
        }
        return parts;
    }

    private FsNode walk(List<String> parts, boolean create) {
        FsNode cur = root;
        for (String p : parts) {
            if (!cur.children.containsKey(p)) {
                if (!create) return null;
                cur.children.put(p, new FsNode());
            }
            cur = cur.children.get(p);
        }
        return cur;
    }

    public List<String> ls(String path) {
        List<String> parts = split(path);
        FsNode n = walk(parts, false);
        if (n == null) return new ArrayList<>();
        if (n.isFile) return new ArrayList<>(List.of(parts.get(parts.size() - 1)));
        return new ArrayList<>(n.children.keySet());
    }

    public void mkdir(String path) {
        walk(split(path), true);
    }

    public void addContentToFile(String filePath, String content) {
        FsNode n = walk(split(filePath), true);
        n.isFile = true;
        n.content += content;
    }

    public String readContentFromFile(String filePath) {
        FsNode n = walk(split(filePath), false);
        return n == null ? "" : n.content;
    }
}

class FsNode {
    children: Map<string, FsNode> = new Map();
    content: string = '';
    isFile: boolean = false;
}

class FileSystem {
    private root: FsNode = new FsNode();

    private split(path: string): string[] {
        return path.split('/').filter(p => p.length > 0);
    }

    private walk(parts: string[], create: boolean): FsNode | null {
        let cur: FsNode = this.root;
        for (const p of parts) {
            if (!cur.children.has(p)) {
                if (!create) return null;
                cur.children.set(p, new FsNode());
            }
            cur = cur.children.get(p) as FsNode;
        }
        return cur;
    }

    ls(path: string): string[] {
        const parts = this.split(path);
        const n = this.walk(parts, false);
        if (!n) return [];
        if (n.isFile) return [parts[parts.length - 1]];
        return [...n.children.keys()].sort();
    }

    mkdir(path: string): void {
        this.walk(this.split(path), true);
    }

    addContentToFile(filePath: string, content: string): void {
        const n = this.walk(this.split(filePath), true) as FsNode;
        n.isFile = true;
        n.content += content;
    }

    readContentFromFile(filePath: string): string {
        const n = this.walk(this.split(filePath), false);
        return n ? n.content : '';
    }
}

Editorial#

Using std::map keeps children sorted automatically, eliminating an explicit sort in ls. Treating files as trie leaves with the isFile flag avoids a separate file-vs-dir representation. addContentToFile is idempotent on directory creation — walks the path with create = true and appends content.

Complexity#

Time: O(L) per op (L = path length); ls on a directory is O(L + k log k) for k children.
Space: proportional to total paths.

Concept revision#

Design File System