Problem statement

https://leetcode.com/problems/design-in-memory-file-system/

Solution

Quite painful problem from technical point of view, because you need to code about 30-40 lines. The idea is to have Tree like structure, where we have two fields: dirs and files, where dirs is dictionary which have again different Nodes. In fact what we nave is almost classical Trie, where files is end nodes and dirs are another nodes.

  1. Funciton getExistedNode(self, path) returns Node, and its type, given path.
  2. Function ls(self, path): first we need to find this path in our tree structure, then check if it is directory or file and return either list of all directories and files or just name of file.
  3. Function mkdir(self, path): we start from root of our Tree structure and then create new subfolder if needed and go one level deeper.
  4. Function addContentToFile(self, filePath, content): first we need to parse our filePath and create directory, using mkdir. Then we go to desired node and either create empty file or add content to existing file.
  5. Function readContentFromFile(self, filePath): very similar to previous function, but we need just to return content of file.

Complexity

Time complexity: it is O(n) for mkdir, getExistedNode, where n is length of path. For ls it is O(n + k log k s), where k is number of files and dirs in answer and s is average length of its names. For addContentToFile and readContentFromFile it is O(n + m), where m is size of content/file. Also we have O(n + T) space complexity, where T is size of all our File System.

Code

#### borrowed code
class FileSystem(object):
    def __init__(self):
        self.root = {'dirs' : {}, 'files': {}}

    def ls(self, path):
        node, tpe = self.getExistedNode(path)
        if tpe == 'dir': return sorted(list(node['dirs'].keys()) + list(node['files'].keys()))
        return [path.split('/')[-1]]

    def mkdir(self, path):
        node = self.root
        for dr in filter(len, path.split('/')):
            if dr not in node['dirs']: node['dirs'][dr] = {'dirs' : {}, 'files': {}}
            node = node['dirs'][dr]

    def addContentToFile(self, filePath, content):
        dirs = filePath.split('/')
        path, file = '/'.join(dirs[:-1]), dirs[-1]
        self.mkdir(path)
        node, tpe = self.getExistedNode(path)
        if file not in node['files']: node['files'][file] = ''
        node['files'][file] += content

    def readContentFromFile(self, filePath):
        dirs = filePath.split('/')
        path, file = '/'.join(dirs[:-1]), dirs[-1]
        node, tpe = self.getExistedNode(path)
        return node['files'][file]
        
    def getExistedNode(self, path):
        node = self.root
        for dr in filter(len, path.split('/')):
            if dr in node['dirs']: node = node['dirs'][dr]
            else: return node, 'file'
        return node, 'dir'