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 Onsite 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.

Hierarchical Access Control for an Advertising Platform

Quick Overview

This question tests practical application of graph traversal and access control system design using a directed acyclic group hierarchy. It evaluates a candidate's ability to model inheritance-based permissions, choose appropriate data structures for efficient ancestor lookups, and handle grant/revoke semantics under read-heavy workloads — core competencies in coding and algorithms interviews for roles requiring systems thinking.

Hierarchical Access Control for an Advertising Platform

Company: Pinterest

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design an access-control system for an advertising platform. Advertisers are organized into a hierarchy of **groups**. A group may contain other groups (sub-groups) and may contain individual advertisers, forming a tree (or forest) of groups with advertisers at the leaves. The same advertiser may belong to more than one group, and the same group may be nested under more than one parent group. You must implement the following operations: - `grant_access(advertiser, group)` — grant the given advertiser access to the given group. After this call, the advertiser is considered to have access to that group and to **every group transitively reachable below it** (all of its descendant sub-groups). - `revoke_access(advertiser, group)` — remove a previously granted access for the given advertiser on the given group. This only removes a grant that was made directly on `group`; it does not remove grants made on ancestor groups (those may still confer access through inheritance). - `check_access(advertiser, group)` — return `true` if the advertiser can access the given group, and `false` otherwise. An advertiser can access `group` if it has been granted access either to `group` itself or to any **ancestor** group that contains `group` (directly or transitively). Access is inherited downward through the group hierarchy. The group hierarchy itself is provided up front. You may design whatever data structures and constructor / setup methods you need to represent the hierarchy (for example, a method to register that one group is a child of another). Assume advertiser identifiers and group identifiers are strings. ### Constraints & Assumptions - Let $G$ be the number of groups, $E$ the number of parent-child edges between groups, and $A$ the number of distinct advertisers. - The group hierarchy is a DAG: a group can have multiple parents, but there are **no cycles**. - `grant_access`, `revoke_access`, and `check_access` may be interleaved in any order after the hierarchy is built. - `check_access` should be efficient; a single call should not need to re-scan the entire hierarchy from scratch. Aim for a complexity bounded by the number of ancestor groups of the queried group rather than by the total number of grants. - Granting access to a group the advertiser was already granted is idempotent; revoking a grant that does not exist is a no-op. - A group may have hundreds of ancestors in pathological cases; queries far outnumber writes. ### Input / Output Format Implement the class so that a driver can: 1. Build the hierarchy (e.g. by repeatedly declaring that group `X` is a child of group `Y`). 2. Call `grant_access(advertiser, group)` and `revoke_access(advertiser, group)` (no return value). 3. Call `check_access(advertiser, group)` and receive a boolean. Example sequence: ``` hierarchy: root -> {regionA, regionB}; regionA -> {teamX, teamY} grant_access("alice", "regionA") check_access("alice", "teamX") -> true (teamX is a descendant of regionA) check_access("alice", "regionB") -> false (regionB is not under regionA) check_access("alice", "root") -> false (grant does not propagate upward) revoke_access("alice", "regionA") check_access("alice", "teamX") -> false ```

Quick Answer: This question tests practical application of graph traversal and access control system design using a directed acyclic group hierarchy. It evaluates a candidate's ability to model inheritance-based permissions, choose appropriate data structures for efficient ancestor lookups, and handle grant/revoke semantics under read-heavy workloads — core competencies in coding and algorithms interviews for roles requiring systems thinking.

You are building an access-control system for an advertising platform. Advertisers are organized into a hierarchy of **groups**. A group may contain sub-groups and individual advertisers, forming a directed acyclic graph (DAG) of groups: a group can have multiple parents, but there are no cycles. Access granted on a group is inherited **downward** by every group transitively reachable below it. Implement a driver `solution(edges, operations)`: - `edges` is a list of `[parent, child]` pairs declaring the group hierarchy. Group identifiers are strings. - `operations` is a list of operations applied after the hierarchy is built. Each operation is one of: - `["grant_access", advertiser, group]` — grant `advertiser` access to `group` and to every descendant of `group`. Idempotent. - `["revoke_access", advertiser, group]` — remove a grant made **directly** on `group` for `advertiser`. Does not affect grants on ancestor groups. Revoking a grant that does not exist is a no-op. - `["check_access", advertiser, group]` — return `true` if `advertiser` can access `group`, i.e. it was granted access to `group` itself or to any ancestor of `group` (directly or transitively). Access propagates downward only, never upward. Return a list of booleans, one per `check_access` operation, in the order they appear. **Example** ``` edges = [["root","regionA"],["root","regionB"],["regionA","teamX"],["regionA","teamY"]] operations = [ ["grant_access","alice","regionA"], ["check_access","alice","teamX"], # true (teamX is a descendant of regionA) ["check_access","alice","regionB"], # false (regionB is not under regionA) ["check_access","alice","root"], # false (grant does not propagate upward) ["revoke_access","alice","regionA"], ["check_access","alice","teamX"] # false (grant removed) ] # returns [true, false, false, false] ```

Constraints

Group and advertiser identifiers are strings.
The group hierarchy is a DAG: a group may have multiple parents, but there are no cycles.
grant_access is idempotent; revoke_access on a non-existent grant is a no-op.
revoke_access only removes a grant made directly on the named group; inherited access via ancestors is unaffected.
Access is inherited downward only — a grant on a group never confers access to its ancestors.
Queries (check_access) far outnumber writes; a group may have hundreds of ancestors.

Examples

Input: ([['root','regionA'],['root','regionB'],['regionA','teamX'],['regionA','teamY']], [['grant_access','alice','regionA'],['check_access','alice','teamX'],['check_access','alice','regionB'],['check_access','alice','root'],['revoke_access','alice','regionA'],['check_access','alice','teamX']])

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

Explanation: alice is granted regionA. teamX is a descendant of regionA -> true. regionB is not under regionA -> false. root is an ancestor, grants don't propagate upward -> false. After revoking regionA, teamX is no longer reachable -> false.

Input: ([], [['check_access','bob','x']])

Expected Output: [False]

Explanation: Empty hierarchy and no grants: bob has no access to x.

Input: ([['a','b'],['b','c'],['x','c']], [['grant_access','u','a'],['check_access','u','c'],['grant_access','u','a'],['check_access','u','c'],['revoke_access','u','a'],['check_access','u','c'],['grant_access','u','x'],['check_access','u','c']])

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

Explanation: c has two ancestor paths (via a->b and via x). Grant on a reaches c -> true; the second grant on a is idempotent -> still true. After revoking a, c is no longer reachable -> false. Granting x (the other parent of c) restores access -> true.

Input: ([['g','h']], [['revoke_access','z','g'],['check_access','z','g'],['grant_access','z','g'],['check_access','z','g'],['check_access','z','h']])

Expected Output: [False, True, True]

Explanation: Revoking a non-existent grant is a no-op, so the first check is false. After granting g, z can access g and its descendant h.

Input: ([['root','a'],['a','b'],['b','c']], [['grant_access','p','b'],['check_access','p','c'],['check_access','p','root'],['check_access','p','a']])

Expected Output: [True, False, False]

Explanation: Grant on b reaches descendant c -> true, but does not reach ancestors root or a -> false. Confirms downward-only inheritance through a multi-level chain.

Hints

Store grants as advertiser -> set of directly-granted groups. Do not eagerly expand grants to all descendants; that makes revoke and large sub-trees expensive.
For check_access, walk UPWARD from the queried group through its ancestors (the group itself first) and return true the moment you hit a group that was directly granted to that advertiser.
Because the hierarchy is a DAG (multiple parents), use a visited set during the upward walk so you don't revisit a shared ancestor.
revoke_access must only remove the direct grant on the named group — a simple set.discard — never touch ancestor grants.

Last updated: Jun 24, 2026

Loading coding console...

Quick Overview

Hierarchical Access Control for an Advertising Platform

Company: Pinterest

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Constraints

Group and advertiser identifiers are strings.
The group hierarchy is a DAG: a group may have multiple parents, but there are no cycles.
grant_access is idempotent; revoke_access on a non-existent grant is a no-op.
revoke_access only removes a grant made directly on the named group; inherited access via ancestors is unaffected.
Access is inherited downward only — a grant on a group never confers access to its ancestors.
Queries (check_access) far outnumber writes; a group may have hundreds of ancestors.

Examples

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

Input: ([], [['check_access','bob','x']])

Expected Output: [False]

Explanation: Empty hierarchy and no grants: bob has no access to x.

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

Input: ([['g','h']], [['revoke_access','z','g'],['check_access','z','g'],['grant_access','z','g'],['check_access','z','g'],['check_access','z','h']])

Expected Output: [False, True, True]

Explanation: Revoking a non-existent grant is a no-op, so the first check is false. After granting g, z can access g and its descendant h.

Input: ([['root','a'],['a','b'],['b','c']], [['grant_access','p','b'],['check_access','p','c'],['check_access','p','root'],['check_access','p','a']])

Expected Output: [True, False, False]

Explanation: Grant on b reaches descendant c -> true, but does not reach ancestors root or a -> false. Confirms downward-only inheritance through a multi-level chain.

Hints

Store grants as advertiser -> set of directly-granted groups. Do not eagerly expand grants to all descendants; that makes revoke and large sub-trees expensive.
For check_access, walk UPWARD from the queried group through its ancestors (the group itself first) and return true the moment you hit a group that was directly granted to that advertiser.
Because the hierarchy is a DAG (multiple parents), use a visited set during the upward walk so you don't revisit a shared ancestor.
revoke_access must only remove the direct grant on the named group — a simple set.discard — never touch ancestor grants.

Last updated: Jun 24, 2026

Loading coding console...