Design In Memory File System

This page explains Java solution to problem Design In Memory File System using Hash Map data structure.

Problem Statement

Design an in-memory file system to simulate the following functions:

ls: Given a path in string format. If it is a file path, return a list that only contains this file's name. If it is a directory path, return the list of file and directory names in this directory. Your output (file and directory names together) should in lexicographic order.

mkdir: Given a directory path that does not exist, you should make a new directory according to the path. If the middle directories in the path don't exist either, you should create them as well. This function has 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. If the file already exists, you need to append given content to original content. This function has void return type.

readContentFromFile: Given a file path, return its content in string format.

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"]

Solution

package com.vc.hard;

import java.util.*;

class DesignInMemoryFileSystem {
    static class Dir {
        HashMap<String, Dir> dirs;
        HashMap<String, String> files;

        Dir(HashMap<String, Dir> dirs, HashMap<String, String> files) {
            this.dirs = dirs;
            this.files = files;
        }
    }

    private Dir root;
    public DesignInMemoryFileSystem() {
        this.root = new Dir(new HashMap<>(), new HashMap<>());
    }

    public List<String> ls(String path) {
        List<String> res = new ArrayList<>();

        String[] split = path.split("/");
        Dir current = root;
        for(int i = 1; i < split.length; i++) {
            if(current.dirs.containsKey(split[i])) {
                current = current.dirs.get(split[i]);
            }
            else if(current.files.containsKey(split[i])) {
                res.add(split[i]);
                return res;
            }
            else return res;
        }

        for(Map.Entry<String, Dir> entry: current.dirs.entrySet()) {
            res.add(entry.getKey());
        }

        for(Map.Entry<String, String> entry: current.files.entrySet()) {
            res.add(entry.getKey());
        }

        res.sort(new Comparator<String>(){
            public int compare(String path1, String path2) {
                return path1.compareTo(path2);
            }
        });

        return res;
    }

    public void mkdir(String path) {
        String[] split = path.split("/");
        Dir current = root;
        for(int i = 1; i < split.length; i++) {
            if(!current.dirs.containsKey(split[i])) {
                current.dirs.put(split[i],
                        new Dir(new HashMap<String, Dir>(), new HashMap<String, String>()));
            }
            current = current.dirs.get(split[i]);
        }
    }

    public void addContentToFile(String filePath, String content) {
        String[] split = filePath.split("/");
        Dir current = root;
        for(int i = 1; i < split.length - 1; i++) {
            if(!current.dirs.containsKey(split[i])) {
                current.dirs.put(split[i],
                        new Dir(new HashMap<>(), new HashMap<>()));
            }
            current = current.dirs.get(split[i]);
        }
        String fileName = split[split.length - 1];
        current.files.put(fileName, current.files.getOrDefault(fileName, "") + content);
    }

    public String readContentFromFile(String filePath) {
        String[] split = filePath.split("/");
        Dir current = root;
        for(int i = 1; i < split.length - 1; i++) {
            if(!current.dirs.containsKey(split[i])) return "";
            current = current.dirs.get(split[i]);
        }
        String fileName = split[split.length - 1];
        return current.files.getOrDefault(fileName, "");
    }
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * DesignInMemoryFileSystem obj = new DesignInMemoryFileSystem();
 * List<String> param_1 = obj.ls(path);
 * obj.mkdir(path);
 * obj.addContentToFile(filePath,content);
 * String param_4 = obj.readContentFromFile(filePath);
 */

Time Complexity

ls : O(M + N + K log(K))
mkdir : O(M + N)
addContentToFile : O(M + N)
readContentFromFile : O(M + N) Where
M is length of input path
N is depth of directory structure
K is total number of directory and files in a ls output

Space Complexity

O(P + Q) Where
P is total number of input dirs
Q is total number of input files