Design File System

Design File System

1. What is this problem about?

The Design File System interview question asks you to implement a simplified path-based storage system. You need to support createPath(path, value) and get(path). A path is valid only if its parent path already exists. For example, you can't create "/a/b" unless "/a" has already been created. This Design File System coding problem is a variation of prefix-based data storage.

2. Why is this asked in interviews?

Companies like Uber and Airbnb ask this to test your understanding of Trie interview patterns and hierarchical data. It evaluates how you handle string parsing and whether you can enforce structural constraints (parent existence) during insertion. It’s a test of clean API design and logical validation.

3. Algorithmic pattern used

• Method 1 (Hash Map): Use a Map<String, Integer> to store the full path string. Before creating "/a/b", check if "/a" exists in the map. This is simple and effective.
• Method 2 (Trie): Each node in the Trie represents a directory component (e.g., "a" or "b"). createPath traverses the Trie and returns an error if a component's parent node isn't found.

4. Example explanation

1. createPath("/leet", 1): Root has no parent requirement. Map: {"/leet": 1}. Success.
2. createPath("/leet/code", 2): Parent "/leet" exists. Map: {"/leet": 1, "/leet/code": 2}. Success.
3. createPath("/c/d", 3): Parent "/c" does not exist. Return false.
4. get("/leet/code"): Returns 2.

5. Common mistakes candidates make

• Incorrect Splitting: Splitting path strings by "/" and failing to handle the resulting empty strings or the root path.
• Missing Parent Check: Failing to verify that every directory in the path except the last one already exists.
• Redundant Search: Re-parsing the entire path string for every single get operation when a simple map lookup is $O(1)$ after path parsing.

6. Interview preparation tip

While a Hash Map is easier to code, be prepared to discuss the Trie approach. Tries are more space-efficient if many paths share long prefixes and are the standard way real file systems or routers manage hierarchical data.