Katkat
Back

Resolve user roles across account hierarchy

StripeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to navigate hierarchical structures (a tree of accounts) and perform efficient permission aggregation using set operations.

Problem Statement

You are working with a tree-like hierarchy of user accounts, where each account can have a 'parent' account. A user is assigned a specific role at a specific account node. Roles inherit permissions from the parent hierarchy: if a user has a role at account 'A', they implicitly possess that role for all descendant accounts of 'A'.

Given the account hierarchy as a list of (child_id, parent_id) pairs, a list of user roles (user_id, account_id, role), and a list of queries (user_id, target_account_id), determine the set of unique roles the user possesses at the target_account_id.

Function Signature

def get_effective_roles(hierarchy, user_roles, queries):

  • hierarchy: List of (child, parent) tuples. Root nodes have no parent.
  • user_roles: List of (user_id, account_id, role) tuples.
  • queries: List of (user_id, target_account_id) tuples.

Example

hierarchy = [('B', 'A'), ('C', 'B')]
user_roles = [('u1', 'A', 'admin'), ('u1', 'B', 'editor')]
queries = [('u1', 'C')]

# Output: {'admin', 'editor'}
# Explanation: 'u1' inherits 'admin' from 'A' (parent of 'B') and 'editor' from 'B' (parent of 'C').

Constraints

  • The hierarchy is a Directed Acyclic Graph (DAG) or a tree.
  • account_ids are strings; user_ids are strings.
  • Optimize for multiple queries against the same hierarchy structure.

Edge Cases

  • Users with no roles assigned.
  • Target account is the root or has no ancestors.
  • Cycles in hierarchy (assume invalid input for basic implementation, but consider robustness).

Hints

Hint 1

Represent the hierarchy as an adjacency list where each node points to its parent to facilitate upward traversal.

Hint 2

For each query, traverse from the target account up to the root, collecting all assigned roles for the user at each ancestor node.

Hint 3

Pre-process the user roles into a map of `user_id -> account_id -> set(roles)` to allow for O(1) role lookups during traversal.

Follow-up questions

  • How would you optimize the solution if there are millions of queries but the hierarchy and user roles change infrequently?
  • What changes if roles have an explicit 'override' mechanism (e.g., a role at a child account can revoke a role inherited from a parent)?
  • How would you handle a scenario where the hierarchy is not a tree, but a general DAG where an account can have multiple parents?