Page Permission Inheritance
Notion● MediumFULLTIMEPHONE SCREENONSITE INTERVIEWProblem statement
Permission roles have this increasing order: NONE < VIEW < COMMENT < EDIT. Pages form a rooted forest. Each pageParents row is [pageId, parentId], with - for a root.
A user can receive a role directly through [pageId, userId, role] in userPermissions, or through a group. Each group membership is [groupId, userId], and each group permission is [pageId, groupId, role].
A permission applies to its page and every descendant. A user's effective role on pageId is the most permissive role from every direct or group permission on that page or an ancestor.
Return two strings:
- the effective role for the requested
userId; - every user named by either permission input whose effective role is above
NONE, formatted asuserId:rolein lexicographic user-ID order and joined by commas, or the empty string when no user qualifies.
Function
resolvePagePermissions(pageParents: String[][], userPermissions: String[][], groupMemberships: String[][], groupPermissions: String[][], pageId: String, userId: String) → String[]Examples
Example 1
pageParents = [["root","-"],["child","root"]]userPermissions = [["root","alice","VIEW"],["child","bob","COMMENT"]]groupMemberships = [["editors","carol"],["editors","alice"]]groupPermissions = [["child","editors","EDIT"]]pageId = "child"userId = "alice"return = ["EDIT","alice:EDIT,bob:COMMENT,carol:EDIT"]Alice inherits VIEW from root and receives EDIT from the child page through editors, so EDIT wins. The second row lists every user with a non-NONE effective role in user-ID order.
Constraints
1 <= pageParents.length <= 500.- Every page appears once, parent references are valid, and the page hierarchy has no cycle.
0 <= userPermissions.length, groupMemberships.length, groupPermissions.length <= 2000.- IDs are non-empty ASCII strings containing neither a comma, colon, nor whitespace.
- Every role is one of
NONE,VIEW,COMMENT, orEDIT. - The requested page exists; the requested user need not appear in the permission data.