Folder path from a node id

A file browser stores its folder hierarchy as three parallel arrays:

• idList[i] is a unique folder id.
• children[i] lists the ids of the folders directly inside folder idList[i].
• nameList[i] is the display name of folder idList[i].

Every folder has at most one parent, so the folders form a forest. A folder that is not inside any other folder is top-level.

Implement folder_path(idList, children, nameList, targetId). It returns the full path of targetId as a string that starts at its top-level folder, with names separated by / and a leading /. Return None (or an empty value in your language) if targetId is not a folder.

Constraints:

• Up to 10^5 folders; a single chain can be that deep.
• Names are not unique; ids are.
• Be ready to answer many queries against the same hierarchy.

Example 1

idList   = [10, 20, 30, 40, 50, 60]
children = [[20, 30], [40], [], [], [60], []]
nameList = ["home", "projects", "music", "compass", "tmp", "cache"]
targetId = 40

Output: "/home/projects/compass". Folder 40 is inside 20, which is inside the top-level folder 10.

Example 2

Same hierarchy, targetId = 60. Output: "/tmp/cache". Folder 50 is a second top-level folder.

Reconstructed from the reported question; details may differ from what interviewers ask.