How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Pinterest.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Pinterest during technical interviews.

Design Hierarchical Permission Checks | Pinterest Coding Question

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.

Input: ({'W': None, 'X': 'W', 'Y': 'W', 'Z': 'X'}, [('grant', 'a', 'W'), ('grant', 'b', 'X'), ('check', 'a', 'Y'), ('check', 'b', 'Z'), ('check', 'b', 'Y'), ('revoke', 'b', 'X'), ('check', 'b', 'Z')])

Expected Output: [True, True, False, False]

Explanation: Advertiser 'a' inherits from the root. Advertiser 'b' can access 'Z' through 'X' but not sibling 'Y'. After revoking 'X', 'b' loses access to 'Z'.

Input: ({'Only': None}, [('check', 'adv', 'Only'), ('revoke', 'adv', 'Only'), ('grant', 'adv', 'Only'), ('check', 'adv', 'Only')])

Expected Output: [False, True]

Explanation: In a single-node tree, a check is false before any grant. Revoking a non-existent direct permission does nothing. After granting on the root, the check becomes true.

Input: ({'Root': None}, [])

Expected Output: []

Explanation: There are no operations, so there are no check results to return.

Hints

Store only direct permissions, not all inherited permissions. Expanding grants to every descendant would make updates too expensive.
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.

Quick Overview

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