Design a File System — Trie-Based Path Storage

Problem

Design a file system with two operations:

createPath(path, value) — create a new path (like /a/b/c) with a value. Returns false if path already exists or parent doesn't exist.
get(path) — return the value associated with path, or -1 if not found.

Key Insight — HashMap or Trie

HashMap approach: Map full path strings to values. For createPath, check parent path exists.

Trie approach: Each node represents a directory component.

The HashMap approach is simpler and O(L) per operation where L = path length.

Solutions

Python

class FileSystem:
    def __init__(self):
        self.paths = {"/": -1}

    def createPath(self, path: str, value: int) -> bool:
        if path in self.paths:
            return False
        parent = path[:path.rfind("/")]
        if not parent:
            parent = "/"
        if parent not in self.paths:
            return False
        self.paths[path] = value
        return True

    def get(self, path: str) -> int:
        return self.paths.get(path, -1)

JavaScript

class FileSystem {
    constructor() { this.paths = new Map([["/", -1]]); }
    createPath(path, value) {
        if (this.paths.has(path)) return false;
        const parent = path.substring(0, path.lastIndexOf("/")) || "/";
        if (!this.paths.has(parent)) return false;
        this.paths.set(path, value);
        return true;
    }
    get(path) { return this.paths.has(path) ? this.paths.get(path) : -1; }
}

Java

import java.util.*;
class FileSystem {
    Map<String, Integer> paths = new HashMap<>();
    public FileSystem() { paths.put("/", -1); }
    public boolean createPath(String path, int value) {
        if (paths.containsKey(path)) return false;
        String parent = path.substring(0, path.lastIndexOf('/'));
        if (parent.isEmpty()) parent = "/";
        if (!paths.containsKey(parent)) return false;
        paths.put(path, value); return true;
    }
    public int get(String path) { return paths.getOrDefault(path, -1); }
}

C++

#include <unordered_map>
#include <string>
using namespace std;
class FileSystem {
    unordered_map<string,int> paths;
public:
    FileSystem() { paths["/"] = -1; }
    bool createPath(string path, int value) {
        if (paths.count(path)) return false;
        int pos = path.rfind('/');
        string parent = pos == 0 ? "/" : path.substr(0, pos);
        if (!paths.count(parent)) return false;
        paths[path] = value; return true;
    }
    int get(string path) {
        return paths.count(path) ? paths[path] : -1;
    }
};

C

#include <string.h>
#include <stdlib.h>
/* C: hash table with string keys mapping paths to integer values */
/* Parent check: find last '/' and look up prefix */

Complexity

Operation	Time	Space
createPath	O(L)	O(N·L)
get	O(L)	—