929. Folder Paths Store

Medium3.5 points estimatedDesignHash TableTrieString4 hints
RPby Rohit Parihar

You are writing the metadata index for a tiny file system. Build FolderPaths with an empty constructor.

createPath(path, value) stores a number for a new folder path such as /orchard/pear and returns true. It must return false and change nothing when the path already exists, or when its parent folder (the path without its last segment) has not been created yet. A single-segment path like /orchard always has a valid parent, the root, which is not itself a stored path.

get(path) returns the stored value, or -1 if the path does not exist. Paths are a slash followed by lowercase segments separated by slashes, with no trailing slash. A value can never be changed once stored.

Example 1

Input:
operations = ["FolderPaths","createPath","createPath","createPath","createPath","createPath","get","get"]arguments = [[],["/orchard/pear",12],["/orchard",3],["/orchard/pear",12],["/orchard/pear",13],["/orchard/pear/seed",7],["/orchard/pear"],["/orchard/plum"]]
Output:
[null,false,true,true,false,true,12,-1]
Explanation:

The first call fails because /orchard does not exist yet. After /orchard is created, /orchard/pear succeeds once and a repeat is refused even with another value, while /orchard/pear/seed is allowed. /orchard/plum was never created, so get returns -1.

Example 2

Input:
operations = ["FolderPaths","createPath","get","createPath","get"]arguments = [[],["/x/y/z",1],["/x"],["/x",0],["/x"]]
Output:
[null,false,-1,true,0]
Explanation:

/x/y/z needs /x/y, which is missing, so it is refused and /x still reads -1 until it is created.

Constraints

1 ≤ path.length ≤ 100

Segments contain only lowercase letters; paths are well formed

0 ≤ value ≤ 109

At most 2000 calls in total

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(L) per call
Space
O(total path length)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.