ACL Inheritance with Local-Only Deny Rules
Learn this problem
SnowflakeFULLTIMEPHONE SCREENProblem statement
There are n = allows.length access-control nodes numbered from 0 through n - 1. A permission is one lowercase English letter.
allows[v]lists the permissions directly allowed at nodev.denies[v]lists the permissions directly denied at nodev.- Each directed edge
[parent, child]means that the child inherits allow declarations from that parent and all of its ancestors. The graph is acyclic.
A query asks whether node queryNodes[i] may use permission permissions[i]. Return one boolean per query in order.
The answer is true exactly when the queried node or at least one of its ancestors directly allows the permission, and the queried node itself does not directly deny it.
- Deny rules apply only at the node that declares them. They never propagate to descendants.
- A local deny overrides both local and inherited allows for that node.
- A local deny does not remove the underlying allow declaration from inheritance. An allow can pass through a node that locally denies it and still reach a descendant.
- If no local or inherited allow exists, access is false.
Edges, declarations and queries are valid. Queries do not change the graph or rules. Empty allow and deny strings are permitted, and their letter order is irrelevant.
Function
canAccess(allows: String[], denies: String[], edges: int[][], queryNodes: int[], permissions: String) → boolean[]Examples
Example 1
allows = ["a","",""]denies = ["","a",""]edges = [[0,1],[1,2]]queryNodes = [0,1,2]permissions = "aaa"return = [true,false,true]Permission a is allowed at node 0. Node 1 denies it locally, but that deny does not reach node 2 or stop the inherited allow. The three answers are true, false and true.
Example 2
allows = ["a","b","","c"]denies = ["","","b","a"]edges = [[0,2],[1,2],[2,3]]queryNodes = [2,2,3,3,3]permissions = "ababc"return = [true,false,false,true,true]Node 2 inherits a and b, then denies only its own access to b. Node 3 inherits both underlying allows, adds c and locally denies a.
Constraints
1 <= allows.length = denies.length <= 100.- Each allow or deny string contains unique lowercase English letters and has length from
0through26. A letter may appear in both lists for the same node. 0 <= edges.length <= 500; every edge has distinct valid endpoints, no directed edge is repeated, and the graph is a DAG.0 <= queryNodes.length = permissions.length <= 200.- Each queried node is valid, and each queried permission is a lowercase English letter.