Coding Interview PatternsDesign File System
MediumTrie

Design File System

Explanation & Solution

Practice Problem

Description

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:

  • 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.
  • get(string path) — Returns the value associated with the path, or returns -1 if the path doesn't exist.
Input:operations = ["FileSystem","createPath","createPath","get","createPath","get"], operands = [[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",0],["/c"]]
0
FileSystem
1
createPath
2
createPath
3
get
4
createPath
5
get
Output:[null,true,true,2,false,-1]
0
null
1
true
2
true
3
2
4
false
5
-1

Explanation: createPath("/leet", 1) creates path /leet with value 1. createPath("/leet/code", 2) creates path /leet/code with value 2. get("/leet/code") returns 2. createPath("/c/d", 0) fails because parent /c doesn't exist. get("/c") returns -1 because /c doesn't exist.

Constraints

  • The number of calls to the two functions is less than or equal to 10^4 in total
  • 2 <= path.length <= 100
  • 1 <= value <= 10^9

Approach

Trie pattern

1. Model the File System as a Trie

  • Each directory component in a path becomes a node in the trie
  • The root node represents the / root directory
  • Each node stores a children map and a value

2. Implement createPath

  • Split the path by / and filter out empty strings
  • Traverse the trie for all parts except the last one
  • If any intermediate part doesn't exist, the parent path is missing — return false
  • If the last part already exists, the path already exists — return false
  • Otherwise, create a new node with the given value and return true

3. Implement get

  • Split the path by / and traverse the trie
  • If any part doesn't exist in the trie, return -1
  • Otherwise, return the value stored at the final node

4. Process Operations

  • Iterate through the operations array
  • For "FileSystem", push null (constructor call)
  • For "createPath" and "get", call the respective function and push the result

Key Insight

  • A trie naturally models hierarchical path structures where each level represents a directory component
  • Both createPath and get run in O(L) time where L is the number of path components
  • Using a Map for children gives O(1) lookups per component

Solution Code

Previous
Lexicographical Numbers
Next
Extra Characters in a String