Quick Overview

This question evaluates understanding of hierarchical access control, tree data structures, and permission inheritance, testing competencies in data modeling and algorithmic reasoning.

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')])

Expected Output: [True, True, False]

Explanation: A grant on 'US' applies to 'NYC' and 'SF', and also counts for 'US' itself, but it does not apply to sibling subtree 'CA'.

Input: ({'Root': None, 'A': 'Root', 'B': 'A', 'C': 'B'}, [('grant', 'x', 'A'), ('grant', 'x', 'C'), ('check', 'x', 'C'), ('revoke', 'x', 'A'), ('check', 'x', 'C'), ('check', 'x', 'B')])

Expected Output: [True, True, False]

Explanation: Before revocation, 'C' is accessible through both 'A' and a direct grant. After revoking 'A', 'C' is still accessible because it still has a direct grant, but 'B' is no longer accessible.

Hints

  1. Store only direct permissions, not all inherited permissions. Expanding grants to every descendant would make updates too expensive.
  2. For a check, start from the target group and walk upward through parent pointers until you either find a direct grant for that advertiser or reach the root.

Loading coding console...