Design In-Memory File System

Build a tiny file system that lives in memory. Paths are absolute, start with /, and use / between names (the root itself is "/"; no other path ends with a slash). Implement the class FileSystem:

• FileSystem() starts with only the empty root directory.
• ls(path): if path is a file, return a list containing just that file's name. If it is a directory, return the names of everything directly inside it (files and directories), sorted lexicographically.
• mkdir(path) creates the directory and any missing parent directories. If it already exists, nothing happens.
• addContentToFile(filePath, content) creates the file (and missing parent directories) if needed, then appends content to the end of it.
• readContentFromFile(filePath) returns the file's full content.

Each test lists operation names and their arguments; the output holds every return value, with null for the constructor and methods that return nothing.

Example 1

Example 2

Example 3

Constraints

• 1 <= path.length, filePath.length <= 100
• Names contain only lowercase English letters; content contains lowercase letters and spaces (1 to 50 characters).
• ls is only called on paths that exist, and readContentFromFile only on existing files.
• No call ever uses a file as a directory or a directory as a file.
• At most 1000 calls in total.

Pattern Path · Design · problem 169 of 169

Start simple

Keep a flat dictionary from full path string to content and, for ls, scan every stored path for those that start with the directory prefix: O(total paths · path length) per ls.

The key idea

A file system is a tree, and a path is a walk from the root down that tree, one name per level. This is the same shape as a trie, except that each edge is labelled with a whole name instead of a single character.

Give every entry a children map from name to entry, an isFile flag and a content string. Then write one helper, find(path), that splits the path on /, skips the empty first piece, and walks down the maps, creating an empty entry whenever a name is missing. With that single helper:

• mkdir just calls find; creating parents and ignoring an existing directory both come for free.
• addContentToFile calls find, marks the entry as a file and appends to its content.
• readContentFromFile returns the content of the found entry.
• ls returns the last name of the path for a file, or the sorted keys of children for a directory.

Each operation costs time proportional to the path length, plus O(k log k) for sorting the k children in ls. Nothing outside the visited branch is touched, unlike the flat-dictionary approach.

Complexity

• Time: O(L) per call, plus O(k log k) for ls on a directory with k entries (L = path length)
• Space: O(total length of names and content)

Python

class Entry:
    """A directory (is_file False) or a file (is_file True) in the tree."""
    def __init__(self):
        self.children = {}   # name -> Entry, used by directories
        self.is_file = False
        self.content = ""    # used by files


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

    def _find(self, path: str) -> Entry:
        """Walk to the entry at path, creating missing directories along the way."""
        node = self.root
        for name in path.split("/"):
            if name:  # skip the empty piece before the leading "/"
                node = node.children.setdefault(name, Entry())
        return node

    def ls(self, path: str) -> List[str]:
        node = self._find(path)
        if node.is_file:
            return [path.split("/")[-1]]
        return sorted(node.children)

    def mkdir(self, path: str) -> None:
        self._find(path)

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self._find(filePath)
        node.is_file = True
        node.content += content

    def readContentFromFile(self, filePath: str) -> str:
        return self._find(filePath).content

JavaScript

// A directory (isFile false) or a file (isFile true) in the tree.
class Entry {
  constructor() {
    this.children = new Map(); // name -> Entry, used by directories
    this.isFile = false;
    this.content = "";         // used by files
  }
}

class FileSystem {
  constructor() {
    this.root = new Entry();
  }

  // Walk to the entry at path, creating missing directories along the way.
  find(path) {
    let node = this.root;
    for (const name of path.split("/")) {
      if (!name) continue; // skip the empty piece before the leading "/"
      if (!node.children.has(name)) node.children.set(name, new Entry());
      node = node.children.get(name);
    }
    return node;
  }

  ls(path) {
    const node = this.find(path);
    if (node.isFile) return [path.split("/").pop()];
    return [...node.children.keys()].sort();
  }

  mkdir(path) {
    this.find(path);
  }

  addContentToFile(filePath, content) {
    const node = this.find(filePath);
    node.isFile = true;
    node.content += content;
  }

  readContentFromFile(filePath) {
    return this.find(filePath).content;
  }
}

What the interviewer is checking

This is about modelling: turning a vague spec into a clean tree-of-maps structure, sharing one path-walking helper across operations, and handling the root and file-versus-directory cases precisely.

Mistakes to avoid

• Splitting "/" or "/a" on / produces empty strings; they must be skipped, or the root gets a child named "".
• Overwriting a file's content instead of appending to it.
• Returning the full path, or every name on it, when ls is called on a file; only the file's own name is expected.
• Forgetting to sort the names returned by ls.

Follow-ups to expect

• Add rm and mv. (Detach or re-link a subtree in the parent's map.)
• Make ls fast for huge directories. (Keep children in a sorted map.)
• Report the total size of a directory. (Cache subtree sizes, update on append.)

In real software

Virtual file systems in containers, in-browser IDEs and object stores that simulate folders all keep a tree of name-to-node maps, and URL routers resolve paths segment by segment in the same way.

Practice next