Find All Paths for a Name in a File System
The Walt Disney Company● MediumFULLTIMEPHONE SCREENProblem statement
An in-memory file system has n entries, numbered from 0 to n - 1. Each entry is a file or a folder, and together they form a tree under one root folder. The root folder itself is not one of the entries.
You are given:
names[i]: the name of entryi.parent[i]: the number of the folder that directly contains entryi, or-1when entryiis directly inside the root folder.target: the name to search for.
Names can repeat. Entries in different folders can have the same name, and a file and a folder can share a name. Inside one folder, no two entries have the same name. Entries are listed in no particular order, so a folder can come after the entries inside it.
The full path of an entry is / followed by the names on the way from the root down to that entry, joined by /. For example, an entry named notes.txt inside a folder named docs that is directly inside the root has the full path /docs/notes.txt.
Return the full paths of all entries whose name is exactly target, files and folders alike. Sort the paths in lexicographic order by character code, so . comes before /, and both come before digits and letters. A path that is a prefix of another path comes first. If no entry is named target, return an empty array.
Function
findPathsByName(names: String[], parent: int[], target: String) → String[]Examples
Example 1
names = ["docs","photos","notes.txt","docs","notes.txt","2024","notes.txt"]parent = [-1,-1,0,1,3,1,5]target = "notes.txt"return = ["/docs/notes.txt","/photos/2024/notes.txt","/photos/docs/notes.txt"]Entries 0 (docs) and 1 (photos) are directly inside the root. Entry 3 is a second folder named docs, inside photos, and entry 5 (2024) is also inside photos.
Three entries are named notes.txt:
- Entry
2is inside entry0:/docs/notes.txt. - Entry
4is inside entry3, which is inside entry1:/photos/docs/notes.txt. - Entry
6is inside entry5, which is inside entry1:/photos/2024/notes.txt.
In sorted order, /docs/notes.txt comes first because d comes before p. /photos/2024/notes.txt comes before /photos/docs/notes.txt because 2 comes before d.
Example 2
names = ["x","a","x","a.b"]parent = [3,-1,1,-1]target = "x"return = ["/a.b/x","/a/x"]Entry 0 is listed before its folder, entry 3 (a.b). So the two entries named x have the full paths /a.b/x and /a/x.
The two paths first differ at their third character: . in /a.b/x and / in /a/x. The dot has the smaller character code, so /a.b/x comes first.
Example 3
names = ["music","music","song.mp3"]parent = [-1,0,1]target = "music"return = ["/music","/music/music"]Entry 0 is a folder named music directly inside the root, and entry 1 is another folder named music inside it. Both match, even though they are folders.
/music is a prefix of /music/music, so it comes first. The file song.mp3 does not match.
Constraints
1 <= n <= 10^4, wheren == names.length == parent.length-1 <= parent[i] <= n - 1- Following
parentfrom any entry always ends at-1, so the entries form a tree with no cycles. - Every full path has at most
100names. - No two entries with the same
parentvalue have the same name. 1 <= names[i].length <= 201 <= target.length <= 20names[i]andtargetuse only lowercase English letters, digits, and dots, and each has at least one letter or digit.