Compute Inherited Role Privileges
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given n roles. The array initialPrivileges has length n, where initialPrivileges[i] is the list of privileges directly assigned to role i. You are also given a list of grants. Each grant is a pair [parent, child], meaning role child inherits all privileges from role parent. The grant graph is guaranteed to be a directed acyclic graph, so there are no cycles.
Return the complete set of privileges for every role after applying all inherited grants from every ancestor role. Duplicate privileges should appear only once per role. You may return each role's privileges in any deterministic order, such as sorted lexicographically.
Example:
initialPrivileges = [["A"], ["B"], ["C"]]
grants = [[0, 1], [1, 2]]
Role 1 inherits from role 0, and role 2 inherits from roles 1 and 0 transitively.
Output:
[["A"], ["A", "B"], ["A", "B", "C"]]
Quick Answer: This question evaluates understanding of directed acyclic graph traversal, transitive inheritance, and set aggregation/deduplication, assessing competency in graph algorithms, data structures, and permission-model reasoning.
You are given roles numbered from 0 to n - 1. The list initialPrivileges has length n, where initialPrivileges[i] contains the privileges directly assigned to role i. You are also given a list of grants, where each grant is a pair [parent, child]. This means role child inherits every privilege from role parent, including privileges parent inherited transitively from its own ancestors.
The grant graph is guaranteed to be a directed acyclic graph (DAG), so inheritance never forms a cycle.
Return the complete privilege list for every role after applying all inheritance rules. Each role's result must contain unique privileges only, and for deterministic output, each role's privileges should be sorted lexicographically.
Constraints
- 0 <= n == len(initialPrivileges) <= 10^4
- 0 <= len(grants) <= 2 * 10^4
- 0 <= parent, child < n for every [parent, child] in grants
- The grant graph is a directed acyclic graph
- The total number of directly listed privileges across all roles is at most 2 * 10^4
Examples
Input: ([['A'], ['B'], ['C']], [[0, 1], [1, 2]])
Expected Output: [['A'], ['A', 'B'], ['A', 'B', 'C']]
Explanation: Role 1 inherits A from role 0. Role 2 inherits from role 1, so it gets both A and B in addition to its own C.
Input: ([['read', 'write'], ['write', 'write'], ['execute'], []], [[0, 3], [1, 3], [2, 3]])
Expected Output: [['read', 'write'], ['write'], ['execute'], ['execute', 'read', 'write']]
Explanation: Role 3 inherits privileges from three parents. Duplicate privileges such as write appear only once in the final result.
Hints
- Because the inheritance graph is a DAG, think about processing roles in topological order so that a parent is handled before its children.
- Use a set for each role to merge privileges efficiently and automatically remove duplicates.