How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snowflake.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snowflake during technical interviews.

Compute Inherited Role Privileges | Snowflake Coding Question

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.

Input: ([['admin'], [], ['audit'], ['user']], [[0, 1], [1, 2]])

Expected Output: [['admin'], ['admin'], ['admin', 'audit'], ['user']]

Explanation: Role 1 inherits admin from role 0, and role 2 inherits from role 1 transitively. Role 3 is disconnected and keeps only its own privilege.

Input: ([], [])

Expected Output: []

Explanation: There are no roles, so the result is an empty list.

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.

Quick Overview

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.