Effective privileges in a role hierarchy with allow and disallow lists

You are building the access-control layer of a data platform. Every role has:

• allowed: privileges granted directly to the role
• disallowed: privileges explicitly taken away from the role
• parents: roles it inherits from

The inheritance graph is a directed acyclic graph. A role can have several parents, and many roles can share one parent.

Implement

def effective_privileges(roles: dict[str, Role]) -> dict[str, set[str]]

The function returns the final set of privileges for every role, using this rule:

1. Start with the union of the final sets of all of the role's parents.
2. Add the role's own allowed privileges.
3. Remove the role's own disallowed privileges. If a privilege is both allowed and disallowed on the same role, the disallow wins.

Children inherit their parent's final set, so a privilege a parent disallows does not reach a child through that parent. The child can still get it by allowing it itself or from another parent.

Raise an error if a role names a parent that does not exist or if the graph contains a cycle.

Constraints: up to 2·10^5 roles and 2·10^5 inheritance edges. Privilege names are non-empty strings.

Example

Result:

• base → {select}
• writer → {select, insert, update}
• analyst → {select, insert, share} (update removed)
• owner → {select, insert, share, update} (allowed again on the role itself)
• blend → {select, insert, share, update} (update still arrives through writer)

A role with allowed = {select} and disallowed = {select} ends with {}.

Follow-up to expect: what changes if a disallow on any ancestor must block the privilege for every descendant, even one that allows it again?

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