Account Roles With Parent-User Inheritance
Problem statement
Users own accounts, and roles are granted on accounts. You are given three lists:
accounts: each entry"accountId,userId"says that the user owns the account. Every account has exactly one owner; a user may own several accounts or none.roles: each entry"accountId,role"grants the role on that account. A user directly holds every role granted on any account they own.parents: each entry"userId,parentUserId"gives a user's parent user. A user has at most one parent, and the links never form a cycle.
A user holds a role if the user or any ancestor (the parent, the parent's parent, and so on) directly holds it. Roles pass from parents to children only, never from a child to its parent. The users of the system are everyone who appears in accounts or parents.
Answer each query in queries, in order:
"roles u": every role that useruholds."users r1 r2 ...": every user who holds all of the listed roles.
Each answer lists every value once, sorted in increasing character order. Return the answers as a list with one entry per query.
Function
answerAccessQueries(accounts: String[], roles: String[], parents: String[], queries: String[]) → String[][]Examples
Example 1
accounts = ["a1,alice","a2,alice","b1,bob","c1,carol"]roles = ["a1,admin","a2,viewer","b1,editor","c1,viewer"]parents = ["bob,alice","dave,bob"]queries = ["roles alice","roles bob","roles dave","users viewer","users admin editor"]return = [["admin","viewer"],["admin","editor","viewer"],["admin","editor","viewer"],["alice","bob","carol","dave"],["bob","dave"]]aliceownsa1anda2, so her roles areadminandviewer.bob's parent isalice. He haseditorfromb1and inheritsadminandviewer.daveowns no account, but his parent isbob, so he inherits everythingbobhas:admin,editor,viewer.vieweris held byalice,bob,carolanddave.- Only
bobanddavehold bothadminandeditor.
Example 2
accounts = ["p1,parent","k1,kid"]roles = ["p1,billing","k1,support"]parents = ["kid,parent"]queries = ["roles parent","roles kid","users support","users billing support","users owner"]return = [["billing"],["billing","support"],["kid"],["kid"],[]]Roles flow from a parent to its child, never back up: parent keeps only billing, while kid has support plus the inherited billing. So support is held only by kid, and kid is also the only user with both billing and support. Nobody holds owner, so that answer is empty.
Example 3
accounts = ["x1,u3","x2,u3","y1,u1"]roles = ["x1,read","x2,read","y1,write"]parents = ["u2,u1","u3,u2"]queries = ["roles u3","users read write"]return = [["read","write"],["u3"]]u3's parent is u2, whose parent is u1. Roles are inherited through every ancestor, so u3 gets write from its grandparent u1. read is granted on two of u3's accounts but is listed once. u3 is the only user with both roles.
Constraints
1 <= accounts.length <= 3001 <= roles.length <= 6000 <= parents.length <= 1991 <= queries.length <= 100- Every account ID, user ID and role has 1 to 10 characters, each a lowercase English letter or a digit.
- Account IDs in
accountsare distinct, and every account named inrolesappears inaccounts. - In
parents, no user is its own parent, no user has two parents, the links form no cycle, and there are at most 200 distinct users in total. - Each query is
"roles u"for a useruof the system, or"users"followed by 1 to 5 distinct roles, separated by single spaces.