Find the Super Admin User Who Can Access Every Camera Through Nested Groups
Company: Verkada
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
An enterprise permission system for security cameras is built on roles and groups. It has three kinds of entities: users, groups and cameras. You are given the permission relationships as a list `perms_data` of triples `(source, relationship, destination)`, using two relationships:
- `(entity, "camera_owner", camera_id)`: the entity (a user or a group) directly holds access and management rights to the camera.
- `(entity, "group_member", group_id)`: the entity (a user or a group) is a member of the group. Permissions are transitive: a member inherits every camera owned by that group and by every group above it in the nesting, at any depth.
Find the super admin: the single user who can access every camera in the organization. Return that user's ID, or `None` if no single user can access all of the cameras.
### Function Signature
```python
def find_admin_user(perms_data: list[tuple[str, str, str]]) -> str | None:
```
### Rules
- IDs are typed by prefix: users start with `"user_"`, groups with `"group_"` and cameras with `"camera_"`.
- The cameras in the organization are exactly the IDs that appear as the destination of at least one `"camera_owner"` triple.
- A user can access a camera if the user owns it directly, or if a chain of `"group_member"` triples leads from the user to a group that owns it (for example, `user_x` is a member of `group_a`, `group_a` is a member of `group_b`, and `group_b` owns the camera).
- Permissions flow only from a group to its members. A group does not gain a camera because one of its members owns it, and access is never pooled across users: each user must reach every camera alone.
- Group membership may contain cycles: two groups may each be a member of the other, a longer cycle may exist, and a group may be listed as a member of itself. Your function must terminate on such input, and the access rule above applies unchanged.
- Only a user can be returned. A group that can access every camera is never the answer.
- Every user ID that appears in `perms_data` is a candidate, including a user who appears only in `"group_member"` triples.
- If no camera appears in the input (including when `perms_data` is empty), return `None`.
- If more than one user can access every camera, return the ID that is smallest under ordinary string comparison (Python's default `str` ordering).
- Duplicate triples may appear and have no additional effect.
### Constraints
- `0 <= len(perms_data) <= 5000`
- Each `relationship` is exactly `"camera_owner"` or `"group_member"`.
- In a `"camera_owner"` triple, the source starts with `"user_"` or `"group_"`, and the destination starts with `"camera_"`.
- In a `"group_member"` triple, the source starts with `"user_"` or `"group_"`, and the destination starts with `"group_"`.
- Every ID is its prefix (`"user_"`, `"group_"` or `"camera_"`) followed by 1 to 20 characters, each a lowercase English letter, a digit or `_`.
### Examples
**Example 1**
```text
Input: perms_data = [
("user_admin", "group_member", "group_sec"),
("group_sec", "camera_owner", "camera_1"),
("group_sec", "camera_owner", "camera_2"),
("user_admin", "camera_owner", "camera_3"),
("user_bob", "camera_owner", "camera_1")
]
Output: "user_admin"
```
The cameras are `camera_1`, `camera_2` and `camera_3`. `user_admin` owns `camera_3` directly and inherits `camera_1` and `camera_2` through `group_sec`. `user_bob` can access only `camera_1`.
**Example 2**
```text
Input: perms_data = [
("user_super", "group_member", "group_exec"),
("group_exec", "group_member", "group_ops"),
("group_ops", "camera_owner", "camera_hq"),
("user_super", "camera_owner", "camera_branch")
]
Output: "user_super"
```
The cameras are `camera_hq` and `camera_branch`. `user_super` inherits `camera_hq` along the chain `user_super -> group_exec -> group_ops` and owns `camera_branch` directly.
**Example 3**
```text
Input: perms_data = [
("user_alice", "camera_owner", "camera_1"),
("user_bob", "camera_owner", "camera_2")
]
Output: None
```
Each user can access only one of the two cameras, so no single user covers them all.
Overview: Given permission triples linking users, groups and cameras, find the user who can access every camera through direct ownership or through nested, possibly cyclic group memberships. It tests modeling permissions as a directed graph, reachability that tolerates membership cycles, and edge cases such as an input with no cameras or a group that covers everything.
Read the full Verkada Software Engineer interview experience this question came from