Find users with access to all cameras
Company: Verkada
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given entities and relationships (user, owns, camera), (user, belongs_to, group), (group, owns, camera), and (group, belongs_to, group) where groups can be nested arbitrarily, a user has access to a camera if they directly own it or belong transitively to any group that owns it. Design an algorithm to find all admin users who have access to every camera. Specify the input representation, handle cycles in group membership, describe a BFS-based approach, and analyze time and space complexity. Provide the algorithm steps and discuss edge cases.
Quick Answer: This question evaluates understanding of graph modeling and traversal techniques, particularly transitive closure, cycle detection, and BFS-based permission propagation across nested group relationships.
You are given admin users, a complete list of cameras, and four kinds of relationships:
- (user, camera) in user_owns
- (user, group) in user_groups
- (group, camera) in group_owns
- (child_group, parent_group) in group_parents
A user has access to a camera if:
1. the user directly owns the camera, or
2. the user belongs to a group that owns the camera, or
3. the user belongs to a group that belongs to another group, and that ancestor group owns the camera.
Group nesting can be arbitrarily deep, and group membership may contain cycles. For example, g1 may belong to g2 and g2 may belong back to g1.
Write a function that returns all admin users who have access to every camera in the given cameras list. The returned admin IDs must appear in the same order as admin_users.
A BFS-based approach is expected:
- Build adjacency maps for fast lookups.
- For each admin, start with cameras they directly own.
- Run BFS from the user's direct groups through parent groups.
- Use a visited set to avoid infinite loops caused by cycles.
- Collect all cameras owned by visited groups.
- If the admin can reach every camera in cameras, include them in the result.
Edge cases to handle:
- If cameras is empty, every admin qualifies.
- Cycles in group_parents must not cause infinite loops.
- Duplicate relationship pairs should not change the answer.
- If a camera appears in cameras but is owned by nobody, then no admin can have access to every camera.
Constraints
- 0 <= len(admin_users) <= 10^3
- 0 <= total number of relationship pairs across all lists <= 2 * 10^4
- group_parents may contain cycles and duplicate edges
- Camera and entity IDs are strings
Examples
Input: (['alice','bob','carol'], ['c1','c2','c3'], [('bob','c1')], [('alice','g1'),('bob','g2'),('carol','g3')], [('g1','c1'),('g2','c2'),('g3','c1'),('g4','c3'),('g5','c2')], [('g1','g4'),('g2','g5'),('g3','g4'),('g5','g4')])
Expected Output: ['bob']
Explanation: Bob directly owns c1 and reaches g2 -> g5 -> g4, which gives c2 and c3. Alice and Carol each miss c2.
Input: (['u1','u2'], ['c1','c2'], [], [('u1','g1'),('u2','g3')], [('g2','c1'),('g3','c2')], [('g1','g2'),('g2','g1'),('g1','g3')])
Expected Output: ['u1']
Explanation: u1 reaches g1, then g2 and g3. The cycle between g1 and g2 is harmless with a visited set. u1 gets both cameras; u2 gets only c2.
Hints
- Build hash maps from users to groups, groups to parent groups, and entities to owned cameras so each BFS step is efficient.
- For each admin, use a queue to explore reachable groups and a visited set to prevent revisiting groups in a cycle.