Leetcode: Design File System

Design File System

Similar Problems:

• CheatSheet: Leetcode For Code Interview
• Tag: #oodesign

You are asked to design a file system which provides two functions:

• createPath(path, 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(path): Returns the value associated with a path or returns -1 if the path doesn’t exist.

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 two functions.

Please refer to the examples for clarifications.

Example 1:

Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

Example 2:

Input: 
["FileSystem","createPath","createPath","get","createPath","get"]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]
Output: 
[null,true,true,2,false,-1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/leet", 1); // return true
fileSystem.createPath("/leet/code", 2); // return true
fileSystem.get("/leet/code"); // return 2
fileSystem.createPath("/c/d", 1); // return false because the parent path "/c" doesn't exist.
fileSystem.get("/c"); // return -1 because this path 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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:

// https://code.dennyzhang.com/design-file-system
// Basic Ideas: hashmap
// Complexity: Time O(n), Space O(n)
import "strings"
type FileSystem struct {
    m map[string]int
}

func Constructor() FileSystem {
    m := map[string]int{}
    return FileSystem{m:m}
}

func (this *FileSystem) CreatePath(path string, value int) bool {
    // assume input is valid. e.g: //a, a/b, won't be given
    _, ok := this.m[path]
    if ok { return false }
    index := strings.LastIndex(path, "/")
    if index != 0 {
        parent := path[0:index]
        _, ok := this.m[parent]
        if !ok {
            return false
        } 
    }
    this.m[path] = value
    return true
}

func (this *FileSystem) Get(path string) int {
    res, ok := this.m[path]
    if ! ok {
       res = -1 
    }
    return res
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.CreatePath(path,value);
 * param_2 := obj.Get(path);
 */