Role Privilege Inheritance

MediumPython

Problem

In Snowflake role-based access control, a role inherits all privileges assigned to its ancestor roles. Given each role's directly assigned privileges and direct inheritance grants, compute the complete privilege set for every role.

A grant [parent, child] means the child role inherits the parent's privileges. Return one sorted list of unique privilege names per role, including privileges assigned directly to that role and inherited through any number of ancestors.

Formal Specification

Implement calculate_privileges(privileges, grants).

privileges is a list of lists of strings, where privileges[i] contains privileges directly assigned to role i.
grants is a list of two-element integer lists. Each [parent, child] represents a direct inheritance relationship.
Return a list of lists of strings. The result at index i must contain every privilege role i can receive, sorted lexicographically.

The inheritance graph is guaranteed to be a directed acyclic graph, and each role index is valid.

Constraints

1 <= len(privileges) <= 10^4
0 <= len(grants) <= 5 * 10^4
Each privilege list contains at most 10^3 strings
Privilege names contain printable non-whitespace characters
The inheritance graph is acyclic
Duplicate direct assignments and duplicate grants are allowed

Function Signature

def calculate_privileges(privileges, grants):

Formal Specification

Implement calculate_privileges(privileges, grants).

privileges is a list of lists of strings, where privileges[i] contains privileges directly assigned to role i.
grants is a list of two-element integer lists. Each [parent, child] represents a direct inheritance relationship.
Return a list of lists of strings. The result at index i must contain every privilege role i can receive, sorted lexicographically.

The inheritance graph is guaranteed to be a directed acyclic graph, and each role index is valid.