Leetcode: Design In-Memory File System

This question is asked at Amazon and Airbnb. It is to design an in-memory file system intended to simulate certain functions. We have to design an in-memory file system to simulate certain functions and impement the ls, mkdir, addContentToFile, and readContentFromFile functions.

Mkdir: Given a directory path that does not exist, make a new directory according to the path. If the middle directories in the path don't exist eather you should create them as well, and this function has a void return type. 

addContentToFile: Given a file path and file content in string format, if the file doesn't exist you need to create that file containing given content, or append content to original content. This function also has a void return type. 

ls: Given a path in string formet. If there is a file path, return the list of file and directory names in this directory. It should arrange things in lexicographic order. 

Input: 

["FileSystem","ls","mkdir","addContentToFile","ls","readContentFromFile"]

[[],["/"],["/a/b/c"],["/a/b/c/d","hello"],["/"],["/a/b/c/d"]]

Output:

[null,[],null,null,["a"],"hello"]

Explanation:

The filesystem is instantiated with the following: 

/*

Your FileSystem object will be instantiated and called as such:

FileSystem obj = new FileSystem();

List<String> param_l = obj.ls(path);

obj.mkdir(path);

obj.addContentToFile(filePath, content);

String param_4 = obj.readContentFromFile(filePath);

*/

Here, I will describe one approach to solving the problem, which is using a separate Directory and File List. The root acts as the base of the directory structure. Each directory has 2 hashmaps referring to files. There are ways to implement this, but I want to draw the diagram first. 

Here is how to implement the ls: We start by initializing a temporary directory pointer to the root directory and split the input directory path based on (/) and obtain the individual levels of directory name in the d array. Then we traverse over the tree directory structure and we keep updating the t directory pointer to a new level as we go to the children. We stop at either the end level directory or the file name depending on the input given, and return the last entry in the directory. We can also obtain a list of files using a HashMap. 

How to implement mkdir: We start entering a directory structure, and create the empty directory and initialize the directory as an empty list. We create an entry in the last valid directory and initialize its subdirectory as an empty list. Keep doing this until we reach the end level directory. 

How to implement addContentToFile: We start going through the structure of the file and check the hashmap to see if the file exists, and either add or append the hashmap but using the put() and get() methods, respectively. 

How to implement readContentFromFile: Reach the last directory level by traversing, then searching for the file name entry corresponding to the key, and return the contents of the file. 

Time complexity for mkdir is O(m + n) and ls is O(m + n + klog(k)), where the k log k is done by sorting. There is an O(m + n) time complexity by adding the content to the files and reading the content from the files. So overall, this algorithm is relatively efficient.

Here's the code: 

public class FileSystem {

    class Dir {

        //initialize hashmap of directories and files.

        HashMap<String, Dir> dirs = new HashMap<>();

        HashMap<String, String> files = new HashMap<>();

    }

    Dir root;

    public FileSystem() {

        //initialize new directory

        root = new Dir();

    }

    public List<String> ls(String path) {

        Dir t = root;

        List<String> files = new ArrayList<String>();

        //We want to make sure that we don't reach the end of the path

        if(!path.equals("/")){

            String[] d = path.split("/");

            //traverse through the directories. 

            for(int i = 1; i < d.length - 1; i++) {

                t = t.dirs.get(d[i]);

            }

            //If we have the final directory we either add or go the the final directory.

            if(t.files.containsKey(d[d.length - 1])){

                files.add(d[d.length - 1]);

                return files;

            } else {

                t = t.dirs.get(d[d.length - 1]);

            }

        }

        //add all the directories and files and arrange them.

        files.addAll(new ArrayList<>(t.dirs.keySet()));

        files.addAll(new ArrayList<>(t.files.keySet()));

        Collections.sort(files);

        return files;

    }

    public void mkdir(String path) {

        Dir t = root;

        String[] d = path.split("/");

        //make a new directory and put new directories in the parent files if they don't exist. 

        for(int i = 1; i < d.length; i++) {

            if(!t.dirs.containsKey(d[i]))

                t.dirs.put(d[i], new Dir());

            t = t.dirs.get(d[i]);

        }

        public void addContentToFile(String filePath, String content) {

            Dir t = root;

            String[] d = filePath.split("/");

            //get to the intended directory

            for(int i = 1; i < d.length - 1; i++){

                t = t.dirs.get(d[i]);

            }

            //either add the text in a new file or old file. 

            t.files.put(d[d.length - 1], t.files.getOrDefault(d[d.length - 1], "") + content);

        }

        public String readContentFromFile(String filePath) {

            Dir t = root;

            String[] d = filePath.split("/");

            //get to the intended directory

            for(int i = 1; i < d.length - 1; i++) {

                t = t.dirs.get(d[i]);

            }

            //get the text from this directory, else return null if it doesn't exist. 

            return t.files.get(d[d.length - 1]);

        }

    }

}