Effective privileges in a role hierarchy with allow and disallow lists

Clarify first. Each role has a set of privileges it allows, a set it disallows, and a list of parent roles it inherits from. The graph is a DAG. Pin down these rules before coding:

• Direction. An edge parent -> child means the child inherits from the parent. A role can have many parents, and a privilege can reach it along several paths.
• What a role passes on. A role passes its final set to its children, after its own disallows have been applied. So a disallow hides a privilege from that role and from everything that inherits only through it.
• Order inside one role. final(r) = (union of final(p) for each parent p) ∪ allowed(r) − disallowed(r). If a role both allows and disallows the same privilege, the disallow wins. Say this out loud; it is the edge case interviewers check most.
• A child can allow again. If a parent disallowed write, a child that lists write in its own allowed set has it.
• Many paths. If one parent drops x but another parent still has it, the child gets x. A union over parents gives this behavior automatically.
• Bad input. Unknown parent names and cycles are errors, not silent drops.

Ask which deny rule the interviewer wants. Another common version says that a deny anywhere above a role blocks the privilege for good. That version is in Follow-ups and needs a second set to propagate.

Brute force. For each role, run a DFS up through its ancestors and work out every ancestor's final set again. Shared ancestors are computed again on each path, so this can take exponential time on a diamond-heavy DAG. Even with a seen set for each role it costs O(R · (R + E) · P).

Optimal: topological order with memoization. A role's final set depends only on its parents' final sets. Process roles in topological order (Kahn's algorithm) so that every parent is finished before its children:

1. Build children lists and an in-degree count for each role.
2. Start a queue with every role that has no parents.
3. Pop a role, take the union of its parents' final sets, add allowed, subtract disallowed, and store the result. Lower the in-degree of each child and push any child that reaches 0.
4. If fewer than R roles were popped, there is a cycle.

Invariant. When a role is popped, all of its parents are already final. So each role's set is computed exactly once and never changes. A recursive DFS with a memo gives the same result. Kahn's algorithm avoids Python's recursion limit on deep hierarchies (up to 2·10^5 roles) and finds cycles for free.

from __future__ import annotations

from collections import deque
from dataclasses import dataclass, field


@dataclass
class Role:
    allowed: set[str] = field(default_factory=set)
    disallowed: set[str] = field(default_factory=set)
    parents: list[str] = field(default_factory=list)


class CycleError(ValueError):
    pass


def effective_privileges(roles: dict[str, Role]) -> dict[str, set[str]]:
    """Final privilege set for every role.

    final(r) = (union of final(parent)) | allowed(r) - disallowed(r);
    children inherit the parent's final set.
    """
    indegree: dict[str, int] = {name: 0 for name in roles}
    children: dict[str, list[str]] = {name: [] for name in roles}
    for name, role in roles.items():
        for parent in set(role.parents):          # ignore duplicate edges
            if parent not in roles:
                raise KeyError(f"{name} inherits from unknown role {parent}")
            children[parent].append(name)
            indegree[name] += 1

    queue = deque(name for name, d in indegree.items() if d == 0)
    final: dict[str, set[str]] = {}
    while queue:
        name = queue.popleft()
        role = roles[name]
        privs: set[str] = set()
        for parent in role.parents:
            privs |= final[parent]
        privs |= role.allowed
        privs -= role.disallowed                    # disallow wins inside a role
        final[name] = privs
        for child in children[name]:
            indegree[child] -= 1
            if indegree[child] == 0:
                queue.append(child)

    if len(final) != len(roles):
        stuck = sorted(set(roles) - set(final))
        raise CycleError(f"cycle among roles: {stuck}")
    return final


def has_privilege(roles: dict[str, Role], role: str, privilege: str) -> bool:
    """Single query: walk only the role's ancestors, memoized."""
    memo: dict[str, set[str]] = {}

    def solve(name: str) -> set[str]:
        if name not in memo:
            r = roles[name]
            privs: set[str] = set()
            for p in r.parents:
                privs |= solve(p)
            memo[name] = (privs | r.allowed) - r.disallowed
        return memo[name]

    return privilege in solve(role)


if __name__ == "__main__":
    roles = {
        "viewer":  Role(allowed={"read"}),
        "editor":  Role(allowed={"write", "comment"}, parents=["viewer"]),
        "auditor": Role(allowed={"export"}, disallowed={"comment"},
                        parents=["editor"]),
        "guest":   Role(allowed={"read"}, disallowed={"read"}),
        "lead":    Role(allowed={"comment"}, parents=["auditor"]),
        "mixed":   Role(parents=["auditor", "editor"]),
    }
    out = effective_privileges(roles)
    assert out["viewer"] == {"read"}
    assert out["editor"] == {"read", "write", "comment"}
    assert out["auditor"] == {"read", "write", "export"}
    assert out["guest"] == set()                       # disallow beats allow
    assert out["lead"] == {"read", "write", "export", "comment"}  # re-allowed
    assert out["mixed"] == {"read", "write", "export", "comment"}  # other path
    assert has_privilege(roles, "mixed", "comment")
    assert not has_privilege(roles, "auditor", "comment")
    assert effective_privileges({}) == {}
    try:
        effective_privileges({"a": Role(parents=["b"]), "b": Role(parents=["a"])})
        raise AssertionError("expected cycle")
    except CycleError:
        pass
    print("ok")

Let R be the number of roles, E the number of inheritance edges, and P the number of distinct privileges.

• effective_privileges: building the graph is O(R + E). Each edge merges one parent set into one child set, which costs O(P), so the total time is O(R + E · P + total allowed + total disallowed). Space is O(R · P) for the stored final sets, plus O(R + E) for the graph.
• has_privilege (single query): O((A + E_A) · P), where A is the number of ancestors of the role and E_A is the number of edges among them. It visits only the part of the graph above the role.
• With bitsets (privileges mapped to bit positions in an int), each union or difference costs O(P / 64), which makes wide DAGs much faster.

• Single role, no parents, allowed={read} gives {read}.
• Chain viewer -> editor: editor gets {read, write, comment}, its own privileges plus read from viewer.
• auditor inherits from editor and disallows comment: {read, write, export}.
• Same privilege in both lists on one role (guest: allow read, disallow read) gives {}.
• Child re-allows a privilege its parent disallowed (lead lists comment): lead has comment.
• Diamond: mixed inherits from auditor (no comment) and editor (has comment): mixed has comment, because one path is enough.
• A role disallows something it never had: no error, and the set is unchanged.
• Duplicate parent listed twice: the result is the same as listing it once.
• Empty input {} gives {}.
• Two roles that inherit from each other raise CycleError.
• A parent name that does not exist raises KeyError.
• A deep chain of 2·10^5 roles runs without recursion errors, because the code uses Kahn's algorithm and not recursion.

1. Deny is sticky (blocks everything below). A disallow anywhere among a role's ancestors blocks the privilege, even if a child allows it again. Propagate two sets, allow_up and deny_up, each the union over parents plus the role's own list. Then final = allow_up − deny_up. Ask whether one denied path should beat an allowed path; under this rule it usually does.
2. Many queries and live updates. Calls like add_role, grant(parent, child), allow(role, p) and check(role, p) arrive mixed together. Either compute lazily with a memo that you clear for the changed role and all its descendants (BFS over children), or answer each check by walking ancestors on demand. Discuss the read/write ratio: precompute when reads dominate, walk on demand when writes dominate.
3. Explain why. Return the path that grants a privilege (for example viewer -> editor -> lead), or the role whose disallow removed it. Store a back-pointer to the role that first supplied each privilege. Admins need this for audits.
4. Cycles are allowed. Real systems sometimes let roles grant each other. Collapse strongly connected components (Tarjan or Kosaraju), give every role in a component the same set, and run the same algorithm on the condensed DAG. Define what a disallow inside a cycle means before coding.
5. Scale. With millions of roles, map privileges to integer ids and use bitsets. Compute only the ancestors of the roles that are queried. Cache results for each role with a version number that changes when any ancestor changes.

Mid-level (L4)

• Asks which way inheritance flows and what a disallow does, then writes the rule as one formula.
• Writes a correct memoized DFS or topological pass, and handles the diamond case without computing shared ancestors again.
• Tests "allow and disallow on the same role" and empty input without prompting.

Senior (L5)

• Chooses Kahn's algorithm (or an iterative DFS) to avoid deep recursion, and reports cycles and unknown parents as errors.
• States the complexity in terms of R, E and P, and mentions bitsets.
• Moves to the sticky-deny version or live updates quickly, and names which part of the code changes.

Staff (L6+)

• Frames the choice between two deny rules (the final set passes down, or a deny blocks everything below) as a product and security choice, and says which is the safer default.
• Designs for live updates (clearing cached results for descendants, versioned caches) and audit explanations ("why can this role do X?").
• Discusses cycles with SCC condensation, and how a real warehouse such as Snowflake's role hierarchy prevents cycles in the first place.