progress

~/problems / Graphs / Topological sort (Kahn's)

Inherited permissions with allow and disallow

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium assessment 2 levels ~30 min Snowflake

Level 1 Inherited permissions

There are n roles, numbered 0..n-1. perms[i] is a list of the permission names that role i holds itself. inherits is a list of [parent, child] pairs: the child gets everything the parent has, including everything the parent inherited. The pairs form a DAG (no cycles), and a role can have several parents.

Write effective_permissions(perms: list[list[str]], inherits: list[list[int]]) -> list[list[str]]. It returns, for each role, the sorted list (without duplicates) of permissions it has once inheritance is applied.

Graphs have up to 50,000 roles and 150,000 edges.

⭐ Bonus: a speed test with a 50,000-role chain earns a star if each edge is handled once, without recursion. Walking up through every role's ancestors separately is too slow for it.

effective_permissions([["read"], ["write"], ["admin"], []],
                      [[0, 1], [1, 2], [0, 3]])
# [["read"], ["read", "write"], ["admin", "read", "write"], ["read"]]
Show hint

A role's answer is its own permissions plus its parents' finished answers, so handle each role only after all of its parents are done.

Level 2 unlocks when level 1 passes.

Topic: Topological sort (Kahn's). BFS over in-degree-0 nodes; leftover nodes mean a cycle.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc