Design a File System — Trie-Based Path Storage

Problem Statement#

Design a file system supporting two operations: createPath(path, value) creates a new path (e.g., /a/b/c) with an associated integer value and returns false if the path already exists or its parent does not exist. get(path) returns the value at that path or -1 if not found.

Constraints:

• 2 <= path.length <= 100
• 1 <= value <= 10^9
• Each path component is a lowercase English letter string
• At most 10^4 calls to createPath and get

Input:  createPath("/leet", 1), createPath("/leet/code", 2), get("/leet/code")
Output: true, true, 2

Input:  createPath("/c/d", 1)
Output: false  (parent /c does not exist)

Why This Problem Matters#

Virtual file systems and distributed configuration stores like etcd, ZooKeeper, and Consul all use hierarchical path-based key-value storage. The design question of how to validate parent existence before creating a child path is core to maintaining a consistent namespace tree.

This problem appears in Google and Meta system design coding interviews because it bridges two concepts: string manipulation (parsing hierarchical paths) and data structure design (choosing between a HashMap and a Trie). Interviewers want to see that you can evaluate both approaches and justify your choice based on the operation profile.

The HashMap approach with parent path validation is O(L) per operation and is preferred when paths are not too long and prefix enumeration is rare. Understanding this trade-off signals senior-level design intuition.

The Core Insight#

The key insight is that you can flatten a hierarchical tree into a hashmap by using the full path string as the key. To validate that a parent exists for createPath("/a/b/c", v), find the last /, extract the prefix /a/b, and check if it exists in the map.

Initialise the map with {"/" : -1} so the root always exists as a valid parent. This handles top-level paths like /a whose parent is simply /.

The Trie approach is more space-efficient for large path trees with shared prefixes, but the HashMap approach is simpler to implement correctly under interview constraints.

Visual Dry Run#

Solution (Optimal)#

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)

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;
    }
}

Time: O(L) per operation where L is the length of the path string
Space: O(N * L) — N paths each of average length L stored in the map

Common Mistakes#

• Forgetting to initialise root / in the map, causing top-level path creation to fail
• Using path.rfind("/") without handling the case where the result is 0 (parent is root)—the slice path[:0] gives an empty string, not "/"
• Checking if path in self.paths for createPath is required: duplicate paths must return false
• Not returning false when parent is missing—only checking if path exists, not if parent exists
• In JavaScript, using path.lastIndexOf("/") returns 0 for top-level paths—substring(0, 0) is "", which must be mapped to "/"

Interview Tips#

• Explain both approaches (HashMap vs Trie) before coding and justify your choice
• The parent extraction trick with rfind("/") is the algorithmic core—walk through it clearly
• Mention that pre-initialising root as {"/" : -1} is an elegant base case that avoids special-casing top-level paths
• For follow-up, discuss how you would support delete (remove from map) and how that affects child paths (need recursive deletion or reference counting)

Follow-up Questions#

• How would you support listing all children of a path? (Store children set per node, or prefix scan the hashmap)
• How would you implement recursive delete? (Remove all keys with matching prefix from the hashmap)
• How would you handle concurrent createPath calls? (Lock at the parent level, or use optimistic concurrency control)
• How does this scale to a distributed file system with petabytes of data? (Namespace server like HDFS NameNode, storing only path metadata in memory)
• What if paths could be very deep (1000 levels)? (Use a Trie to save memory via shared prefixes)

Key Takeaways#

• A HashMap keyed by full path string achieves O(L) createPath and get operations
• Parent validation requires extracting the prefix up to the last / and checking it exists in the map
• Initialising {"/" : -1} in the constructor elegantly handles all top-level path creation
• The edge case where rfind("/") returns 0 must map the empty prefix string to "/"
• The Trie approach is more memory-efficient for large namespaces with shared path prefixes
• This design mirrors etcd's and ZooKeeper's hierarchical namespace implementations
• Always return false both when a path already exists and when its parent does not—two distinct failure modes