0

Page permission management

by Frontier Interview· about 3 hours ago· ⑂ 0 remixes

Question: Page permission management

Companies: Notion

Difficulty: Medium

Problem statement

Implement page-level permissions: grant and revoke access for users on pages, and answer whether a user can view or edit a page, respecting the page hierarchy. Reported on 1point3acres' Notion bank; reconstructed in our own words.

Clarify the setup

Pages form a tree (a workspace's top-level pages, their sub-pages, and so on). Build:

  • add_page(page_id, parent_id=None), move_page(page_id, new_parent_id).
  • grant(page_id, principal, level) and revoke(page_id, principal) with levels view < comment < edit < full.
  • can(user, page_id, action) -> bool where an action needs a minimum level (view needs view, edit needs edit, share needs full access).

Ask how inheritance works. The common product rules, and the ones used here:

  • Access flows down. A grant on a page applies to all its sub-pages.
  • The strongest grant wins. If a user can view a parent and edit a child, they can edit the child.
  • Restricted pages stop inheritance. A page can be marked restricted: grants above it no longer apply to it or its sub-pages; only grants on the page itself and below count. That is how a private sub-page lives inside a shared team page.
  • Groups. A grant to a group applies to its members (part 2).
  • The page creator or workspace owner usually has full access; model them as ordinary grants.

Approach

Store grants where they are made, not copied onto every descendant: grants[page][principal] = level. Copying would make every share, revoke and move touch the whole subtree.

Check by walking up. effective_level(user, page): start at the page and walk parent pointers to the root. At each page, take the highest level granted to any of the user's principals (the user plus their groups). Stop after processing a restricted page (its ancestors no longer count). The answer is the maximum seen. Cost: O(depth × principals of the user at each page), with depth rarely above 10.

Moves are free. Because grants live on pages and checks walk the current tree, moving a page under a different parent changes its inherited access automatically. That is the behavior users expect ("I moved the page into the private section, now it is private") and the reason not to precompute.

Listing what a user can see (part 2) walks down instead: a DFS from the roots that carries "the best level inherited so far", resetting it at restricted pages. O(pages) for one user; cache per user and invalidate on changes for search filtering.

Code

from typing import Dict, Iterable, List, Optional, Set

LEVELS = {"none": 0, "view": 1, "comment": 2, "edit": 3, "full": 4}
ACTIONS = {"view": "view", "comment": "comment", "edit": "edit", "share": "full", "delete": "full"}


class Permissions:
    def __init__(self) -> None:
        self.parent: Dict[str, Optional[str]] = {}
        self.children: Dict[str, Set[str]] = {}
        self.restricted: Set[str] = set()
        self.grants: Dict[str, Dict[str, int]] = {}
        self.groups: Dict[str, Set[str]] = {}        # user -> groups

    # ---- pages ----------------------------------------------------------------
    def add_page(self, page: str, parent: Optional[str] = None, restricted: bool = False) -> None:
        if page in self.parent:
            raise ValueError(f"{page} exists")
        if parent is not None and parent not in self.parent:
            raise KeyError(parent)
        self.parent[page] = parent
        self.children[page] = set()
        if parent is not None:
            self.children[parent].add(page)
        if restricted:
            self.restricted.add(page)

    def move_page(self, page: str, new_parent: Optional[str]) -> None:
        node = new_parent
        while node is not None:                       # no moving under yourself
            if node == page:
                raise ValueError("cannot move a page under itself")
            node = self.parent[node]
        old = self.parent[page]
        if old is not None:
            self.children[old].discard(page)
        self.parent[page] = new_parent
        if new_parent is not None:
            self.children[new_parent].add(page)

    def set_restricted(self, page: str, restricted: bool) -> None:
        (self.restricted.add if restricted else self.restricted.discard)(page)

    # ---- grants ---------------------------------------------------------------
    def grant(self, page: str, principal: str, level: str) -> None:
        if level not in LEVELS or level == "none":
            raise ValueError(level)
        self.grants.setdefault(page, {})[principal] = LEVELS[level]

    def revoke(self, page: str, principal: str) -> None:
        self.grants.get(page, {}).pop(principal, None)

    def add_to_group(self, user: str, group: str) -> None:
        self.groups.setdefault(user, set()).add(group)

    # ---- checks -----------------------------------------------------------------
    def principals(self, user: str) -> Set[str]:
        return {user} | self.groups.get(user, set())

    def effective_level(self, user: str, page: str) -> int:
        who = self.principals(user)
        best = 0
        node: Optional[str] = page
        while node is not None:
            for principal, level in self.grants.get(node, {}).items():
                if principal in who and level > best:
                    best = level
            if node in self.restricted:
                break                                  # nothing above a restricted page counts
            node = self.parent[node]
        return best

    def can(self, user: str, page: str, action: str) -> bool:
        if page not in self.parent:
            return False
        return self.effective_level(user, page) >= LEVELS[ACTIONS[action]]

    def visible_pages(self, user: str) -> List[str]:
        """Part 2: every page the user can view, by a walk down the tree."""
        who = self.principals(user)
        out: List[str] = []
        stack = [(p, 0) for p, par in self.parent.items() if par is None]
        while stack:
            page, inherited = stack.pop()
            if page in self.restricted:
                inherited = 0
            here = max([inherited] + [lvl for pr, lvl in self.grants.get(page, {}).items() if pr in who])
            if here >= LEVELS["view"]:
                out.append(page)
            stack.extend((c, here) for c in self.children[page])
        return sorted(out)

Complexity

  • can: O(depth × grants per page on the path). Typical trees are shallow (under 10 levels), so a check is a handful of dictionary lookups.
  • grant, revoke, move_page: O(1), plus O(depth) for the cycle check in move_page.
  • visible_pages: O(pages + grants) per user.

Test cases

def _workspace():
    p = Permissions()
    p.add_page("team")
    p.add_page("roadmap", "team")
    p.add_page("q3", "roadmap")
    p.add_page("salaries", "team", restricted=True)
    p.grant("team", "ana", "edit")
    p.grant("team", "bo", "view")
    p.grant("q3", "bo", "comment")
    p.grant("salaries", "cy", "full")
    return p


def test_inheritance_and_strongest_grant():
    p = _workspace()
    assert p.can("ana", "q3", "edit")
    assert p.can("bo", "roadmap", "view") and not p.can("bo", "roadmap", "comment")
    assert p.can("bo", "q3", "comment")              # child grant is stronger
    assert not p.can("dan", "team", "view")


def test_restricted_page_blocks_inherited_access():
    p = _workspace()
    assert not p.can("ana", "salaries", "view")
    assert p.can("cy", "salaries", "share")
    p.set_restricted("salaries", False)
    assert p.can("ana", "salaries", "edit")


def test_revoke_and_move():
    p = _workspace()
    p.revoke("team", "ana")
    assert not p.can("ana", "q3", "view")
    p.grant("team", "ana", "edit")
    p.move_page("q3", "salaries")                     # moved into the restricted page
    assert not p.can("ana", "q3", "view") and p.can("cy", "q3", "edit")
    try:
        p.move_page("team", "q3")
        assert False
    except ValueError:
        pass

def test_groups_and_visible_pages():
    p = _workspace()
    p.add_to_group("eve", "design")
    p.grant("roadmap", "design", "view")
    assert p.can("eve", "q3", "view") and not p.can("eve", "team", "view")
    assert p.visible_pages("eve") == ["q3", "roadmap"]
    assert p.visible_pages("ana") == ["q3", "roadmap", "team"]
    assert p.visible_pages("cy") == ["salaries"]


def test_visible_pages_matches_can():
    import random
    rng = random.Random(4)
    p = Permissions()
    pages = ["p0"]
    p.add_page("p0")
    for i in range(1, 60):
        page = f"p{i}"
        p.add_page(page, rng.choice(pages), restricted=rng.random() < 0.15)
        pages.append(page)
    users = ["u1", "u2", "u3"]
    for _ in range(40):
        p.grant(rng.choice(pages), rng.choice(users), rng.choice(["view", "edit", "full"]))
    for u in users:
        assert p.visible_pages(u) == sorted(x for x in pages if p.can(u, x, "view"))

Follow-ups

  1. Explicit deny. "Everyone in the workspace except contractors" needs deny grants. Define precedence clearly (deny on the closest page wins, or deny always wins) and test it; deny rules are where permission bugs hide.
  2. Caching. Permission checks run on every page load and for every search result. Cache effective_level(user, page) with a version number per workspace bumped on any grant, group or move change; or cache per page the list of grants on its path, invalidated for the subtree on change.
  3. Search filtering. Do not check thousands of candidates one by one; precompute per page the set of principals with access (materialized on change, for the subtree) and filter in the search index, then re-check the few results shown.
  4. Public links and guests. "Anyone with the link can view" is a grant to a special principal that every request presents when it has the link; guests are users outside the workspace whose grants never include workspace-wide groups.
  5. Audit. Record every grant, revoke, restriction and move with who did it and when. "Why can Bo see this page?" is answered by returning the grant and the page it came from, which the walk-up already finds.

Interviewer expectations

Mid-level (L4)

  • Models pages as a tree with grants per page and checks by walking up to the root.
  • Gets view versus edit right with ordered levels.
  • Tests inheritance and revocation.

Senior (L5)

  • Restricted pages that stop inheritance, strongest-grant semantics, and moves that change access without data migration.
  • Prevents moving a page under its own descendant.
  • Lists visible pages with a top-down walk and tests it against per-page checks.

Staff (L6+)

  • Designs caching and invalidation, and search filtering at scale with materialized principal sets.
  • Handles deny rules, guests and public links with clear precedence.
  • Plans auditability ("why does this person have access?") and the performance budget of checks per page load.

Sign in to comment, vote or remix.