Effective Permissions in an Inheritance DAG with Allow and Deny Lists

Permissions are inherited along the edges of a directed acyclic graph. Each node, such as a group, a folder or a resource, has its own allow list and its own deny list of permissions, and it inherits from every node that has an edge into it. Compute the final set of permissions for every node, processing the graph in topological order.

nodes = {
 "org": {"allow": ["read", "write"], "deny": []},
 "eng": {"allow": ["deploy"], "deny": ["write"]},
 "finance": {"allow": [], "deny": ["deploy"]},
 "payroll": {"allow": ["write"], "deny": []},
}
edges = [("org", "eng"), ("org", "finance"), ("eng", "payroll"), ("finance", "payroll")]

effective_permissions(nodes, edges) # -> {node: set of permissions}

In this example, payroll allows write itself while its parent eng denies it, and it inherits deploy as allowed from eng but as denied from finance. Which of these permissions payroll ends up with depends on how allow and deny conflicts are resolved, which the reported question leaves for you to settle with the interviewer.

Constraints and Clarifications

• Given: a directed acyclic graph, an allow list and a deny list on every node, inheritance along the edges, and a final permission set wanted for every node.
• Assume an edge (a, b) means that b inherits from a.
• Not given: how a deny interacts with an allow (on the same node, between a node and its ancestors, or between two parents), what happens to a permission no rule mentions, and how large the graph is. Ask, or state your assumptions.

Clarifying Questions

• Does a deny anywhere above a node always win, or does the nearest explicit rule win, so that a node's own allow overrides an inherited deny?
• When two parents disagree, one allowing and one denying the same permission, which wins?
• What if a node lists the same permission in both its allow list and its deny list?
• Is a permission that no rule mentions granted or denied by default?
• Can the input contain a cycle by mistake, and what should happen then?
• Are results needed for every node at once, or for single nodes on demand, and how often do the lists and edges change?