How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Verkada.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Verkada during technical interviews.

Find users with access to all cameras | Verkada Coding Question

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.

Input: (['a','b'], [], [], [('a','g1')], [('g1','camX')], [('g1','g2'),('g2','g1')])

Expected Output: ['a','b']

Explanation: There are no required cameras, so every admin vacuously has access to all cameras.

Input: (['root','super'], ['cam1'], [('root','cam1'),('root','cam1')], [('super','g1')], [], [])

Expected Output: ['root']

Explanation: root directly owns cam1. Duplicate ownership entries do not affect the result. super cannot reach any camera.

Input: (['ann','ben'], ['c1','c2','c3'], [], [('ann','g1'),('ben','g2')], [('g1','c1'),('g2','c1'),('g3','c2')], [('g1','g3'),('g2','g3')])

Expected Output: []

Explanation: Both admins can reach c1 and c2, but c3 is in the required camera list and is owned by nobody, so no admin qualifies.

Solution

def solution(admin_users, cameras, user_owns, user_groups, group_owns, group_parents):
    from collections import defaultdict, deque

    all_cameras = set(cameras)

    user_to_cameras = defaultdict(set)
    user_to_groups = defaultdict(list)
    group_to_cameras = defaultdict(set)
    group_to_parents = defaultdict(list)

    for user, camera in user_owns:
        user_to_cameras[user].add(camera)

    for user, group in user_groups:
        user_to_groups[user].append(group)

    for group, camera in group_owns:
        group_to_cameras[group].add(camera)

    for child_group, parent_group in group_parents:
        group_to_parents[child_group].append(parent_group)

    result = []

    for admin in admin_users:
        accessible = set(user_to_cameras.get(admin, ()))

        if accessible.issuperset(all_cameras):
            result.append(admin)
            continue

        visited_groups = set()
        queue = deque(user_to_groups.get(admin, ()))

        while queue and not accessible.issuperset(all_cameras):
            group = queue.popleft()
            if group in visited_groups:
                continue

            visited_groups.add(group)
            accessible.update(group_to_cameras.get(group, ()))

            for parent in group_to_parents.get(group, ()): 
                if parent not in visited_groups:
                    queue.append(parent)

        if accessible.issuperset(all_cameras):
            result.append(admin)

    return result

Time complexity: O(E + A * E) worst case, where E is the total number of relationship pairs and A is len(admin_users). Space complexity: O(E + C), where E is the total number of relationship pairs and C is the number of distinct cameras.

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.

Quick Overview

This question evaluates understanding of graph modeling and traversal techniques, particularly transitive closure, cycle detection, and BFS-based permission propagation across nested group relationships.