Design In-Memory File System

Hard Tries Basics Original on LeetCode

Design In-Memory File System is a hard tries problem solved with the basics pattern. The best approach, optimal (trie of path components), runs in O(L + k) per call time and O(total names and content) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (flat maps of full paths) up.

Problem

Build a class FileSystem that simulates a small in-memory file system made of directories and text files. FileSystem() starts with only the empty root directory "/".

  • ls(String path): if path is a file, return a list containing only that file’s name. If it is a directory, return the names of the files and directories directly inside it, in lexicographic order.
  • mkdir(String path): create the directory path, along with any missing directories on the way to it. Directories that already exist are left alone.
  • addContentToFile(String filePath, String content): if the file does not exist, create it (and any missing directories above it) with content; otherwise append content to the end of what it already holds.
  • readContentFromFile(String filePath): return the full content of the file.

Examples

Example 1

Input
FileSystem(), mkdir("/docs/notes"), addContentToFile("/docs/todo", "buy milk"), ls("/"), ls("/docs"), addContentToFile("/docs/todo", " and eggs"), readContentFromFile("/docs/todo")
Output
["docs"], ["notes", "todo"], "buy milk and eggs"
Why
mkdir creates both docs and docs/notes; the second write appends to the existing file instead of replacing it.

Example 2

Input
FileSystem(), addContentToFile("/a/b/report", "hi"), ls("/a/b/report"), mkdir("/a/apple"), ls("/a"), ls("/a/apple")
Output
["report"], ["apple", "b"], []
Why
ls on a file lists just that file's name; ls on a directory lists its entries in lexicographic order, and an empty directory gives an empty list.

Constraints

  • 1 <= path.length, filePath.length <= 100
  • Every path is absolute: it starts with /, and has no trailing / unless it is the root "/" itself.
  • Directory and file names are non-empty and use lowercase English letters only.
  • No name is used for both a file and a directory at the same location.
  • ls is only called on paths that exist, and readContentFromFile only on files that exist.
  • 1 <= content.length <= 50
  • At most 300 calls in total.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (flat maps of full paths)O(N · L + k log k) per ls, O(L) per other callO(N · L)
Optimal (trie of path components)O(L + k) per callO(total names and content)

1Brute force (flat maps of full paths)

TimeO(N · L + k log k) per ls, O(L) per other callls scans all N stored paths of length up to L, then sorts the k names it found.
SpaceO(N · L)Every directory and file path is stored in full.

Do not build a tree at all. Keep a set of every directory path and a map from each file path to its content. To list a directory, scan every stored path, keep the ones directly or indirectly below it, cut each down to its first name after the directory, and sort the distinct names.

  1. dirs = {"/"}, files = empty map.
  2. mkdir(path): add the path and every ancestor prefix to dirs.
  3. addContentToFile(fp, c): add the parent directory and its ancestors to dirs, then append c to files[fp] (starting from an empty string).
  4. readContentFromFile(fp): return files[fp].
  5. ls(path): if path is a file, return its last name. Otherwise, with prefix = path + "/" (or "/" for the root), collect the first name after the prefix from every stored path that starts with it, and return those names sorted.
class FileSystem {
    private final Set<String> dirs = new HashSet<>();
    private final Map<String, String> files = new HashMap<>();

    public FileSystem() {
        dirs.add("/");
    }

    private void makeDirs(String path) {
        int i = path.indexOf('/', 1);
        while (i != -1) {
            dirs.add(path.substring(0, i));
            i = path.indexOf('/', i + 1);
        }
        dirs.add(path);
    }

    private void collect(String p, String prefix, Set<String> names) {
        if (p.length() > prefix.length() && p.startsWith(prefix)) {
            String rest = p.substring(prefix.length());
            int k = rest.indexOf('/');
            names.add(k < 0 ? rest : rest.substring(0, k));
        }
    }

    public List<String> ls(String path) {
        List<String> res = new ArrayList<>();
        if (files.containsKey(path)) {
            res.add(path.substring(path.lastIndexOf('/') + 1));
            return res;
        }
        String prefix = path.equals("/") ? "/" : path + "/";
        TreeSet<String> names = new TreeSet<>();
        for (String p : dirs) collect(p, prefix, names);
        for (String p : files.keySet()) collect(p, prefix, names);
        res.addAll(names);
        return res;
    }

    public void mkdir(String path) {
        makeDirs(path);
    }

    public void addContentToFile(String filePath, String content) {
        int k = filePath.lastIndexOf('/');
        if (k > 0) makeDirs(filePath.substring(0, k));
        files.put(filePath, files.getOrDefault(filePath, "") + content);
    }

    public String readContentFromFile(String filePath) {
        return files.get(filePath);
    }
}

2Optimal (trie of path components)

TimeO(L + k) per callA call walks the L characters of its path (each step a sorted-map lookup on a short name) and ls copies out the k child names.
SpaceO(total names and content)Each directory or file name is stored once in the tree, shared by every path that goes through it.

Model the file system as a tree: each node is a directory or a file and maps child names to child nodes, kept in a sorted map. Walking a path means following one child per name, creating missing nodes as you go, which handles mkdir -p style creation for free. A file node also has a content buffer. ls on a directory is just the sorted keys of its child map.

  1. Node = { sorted map name -> Node, isFile flag, content buffer }; root is an empty directory.
  2. walk(path): split on /, skip empty pieces, and for each name step into that child, creating it if missing.
  3. mkdir(path): walk(path).
  4. addContentToFile(fp, c): node = walk(fp); mark it as a file and append c.
  5. readContentFromFile(fp): return walk(fp)'s content.
  6. ls(path): node = walk(path); if it is a file, return [its last name]; otherwise return its child names in order.
class FileSystem {
    private static class Node {
        TreeMap<String, Node> children = new TreeMap<>();
        boolean isFile;
        StringBuilder content = new StringBuilder();
    }

    private final Node root = new Node();

    public FileSystem() {}

    private Node walk(String path) {
        Node cur = root;
        for (String part : path.split("/")) {
            if (part.isEmpty()) continue;
            cur = cur.children.computeIfAbsent(part, k -> new Node());
        }
        return cur;
    }

    public List<String> ls(String path) {
        Node node = walk(path);
        List<String> res = new ArrayList<>();
        if (node.isFile) {
            res.add(path.substring(path.lastIndexOf('/') + 1));
        } else {
            res.addAll(node.children.keySet());
        }
        return res;
    }

    public void mkdir(String path) {
        walk(path);
    }

    public void addContentToFile(String filePath, String content) {
        Node node = walk(filePath);
        node.isFile = true;
        node.content.append(content);
    }

    public String readContentFromFile(String filePath) {
        return walk(filePath).content.toString();
    }
}

Edge cases to test

  • ls("/") on a brand new file system returns an empty list
  • ls on a file returns a one-element list with the file's own name
  • mkdir on a deep path creates every missing directory along the way, and is harmless if they already exist
  • Writing to a new file inside missing directories creates those directories too
  • Several writes to the same file append, in order

Hints

Hint 1

A path is a sequence of names. Split it on / and ignore the empty pieces.

Hint 2

A tree whose nodes are directories or files, with each node mapping child names to child nodes, mirrors the file system directly. That is a trie over path components.

Hint 3

If each node keeps its children in a sorted map, ls on a directory is simply the list of its keys. A node also needs a flag saying it is a file and a buffer for the content.

FAQ

What is the best time complexity for Design In-Memory File System?

Optimal (trie of path components) runs in O(L + k) per call time and O(total names and content) extra space. A call walks the L characters of its path (each step a sorted-map lookup on a short name) and ls copies out the k child names.

Which pattern does Design In-Memory File System use?

It is a tries problem that uses the basics pattern. Other problems with the same pattern: Implement Trie (Prefix Tree), Implement Trie ll, Design Search Autocomplete System.

Is there a brute force solution for Design In-Memory File System?

Yes. Brute force (flat maps of full paths) takes O(N · L + k log k) per ls, O(L) per other call time and O(N · L) space. Do not build a tree at all.

Which edge cases should I test for Design In-Memory File System?

ls("/") on a brand new file system returns an empty list; ls on a file returns a one-element list with the file's own name; mkdir on a deep path creates every missing directory along the way, and is harmless if they already exist; Writing to a new file inside missing directories creates those directories too; Several writes to the same file append, in order.