Katkat
Back

Hierarchical Access Control for an Advertising Platform

PinterestMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests graph traversal algorithms and efficient membership checking within a directed acyclic graph (DAG) representing hierarchical organizational permissions.

Problem Statement

You are building an authorization engine for an advertising platform where permissions are inherited hierarchically. Groups are organized in a Directed Acyclic Graph (DAG) where a child group inherits all permissions of its parent group.

Given a list of group relationships relationships (where [child, parent] means child inherits from parent) and a list of grants (where [group_id, permission] means the group is explicitly granted that permission), implement a class AccessManager that determines if a specific group possesses a required permission.

Interface

class AccessManager:
    def __init__(self, relationships, grants):
        # relationships: List[List[str]]
        # grants: List[List[str]]
        pass

    def has_permission(self, group_id, permission):
        # Returns True if group_id has permission, else False
        pass

Constraints

  • relationships: up to 10,000 pairs.
  • grants: up to 5,000 pairs.
  • The hierarchy is guaranteed to be a DAG.

Examples

Example 1:

  • relationships: [['admin', 'user'], ['manager', 'user']]
  • grants: [['user', 'view_ads']]
  • has_permission('admin', 'view_ads') -> True (Admin inherits from User)
  • has_permission('manager', 'edit_campaign') -> False

Edge Cases

  • Cycles: The input is guaranteed to be a DAG, but consider disconnected components.
  • Indirect inheritance: A group may be multiple levels deep in the hierarchy.

Hints

Hint 1

Represent the hierarchy as an adjacency list where each node points to its parents.

Hint 2

For each group, you can precompute all reachable ancestor groups using Breadth-First Search (BFS) or Depth-First Search (DFS).

Hint 3

Store the permissions in a hash map where each group maps to a set of its direct and inherited permissions for O(1) lookup time.

Follow-up questions

  • How would you optimize the `__init__` method if the number of relationships changes frequently but `has_permission` calls remain high?
  • If the system experiences high write volume for `grants` but the hierarchy remains static, how would you change your data structure?
  • How would you detect if a new relationship would introduce a cycle in the graph?