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. ```python 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. ```hint Each node waits for its parents Think about the order in which nodes must be processed so that everything a node inherits is already final when you reach it. ``` ```hint Keep the conflict rule in one place Decide what a parent passes down to its children so that changing the allow-versus-deny rule changes one function rather than the traversal. ``` ### 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? ### What a Strong Answer Covers - Settles the conflict rules (deny overrides versus nearest rule wins, disagreeing parents, conflicts on one node, the default) before coding - Processes nodes in topological order so that each node is computed once from its parents' final results - A merge step that implements the chosen rule exactly and is kept separate from the traversal - Detects a cycle instead of looping or silently skipping nodes - Complexity in nodes, edges and permissions, and a compact set representation such as bitsets ### Follow-up Questions - One node's allow list changes. How do you update the results without recomputing the whole graph? - Only a few nodes out of millions are ever queried. Would you still compute every node? - A user asks why they lack a permission. How do you report which rule on which node decided it? - The graph has millions of nodes and thousands of permissions. How do you keep memory manageable?