Remove Redundant Directory Grants
Learn this problem
DropboxFULLTIMEPHONE SCREENProblem statement
A user has explicit access grants to some directories in a directory forest. A grant to a directory also grants access to every descendant of that directory.
The parallel arrays directories and parents describe the forest. For each index i, parents[i] is the direct parent of directories[i], or the empty string when that directory is a root.
Given the distinct explicitly granted directories in grants, remove every grant whose directory has a granted ancestor. Return the remaining grants in their original order in grants.
A grant is never redundant merely because it has a granted descendant. Only an explicit grant on a strict ancestor makes it redundant.
Function
removeRedundantGrants(directories: String[], parents: String[], grants: String[]) → String[]Examples
Example 1
directories = ["A","B","C"]parents = ["","A","A"]grants = ["A","B","C"]return = ["A"]The grant on A already grants access to both children, so the explicit grants on B and C are redundant.
Example 2
directories = ["A","B","C","D","E","F","G","H","I"]parents = ["","A","A","C","C","E","F","B","B"]grants = ["E","I","G"]return = ["E","I"]G is a descendant of the granted directory E, so its grant is removed. Neither E nor I has a granted ancestor.
Constraints
1 <= directories.length <= 2 * 10^5parents.length == directories.length- Every directory name is a unique non-empty string.
- Each
parents[i]is either the empty string or names a different directory indirectories. - The parent relationships form a forest with no cycles.
0 <= grants.length <= directories.length- Every value in
grantsnames a directory and appears at most once. - The total number of characters across all input strings is at most
2 * 10^6.