Find users with access to all cameras

Q: Find users with access to all cameras

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

Q: 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.

Q: What difficulty level is this coding question?

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

Q: What role is this question designed for?

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

Question

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.

PracHub · Accepted Answer

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

Quick Overview

Solution

Hints

Quick Overview