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
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.
### 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, i.e. character by character by character code, a proper prefix being smaller; so `user_10` comes before `user_9`).
- Duplicate triples may appear and have no additional effect.
### Input and output per language
Each triple is a 3-element sequence of strings: a tuple or list in Python, an array in JavaScript, a `java.util.List<String>` in Java and a `std::vector<std::string>` in C++. The no-answer result is `None` in Python, `null` in JavaScript and Java, and an empty `std::optional<std::string>` (`std::nullopt`) in C++. No numeric values are involved, so nothing can exceed 2^31-1.
### 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 `_`.
### 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_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.
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 '_'.
- Group membership may contain cycles (including a group listed as a member of itself), and duplicate triples may appear.
Examples
Input: ([],)
Expected Output: None
Explanation: Empty input has no cameras, so the result is None.
Input: ([('user_a', 'group_member', 'group_x'), ('group_x', 'group_member', 'group_y')],)
Expected Output: None
Explanation: Only group_member triples: no camera exists, so the result is None.
Hints
- The camera list is fixed by the camera_owner destinations alone. Settle it first, including the case where there are none.
- A user's cameras are the ones it owns plus those owned by every group reachable by following group_member links upward. Make sure that walk terminates when the links form a cycle, and that nothing flows from a member back up to its group.
- When several users qualify, compare their IDs as plain strings, not by any number inside them.