Inherited permissions across teams, folders and files

The entities form a forest: each team is a root, folders are inner nodes, files are leaves. A user can see an entity if their ID is in the userIds of that entity or of any ancestor. Everything follows from that one sentence.

Brute force. For has_access(user, id), scan every entity, and for each one that grants the user access, walk its whole subtree looking for id. For accessible_files(user), do the same and collect leaves. That is O(N) per grant, and overlapping grants (a team and a folder inside it both listing the user) visit the same subtree more than once, so it degrades to O(N * grants).

Better: store parent pointers and children lists.

• has_access(user, id): walk up from id to its root and stop at the first entity whose userIds contains the user. Cost is the depth of the node, not the size of the tree. Store userIds as a set so each check is O(1).
• accessible_files(user): keep an index user -> set of entities granted directly. Start a DFS at each directly granted entity, but skip a start node if an ancestor is also directly granted, because that subtree will be covered anyway. Also keep a seen set as a guard. Every reachable node is then visited once, so the cost is O(size of what the user can see), plus the ancestor checks.

Invariants:

• Every non-team entity has exactly one parent, and the parent is a team or a folder (never a file).
• A team has no parent.
• grants[user] holds exactly the entities whose own userIds contain user.
• Access never comes from a descendant: being on a file does not grant its folder.

Validate input as you build: an unknown parent, a file used as a parent, a duplicate ID, or a team given a parent are errors. Raise them rather than silently ignoring them; interviewers check this.

from collections import defaultdict
from typing import Iterable, Optional

TEAM, FOLDER, FILE = "team", "folder", "file"


class Entity:
    def __init__(self, uuid: str, kind: str, user_ids: Iterable[str],
                 parent: Optional[str]) -> None:
        self.uuid = uuid
        self.kind = kind
        self.user_ids: set[str] = set(user_ids)
        self.parent = parent
        self.children: list[str] = []


class PermissionSystem:
    def __init__(self) -> None:
        self.entities: dict[str, Entity] = {}
        self.grants: dict[str, set[str]] = defaultdict(set)  # user -> direct grants

    # ---- building the tree -------------------------------------------------
    def add_team(self, uuid: str, user_ids: Iterable[str] = ()) -> None:
        self._add(uuid, TEAM, user_ids, None)

    def add_folder(self, uuid: str, parent: str, user_ids: Iterable[str] = ()) -> None:
        self._add(uuid, FOLDER, user_ids, parent)

    def add_file(self, uuid: str, parent: str, user_ids: Iterable[str] = ()) -> None:
        self._add(uuid, FILE, user_ids, parent)

    def _add(self, uuid: str, kind: str, user_ids: Iterable[str],
             parent: Optional[str]) -> None:
        if uuid in self.entities:
            raise ValueError(f"duplicate id {uuid}")
        if parent is not None:
            p = self.entities.get(parent)
            if p is None:
                raise KeyError(f"unknown parent {parent}")
            if p.kind == FILE:
                raise ValueError("a file cannot contain children")
            p.children.append(uuid)
        node = Entity(uuid, kind, user_ids, parent)
        self.entities[uuid] = node
        for u in node.user_ids:
            self.grants[u].add(uuid)

    # ---- queries -----------------------------------------------------------
    def has_access(self, user: str, uuid: str) -> bool:
        if uuid not in self.entities:
            raise KeyError(uuid)
        cur: Optional[str] = uuid
        while cur is not None:
            node = self.entities[cur]
            if user in node.user_ids:
                return True
            cur = node.parent
        return False

    def accessible(self, user: str, kind: Optional[str] = None) -> list[str]:
        """All entities the user can see (optionally only one kind), sorted."""
        starts = self.grants.get(user, set())
        out: list[str] = []
        seen: set[str] = set()
        for start in starts:
            if self._ancestor_granted(user, start):
                continue  # covered by a higher grant
            stack = [start]
            while stack:
                cur = stack.pop()
                if cur in seen:
                    continue
                seen.add(cur)
                node = self.entities[cur]
                if kind is None or node.kind == kind:
                    out.append(cur)
                stack.extend(node.children)
        return sorted(out)

    def accessible_files(self, user: str) -> list[str]:
        return self.accessible(user, FILE)

    def _ancestor_granted(self, user: str, uuid: str) -> bool:
        parent = self.entities[uuid].parent
        return parent is not None and self.has_access(user, parent)

Quick check:

ps = PermissionSystem()
ps.add_team("t1", ["ana"])
ps.add_folder("design", "t1", ["bo"])
ps.add_folder("icons", "design")
ps.add_file("logo", "icons")
ps.add_file("notes", "t1", ["cy"])
assert ps.has_access("bo", "logo") and not ps.has_access("bo", "notes")
assert ps.accessible_files("ana") == ["logo", "notes"]
assert ps.accessible_files("cy") == ["notes"]

Let N be the number of entities, D the depth of the tree, and G the number of direct grants for the queried user.

• add_team / add_folder / add_file: O(1 + k) for k listed users.
• has_access: O(D) time, O(1) extra space.
• accessible / accessible_files: O(G * D + R) time, where R is the number of entities the user can reach; O(R) space for seen and the output (plus O(R log R) if you sort the output).
• Memory overall: O(N + total user IDs listed).

Tree used below: team t1 (users: ana) contains folder design (users: bo) and file notes (users: cy). design contains folder icons (no users), which contains file logo. A second team t2 (users: bo) contains file roadmap.

• has_access("ana", "logo") -> True (inherits from t1 through two levels).
• has_access("bo", "logo") -> True (from design).
• has_access("bo", "notes") -> False (sibling of design, not a descendant).
• has_access("cy", "t1") -> False (access never flows upward).
• accessible_files("ana") -> ["logo", "notes"].
• accessible_files("bo") -> ["logo", "roadmap"] (grants across two teams).
• accessible_files("cy") -> ["notes"].
• accessible_files("zed") -> [] (unknown user).
• Overlapping grants: add ana to icons as well; accessible("ana") still lists logo once.
• An empty folder with a grant: accessible("bo", "folder") includes it; accessible_files does not.
• Errors: add_file("x", "logo") raises (file as parent); add_folder("x", "nope") raises (unknown parent); adding t1 again raises (duplicate ID); has_access("ana", "nope") raises.

1. Build from a nested JSON input (each entity lists its children instead of its parent). Do one DFS that calls _add with the current parent. Watch for very deep trees: use an explicit stack instead of recursion.
2. Move an entity to a new parent. Remove it from the old parent's children, append to the new one, update parent. Reject moves into its own subtree (walk up from the new parent; if you meet the moved node, it is a cycle). Nothing else changes, because access is computed on read.
3. Grant and revoke at runtime. Add or remove the user from the entity's set and from grants[user]. Revoking on a folder does not remove access that comes from a higher grant; say this out loud. If the product needs "deny" rules (explicitly block a subtree), has_access walks up and the nearest explicit allow or deny wins.
4. Many reads, few writes. Cache each user's accessible set, or precompute an Euler tour (entry and exit times) so "is X under Y" is two integer comparisons; a user then has access to X if any granted Y's interval contains X's entry time. Moves invalidate the tour, so rebuild it lazily or keep the walk-up path for write-heavy workloads.
5. Roles instead of plain access (viewer < editor < owner, as in a real design tool). Store user -> role on each entity and take the maximum role over the ancestor path. A file-level invite can raise a role but not lower an inherited one.

Mid-level (L4)

• Models the hierarchy with parent and children links and gets has_access right by walking up.
• Produces correct accessible files, with no duplicates when grants overlap.
• Handles an unknown user and an empty folder.

Senior (L5)

• States time in terms of depth and reachable size, and avoids re-walking covered subtrees.
• Validates input (file as parent, unknown parent, duplicate IDs) and explains why access never flows upward.
• Handles move and revoke cleanly, including cycle detection on move.

Staff (L6+)

• Discusses read-heavy versus write-heavy trade-offs: compute on read, cached per-user sets, Euler-tour intervals, and their invalidation cost.
• Extends to roles, deny rules, and group membership (users in groups granted on entities) without rewriting the core.
• Talks about storing this in a database (closure table or materialized path) and keeping permission checks consistent during concurrent moves.