Design File System

Problem

You are asked to design a file system that allows you to create new paths and associate them with different values.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string "" and "/" are not.

Implement the FileSystem class:

• bool createPath(string path, int value) Creates a new path and associates a value to it if possible and returns true. Returns false if the path already exists or its parent path doesn 't exist.
• int get(string path) Returns the value associated with path or returns -1 if the path doesn't exist.

Examples

Example 1:

Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

Example 2:

Input: 
["FileSystem","createPath","createPath","get","createPath","get"]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]
Output: 
[null,true,true,2,false,-1]
Explanation: 
FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/leet", 1); // return true
fileSystem.createPath("/leet/code", 2); // return true
fileSystem.get("/leet/code"); // return 2
fileSystem.createPath("/c/d", 1); // return false because the parent path "/c" doesn't exist.
fileSystem.get("/c"); // return -1 because this path doesn't exist.

Constraints:

• 2 <= path.length <= 100
• 1 <= value <= 10^9
• Each path is valid and consists of lowercase English letters and '/'.
• At most 104 calls in total will be made to createPath and get.

Solution

Method 1 – Trie (Prefix Tree) for Path Management

Intuition

A file system can be modeled as a tree (trie), where each node represents a directory or file. Each path is split by '/', and we traverse or create nodes accordingly. We only allow creating a path if its parent exists and the path does not already exist.

Approach

1. Use a trie node class with a dictionary for children and an integer for value (default -1 for non-existent).
2. For createPath, split the path by '/', traverse the trie, and check if the parent exists and the path does not exist. If valid, create the node and set its value.
3. For get, traverse the trie by splitting the path and return the value if the node exists, else return -1.
4. Edge cases: root ('/') is not a valid path to create or get.

Code

C++

class FileSystem {
    struct Node {
        unordered_map<string, Node*> ch;
        int val = -1;
    } *root;
public:
    FileSystem() { root = new Node(); }
    bool createPath(string path, int value) {
        auto v = root;
        vector<string> parts;
        stringstream ss(path);
        string s;
        while (getline(ss, s, '/')) if (!s.empty()) parts.push_back(s);
        for (int i = 0; i + 1 < parts.size(); ++i) {
            if (!v->ch.count(parts[i])) return false;
            v = v->ch[parts[i]];
        }
        string last = parts.back();
        if (v->ch.count(last)) return false;
        v->ch[last] = new Node();
        v->ch[last]->val = value;
        return true;
    }
    int get(string path) {
        auto v = root;
        vector<string> parts;
        stringstream ss(path);
        string s;
        while (getline(ss, s, '/')) if (!s.empty()) parts.push_back(s);
        for (auto& p : parts) {
            if (!v->ch.count(p)) return -1;
            v = v->ch[p];
        }
        return v->val;
    }
};

Go

type Node struct {
    ch map[string]*Node
    val int
}

type FileSystem struct {
    root *Node
}

func Constructor() FileSystem {
    return FileSystem{&Node{ch: map[string]*Node{}, val: -1}}
}

func (fs *FileSystem) CreatePath(path string, value int) bool {
    v := fs.root
    parts := strings.Split(path, "/")
    var segs []string
    for _, s := range parts {
        if s != "" {
            segs = append(segs, s)
        }
    }
    for i := 0; i+1 < len(segs); i++ {
        if _, ok := v.ch[segs[i]]; !ok {
            return false
        }
        v = v.ch[segs[i]]
    }
    last := segs[len(segs)-1]
    if _, ok := v.ch[last]; ok {
        return false
    }
    v.ch[last] = &Node{ch: map[string]*Node{}, val: value}
    return true
}

func (fs *FileSystem) Get(path string) int {
    v := fs.root
    parts := strings.Split(path, "/")
    var segs []string
    for _, s := range parts {
        if s != "" {
            segs = append(segs, s)
        }
    }
    for _, p := range segs {
        if _, ok := v.ch[p]; !ok {
            return -1
        }
        v = v.ch[p]
    }
    return v.val
}

Java

public class FileSystem {
    static class Node {
        Map<String, Node> ch = new HashMap<>();
        int val = -1;
    }
    Node root;
    public FileSystem() { root = new Node(); }
    public boolean createPath(String path, int value) {
        String[] parts = Arrays.stream(path.split("/")).filter(s -> !s.isEmpty()).toArray(String[]::new);
        Node v = root;
        for (int i = 0; i + 1 < parts.length; i++) {
            if (!v.ch.containsKey(parts[i])) return false;
            v = v.ch.get(parts[i]);
        }
        String last = parts[parts.length - 1];
        if (v.ch.containsKey(last)) return false;
        Node n = new Node();
        n.val = value;
        v.ch.put(last, n);
        return true;
    }
    public int get(String path) {
        String[] parts = Arrays.stream(path.split("/")).filter(s -> !s.isEmpty()).toArray(String[]::new);
        Node v = root;
        for (String p : parts) {
            if (!v.ch.containsKey(p)) return -1;
            v = v.ch.get(p);
        }
        return v.val;
    }
}

Kotlin

class FileSystem {
    class Node {
        val ch = mutableMapOf<String, Node>()
        var val_ = -1
    }
    private val root = Node()
    fun createPath(path: String, value: Int): Boolean {
        val parts = path.split("/").filter { it.isNotEmpty() }
        var v = root
        for (i in 0 until parts.size - 1) {
            v = v.ch[parts[i]] ?: return false
        }
        val last = parts.last()
        if (v.ch.containsKey(last)) return false
        v.ch[last] = Node().apply { val_ = value }
        return true
    }
    fun get(path: String): Int {
        val parts = path.split("/").filter { it.isNotEmpty() }
        var v = root
        for (p in parts) {
            v = v.ch[p] ?: return -1
        }
        return v.val_
    }
}

Python

class FileSystem:
    class Node:
        def __init__(self):
            self.ch = {}
            self.val = -1
    def __init__(self):
        self.root = self.Node()
    def createPath(self, path: str, value: int) -> bool:
        parts = [p for p in path.split('/') if p]
        v = self.root
        for i in range(len(parts)-1):
            if parts[i] not in v.ch:
                return False
            v = v.ch[parts[i]]
        last = parts[-1]
        if last in v.ch:
            return False
        v.ch[last] = self.Node()
        v.ch[last].val = value
        return True
    def get(self, path: str) -> int:
        parts = [p for p in path.split('/') if p]
        v = self.root
        for p in parts:
            if p not in v.ch:
                return -1
            v = v.ch[p]
        return v.val

Rust

use std::collections::HashMap;
struct Node {
    ch: HashMap<String, Box<Node>>,
    val: i32,
}
struct FileSystem {
    root: Box<Node>,
}
impl FileSystem {
    fn new() -> Self {
        FileSystem { root: Box::new(Node { ch: HashMap::new(), val: -1 }) }
    }
    fn create_path(&mut self, path: String, value: i32) -> bool {
        let parts: Vec<&str> = path.split('/').filter(|s| !s.is_empty()).collect();
        let mut v = &mut self.root;
        for i in 0..parts.len()-1 {
            if !v.ch.contains_key(parts[i]) {
                return false;
            }
            v = v.ch.get_mut(parts[i]).unwrap();
        }
        let last = parts[parts.len()-1];
        if v.ch.contains_key(last) {
            return false;
        }
        v.ch.insert(last.to_string(), Box::new(Node { ch: HashMap::new(), val: value }));
        true
    }
    fn get(&self, path: String) -> i32 {
        let parts: Vec<&str> = path.split('/').filter(|s| !s.is_empty()).collect();
        let mut v = &self.root;
        for p in parts {
            if !v.ch.contains_key(p) {
                return -1;
            }
            v = v.ch.get(p).unwrap();
        }
        v.val
    }
}

TypeScript

class Node {
    ch: Map<string, Node> = new Map();
    val = -1;
}
class FileSystem {
    private root = new Node();
    createPath(path: string, value: number): boolean {
        const parts = path.split('/').filter(Boolean);
        let v = this.root;
        for (let i = 0; i < parts.length - 1; i++) {
            if (!v.ch.has(parts[i])) return false;
            v = v.ch.get(parts[i])!;
        }
        const last = parts[parts.length - 1];
        if (v.ch.has(last)) return false;
        const n = new Node();
        n.val = value;
        v.ch.set(last, n);
        return true;
    }
    get(path: string): number {
        const parts = path.split('/').filter(Boolean);
        let v = this.root;
        for (const p of parts) {
            if (!v.ch.has(p)) return -1;
            v = v.ch.get(p)!;
        }
        return v.val;
    }
}

Complexity

• ⏰ Time complexity: O(L) per operation, where L is the number of segments in the path. Each segment is processed once for create/get.
• 🧺 Space complexity: O(N), where N is the total number of nodes (paths) created in the file system.