Design File System Solution in Python

Quick Links

Problem Statement

Ah, the classic “Design File System” problem on LeetCode! It’s like trying to organize your closet but with a lot more code and a lot less dust. Imagine you have a magical closet where you can create paths and store values, but if you try to create a path that doesn’t exist, it’s like trying to find a pair of socks in a black hole—good luck with that!

In this problem, you are tasked with designing a file system that allows you to create paths and retrieve values associated with those paths. You can think of it as a digital version of your messy room where you can only find things if you remember where you put them. If you try to create a path that doesn’t have a parent, it’s like trying to hang a picture frame without a wall—just not going to happen!

Code Solution


class TrieNode:
    def __init__(self, value: int = 0):
        self.children: dict[str, TrieNode] = {}
        self.value = value

class FileSystem:
    def __init__(self):
        self.root = TrieNode()

    def createPath(self, path: str, value: int) -> bool:
        node: TrieNode = self.root
        subpaths = path.split('/')

        for i in range(1, len(subpaths) - 1):
            if subpaths[i] not in node.children:
                return False
            node = node.children[subpaths[i]]

        if subpaths[-1] in node.children:
            return False
        node.children[subpaths[-1]] = TrieNode(value)
        return True

    def get(self, path: str) -> int:
        node: TrieNode = self.root

        for subpath in path.split('/')[1:]:
            if subpath not in node.children:
                return -1
            node = node.children[subpath]

        return node.value

Approach

The approach taken in this solution is to use a Trie (prefix tree) to represent the file system. Each node in the Trie corresponds to a directory or file, and the value stored in the node represents the value associated with that path.

Creating a Path: When creating a path, the code checks if all the parent directories exist. If they do, it creates the new path; if not, it returns False.
Retrieving a Value: To get the value of a path, the code traverses the Trie according to the subpaths. If it finds the path, it returns the value; otherwise, it returns -1.

Time and Space Complexity

Operation	Time Complexity	Space Complexity
createPath	O(N)	O(N)
get	O(N)	O(N)

Real-World Example

Imagine you’re organizing your digital photo album. You have folders for vacations, family gatherings, and random cat pictures. If you try to create a folder for “2023 Vacations” without first having a “Vacations” folder, you’ll end up with a digital mess. This problem mimics that scenario, ensuring that you can only create folders (or paths) that have a valid parent.