Verkada Inc.·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Verkada coding screen for a software engineer role, one algorithmic problem centered on permission graph traversal. Pretty niche problem space given what the company actually does, which in hindsight makes sense.

Questions Asked (1)

You're given a list of (subject, relationship, object) permission tuples where subjects can be users or groups and objects include cameras. Write code to find the single user who has access to every camera, either directly or through arbitrarily nested group memberships (no cycles in the group graph).

Algorithms & Data StructuresSystem Design

Author's notes

The graph traversal part wasn't too bad once I drew it out, but I kept second-guessing whether to go top-down from cameras or bottom-up from users.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph where nodes are subjects (users and groups) and edges are relationships (group membership and permissions). Compute the transitive closure of group memberships to determine all groups each user belongs to, then for each camera, find the set of users who have access via direct permission or through any of their groups. Finally, intersect these sets across all cameras to find users with access to every camera.

Pro tip: Clarify assumptions upfront: whether permissions can be negative (deny rules), whether groups can contain users and groups, and if the graph is guaranteed acyclic. Also, mention that you'd use memoization or topological order to avoid redundant traversals, showing awareness of efficiency.

1. Parse and model the data

Separate the tuples into group memberships (subject is user/group, relationship is 'member_of', object is group) and permissions (subject is user/group, relationship is 'can_access', object is camera). Build adjacency lists for group membership and permission mappings.

2. Compute transitive group memberships

For each user, perform DFS/BFS over the group membership graph to find all groups they belong to (directly or indirectly). Since the graph is acyclic, you can also use topological sort and dynamic programming to compute this efficiently.

3. Determine user access per camera

For each camera, collect all users who have direct permission or belong to any group that has permission. Use a set to avoid duplicates.

4. Find intersection across cameras

Intersect the sets of users for all cameras. If the intersection is non-empty, return any user (or the single user if guaranteed). If empty, return null or indicate no such user.

5. Analyze complexity and edge cases

Discuss time and space complexity: O(U * (G + E)) for naive DFS, or O(U + G + E + C * U) with optimizations. Mention handling of empty camera list, users with no groups, and potential for multiple users (though problem states single).

Key Points to Mention

Graph representation: adjacency lists for group memberships and permissions.
Transitive closure via DFS/BFS or topological sort with memoization.
Set intersection to find users with access to all cameras.
Time complexity: O(U * (G + E) + C * U) where U=users, G=groups, E=membership edges, C=cameras; can optimize with bitsets.
Space complexity: O(G + E + U * C) for storing memberships and access sets.
Edge cases: no cameras, no users, cycles (though stated none), multiple users with access (return any or handle as per requirement).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.