Nested Configuration Paths

A configuration service stores values at slash-separated paths such as /app/db/port. Design a class PathStore:

• PathStore() starts with only the root /, which holds no value.
• create(path, value) creates path with the integer value and returns True. It returns False and changes nothing if path already exists, or if its parent path (everything before the last segment) does not exist. Paths directly below the root always have an existing parent.
• get(path) returns the value stored at path, or -1 if the path does not exist.
• children(path) returns the sorted list of the segment names directly below path ("/" means the root). A missing path gives [].

Examples

ops:  ["PathStore", "create", "create", "create", "create", "create", "get", "get", "children", "children"]
args: [[], ["/app", 1], ["/app/db/port", 5], ["/app/db", 2], ["/app/db/port", 5], ["/app", 9], ["/app/db/port"], ["/app/web"], ["/app"], ["/"]]
Output: [None, True, False, True, True, False, 5, -1, ["db"], ["app"]]
Explanation: "/app/db/port" fails the first time because "/app/db" does not exist yet;
"/app" cannot be created twice.

Constraints

• Paths start with / and consist of non-empty segments of lowercase letters and digits; create is never called with "/"; path length <= 2000
• Up to 10**4 calls in total
• Target: create and get in O(number of segments); children in O(c log c) for c children

Goals

• Build a trie whose edges are path segments rather than characters
• Reject creations whose parent path does not exist yet