Design Hierarchical Permission Checks
Company: Pinterest
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a hierarchy of groups represented as a tree, for example `World -> Country -> City`. Each advertiser can be granted access at any group node. A permission granted at a higher-level node applies to all of its descendants.
Design a class that supports these operations:
- `grant_access(advertiser_id, group_id)`: add a direct permission for the advertiser on the given group.
- `revoke_access(advertiser_id, group_id)`: remove the advertiser's direct permission on the given group.
- `check_access(advertiser_id, group_id)`: return `true` if the advertiser has access to the group, either because the advertiser was granted permission directly on that node or on any ancestor of that node; otherwise return `false`.
Assume the group tree structure is already known and each node can access its parent.
Follow-up: How would you implement this so that `grant_access` and `revoke_access` are `O(1)`, while `check_access` is `O(depth of the tree)`?
Quick Answer: This question evaluates understanding of hierarchical access control, tree data structures, and permission inheritance, testing competencies in data modeling and algorithmic reasoning.
You are given a hierarchy of groups represented as a tree. Each group has a parent, and the root group's parent is None. An advertiser can be granted direct access to any group. That access automatically applies to all descendants of the granted group.
Process a list of operations in order:
- ('grant', advertiser_id, group_id): add a direct permission for the advertiser on that group
- ('revoke', advertiser_id, group_id): remove only the direct permission on that group
- ('check', advertiser_id, group_id): return True if the advertiser has access to that group either directly or through any ancestor, otherwise False
Return a list of boolean results for all check operations, in the order they appear.
The intended design is to support O(1) average-time grant and revoke, and O(depth of tree) check.
Constraints
- 1 <= number of groups <= 10^5
- 0 <= number of operations <= 10^5
- The parent mapping forms a valid tree with exactly one root
- Every group_id used in operations exists in the parent mapping
- grant_access and revoke_access should be O(1) average time; check_access should be O(depth of the tree)
Examples
Input: ({'World': None, 'US': 'World', 'NYC': 'US', 'SF': 'US', 'CA': 'World'}, [('grant', 'adv1', 'US'), ('check', 'adv1', 'NYC'), ('check', 'adv1', 'US'), ('check', 'adv1', 'CA')])