Design a File System (Trie variant)
Design a file system class with `createPath` and `get` methods that efficiently handle path creation and lookup. This involves using a variant of a Trie or Hash Map.
Why Interviewers Ask This
Salesforce evaluates this question to assess a candidate's ability to model hierarchical data structures efficiently. They specifically look for proficiency in Trie implementation, path validation logic, and the trade-offs between space complexity and lookup speed when designing systems that manage nested resources like files or configuration trees.
How to Answer This Question
1. Clarify requirements: Confirm if paths are case-sensitive, handle duplicates, or support wildcards. 2. Propose a Trie structure: Explain why a Trie is superior to a flat Hash Map for prefix operations and memory efficiency in deep hierarchies. 3. Define node design: Describe each node storing a boolean flag for 'isPath' and a map of children nodes. 4. Implement createPath: Walk the tree splitting the string by slashes; create missing nodes only if they don't exist, ensuring no parent path was already marked as a file. 5. Implement get: Traverse the tree matching the path segments exactly and return true only if the final node has the 'isPath' flag set. 6. Analyze complexity: State time complexity as O(L) where L is path length and space as O(N*L).
Key Points to Cover
- Explicitly validating that parent paths do not exist when creating leaf paths
- Choosing a Trie over a Hash Map for hierarchical prefix optimization
- Handling edge cases like empty strings or invalid separators gracefully
- Demonstrating clear time and space complexity analysis relative to path length
- Maintaining clean separation between traversal logic and state mutation
Sample Answer
To solve this, I would design a Trie-based File System class. First, let's clarify that we need to prevent creating a child path if a parent path already exists as a complete file, such as preventing '/a/b' if '/a' is al…
Common Mistakes to Avoid
- Failing to check if an intermediate node is already marked as a complete path before adding children
- Using a single flat Hash Map which loses the hierarchical relationship and increases search costs
- Not handling null pointers or missing segments during tree traversal leading to runtime crashes
- Ignoring case-sensitivity requirements or special character escaping in path strings
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.