FastPrep
Problem · Graph

Effective Role Privileges

Learn this problem
● MediumSnowflakeFULLTIMEPHONE SCREEN
See Snowflake hiring insights

Problem statement

You are given n roles. Role i has a list of direct privileges privileges[i]. You are also given inheritance relations grants, where each pair [u, v] means role v inherits every privilege from role u.

The inheritance graph is a directed acyclic graph. A role's effective privileges are all privileges from its ancestors plus its own direct privileges.

Return the effective privileges for every role. Remove duplicates within each role and return each role's privilege list in lexicographic order.

Function

getEffectivePrivileges(privileges: String[][], grants: int[][]) → String[][]

Examples

Example 1

privileges = [["A"],["B"],["C"]]grants = [[0,1],[1,2]]return = [["A"],["A","B"],["A","B","C"]]

Role 1 inherits role 0, and role 2 inherits both role 1 and role 0 transitively.

Example 2

privileges = [["READ"],["WRITE"],["DEPLOY"],["AUDIT"]]grants = [[0,2],[1,2],[2,3]]return = [["READ"],["WRITE"],["DEPLOY","READ","WRITE"],["AUDIT","DEPLOY","READ","WRITE"]]

Example 3

privileges = [["A","A"],["A"],[]]grants = [[0,1],[1,2]]return = [["A"],["A"],["A"]]

Constraints

  • 1 <= privileges.length <= 2 * 10^5
  • 0 <= grants.length <= 2 * 10^5
  • Each grant is a pair [u, v] with 0 <= u, v < privileges.length.
  • The role inheritance graph is a DAG.
  • Privilege strings are non-empty tokens without spaces.

More Snowflake problems

drafts saved locally
public String[][] getEffectivePrivileges(String[][] privileges, int[][] grants) {
    // write your code here
}
privileges[["A"],["B"],["C"]]
grants[[0,1],[1,2]]
expected[["A", "A", "B", "A", "B", "C"]]
checking account