Problem 40.11 · Designing Data StructuresMedium

Design File System

PatternCombine Structures to Design Trie (Prefix Tree)Hash Map Lookup (Complement)

What it teaches: Paths as keys: a parent must exist before its child, which is a prefix check (map of full paths, or a trie of path parts).

Practise it on judges as “Design File System”.

In plain words

Think of folders on a computer: you can't create /photos/2024 until /photos exists. Each folder here also stores a number.

Build createPath(path, value) (return false if the path already exists or its parent doesn't) and get(path) (the stored number, or −1).

The problem

Design FileSystem with createPath(path, value) and get(path). Paths look like "/a/b". Creating fails if the path exists or its parent path (everything before the last '/') doesn't exist (the root "" always exists).

Example 1

Input: createPath("/leet", 1), createPath("/leet/code", 2), get("/leet/code"), createPath("/c/d", 1), get("/c")
Output: true, true, 2, false, -1

Constraints

Up to 10⁴ calls
Paths are valid and use lowercase letters

Pattern clues in the wording

→ Hierarchical keys
→ Parent must exist

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

FileSystem · starter

import java.util.*;

class FileSystem {
    public FileSystem() {}
    public boolean createPath(String path, int value) { return false; }
    public int get(String path) { return -1; }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["FileSystem","createPath","get"] args = [[],["/a",1],["/a"]]	[null,true,1]
2	ops = ["FileSystem","createPath","createPath","get","createPath","get"] args = [[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]	[null,true,true,2,false,-1]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Map of full paths · O(L) per call for string work 2. Trie of path parts · O(parts) per call

Map of full paths

Time O(L) per call for string work Space O(total path length)

paths: HashMap from full path to value. createPath checks the path is new and the parent is either "" or present.

Approach 1

import java.util.*;

class FileSystem {
    private final Map<String, Integer> paths = new HashMap<>();

    public FileSystem() {}

    public boolean createPath(String path, int value) {
        if (path.isEmpty() || path.equals("/") || paths.containsKey(path)) return false;
        String parent = path.substring(0, path.lastIndexOf('/'));
        if (!parent.isEmpty() && !paths.containsKey(parent)) return false;
        paths.put(path, value);
        return true;
    }

    public int get(String path) { return paths.getOrDefault(path, -1); }
}

Verdict: Simplest correct design.

Trie of path parts

Time O(parts) per call Space O(total parts)

Each folder name is an edge from its parent node. Walk all parts but the last; they must exist; create the last if new.

▶ Dry run: Walk the folder tree part by partcreatePath("/leet", 1), createPath("/leet/code", 2), get("/leet/code"), createPath("/c/d", 1), get("/c")

tree(list)

root leet (1)

returned(list)

true

Step 1/5createPath("/leet", 1): parts = ["", "leet"]. The parent is the root, which always exists, and has no child leet. Add it with value 1.

Approach 2

import java.util.*;

class FileSystem {
    private static class Dir {
        final Map<String, Dir> children = new HashMap<>();
        int value = -1;
    }

    private final Dir root = new Dir();

    public FileSystem() {}

    public boolean createPath(String path, int value) {
        String[] parts = path.split("/");                    // parts[0] is "" before the first slash
        Dir cur = root;
        for (int i = 1; i < parts.length - 1; i++) {
            cur = cur.children.get(parts[i]);
            if (cur == null) return false;                   // missing parent
        }
        String last = parts[parts.length - 1];
        if (cur.children.containsKey(last)) return false;   // already exists
        Dir d = new Dir();
        d.value = value;
        cur.children.put(last, d);
        return true;
    }

    public int get(String path) {
        String[] parts = path.split("/");
        Dir cur = root;
        for (int i = 1; i < parts.length && cur != null; i++) cur = cur.children.get(parts[i]);
        return cur == null ? -1 : cur.value;
    }
}

Verdict: Supports listing a folder's children cheaply.

Before you submit

Edge cases and common mistakes

Test these inputs

Creating an existing path
Missing parent several levels up

Mistakes people make

Only checking that the immediate parent string is non-empty, not that it exists.

Interview

Follow-up questions

How would you list everything under "/leet"?

Command Palette