Snowflake·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Snowflake software engineer interview with a graph traversal / privilege inheritance problem. Pretty clean problem statement but the transitive inheritance part is where things get interesting.

Questions Asked (1)

Given n roles each with directly assigned privileges, and a list of parent-child grant relationships forming a DAG, compute the complete set of privileges for every role after applying all transitive inheritance. Return deduplicated results per role.

Algorithms & Data StructuresSystem Design

Author's notes

The base case is straightforward, just union the direct privileges.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the roles and inheritance as a directed acyclic graph (DAG) where each node represents a role and edges represent parent-child grant relationships. Use topological sorting to process roles in dependency order, computing each role's privilege set as the union of its directly assigned privileges and the privilege sets of its parents. Deduplicate privileges using a set data structure for each role.

Pro tip: Mention that you can optimize memory by using bitsets for privilege sets if the number of distinct privileges is small, and that handling cycles is unnecessary because the input is guaranteed to be a DAG. Also, clarify whether the inheritance is from parent to child (child inherits parent's privileges) or vice versa, as this affects the direction of edges.

1. Clarify the problem and assumptions

Confirm the direction of inheritance (e.g., child roles inherit privileges from parent roles) and that the graph is a DAG. Ask about constraints like number of roles, privileges, and edges to choose the right algorithm.

2. Model the graph and initialize privilege sets

Build an adjacency list for the DAG and initialize each role's privilege set with its directly assigned privileges. Use a set (or bitset) to ensure deduplication.

3. Topologically sort the roles

Perform a topological sort on the DAG to determine a linear order where each role appears after all its parents. This ensures that when processing a role, all its parents' privileges are already computed.

4. Compute inherited privileges in topological order

Iterate through the sorted roles, and for each role, union its privilege set with the privilege sets of all its parents. This propagates privileges transitively.

5. Return deduplicated privilege sets

After processing all roles, return the privilege set for each role, ensuring no duplicates. Optionally, convert sets to sorted lists for consistent output.

Key Points to Mention

Topological sorting to handle dependencies and ensure transitive inheritance is applied correctly.
Using sets (or bitsets) for efficient union operations and automatic deduplication.
Time complexity: O(V + E + total privilege unions), where V is number of roles and E is number of edges; space complexity: O(V * P) where P is average privileges per role.
Handling of multiple parents: union all parents' privilege sets.
Potential optimizations: bitsets for compact storage and fast bitwise OR, or memoization if the graph is large.
Edge cases: roles with no parents (only direct privileges), roles with no direct privileges, and disconnected components in the DAG.

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