Model Hierarchical Permissions as Classes and Match Them with Breadth-First Search

Design a small set of classes that represent hierarchical permissions, then write the logic that decides whether a given permission is granted by searching the hierarchy breadth-first. After writing it, you may be asked to walk through the logic aloud instead of running test cases, so the code should be easy to explain. The report does not give the permission names or the exact hierarchy. Assume a structure like the one below, in which holding a permission grants everything beneath it: ```text admin orders orders.read orders.refund catalog catalog.read catalog.edit ``` A role that holds `orders` may perform `orders.refund` but not `catalog.edit`; a role that holds `admin` may perform everything. ### Clarifying Questions - Is the hierarchy a strict tree, or can one permission sit under several parents (for example, a `support` bundle that contains both `orders.read` and `catalog.read`)? Can a configuration mistake introduce a cycle? - Are permissions granted to users directly, or to roles that users hold, and can roles inherit from other roles? - Is there an explicit deny, and if so, does a deny on a child override an allow on its parent? - Should a check return only yes or no, or also the grant that allowed it, for auditing? - What should happen when a check names a permission that does not exist in the hierarchy? ### Part 1 — Model the permission hierarchy Define the classes for permissions, their parent-child relationships, and the holders of grants (users or roles), along with how the hierarchy is built and validated. ```hint Nodes, edges and grants Decide which object is a node, which relationship is an edge, and where grants live, so that the search in Part 2 starts from a well-defined set of nodes. ``` #### What This Part Should Cover - Classes with clear responsibilities for permissions, the hierarchy and grant holders - Lookup of a permission by name, and validation while the hierarchy is built - How the model represents a permission with more than one parent ### Part 2 — Match a requested permission breadth-first Implement `is_granted(holder, permission_name)`: return whether the holder's grants imply the requested permission, using breadth-first search over the hierarchy. ```hint Direction of the search The search can begin at the holder's grants or at the requested permission. Decide which end to start from, which edges to follow, and what stops the search from visiting the same permission twice. ``` #### What This Part Should Cover - A correct breadth-first search with a visited set, and its result for unknown permission names - The time and space cost of one check, and how the choice of starting point affects it - A walkthrough of the logic on the example hierarchy ### What a Strong Answer Covers - Clarifies tree versus multi-parent hierarchy, roles, deny rules and unknown names before coding - A small, readable class design in which the search is separate from the data model - A breadth-first search that terminates on shared children and cycles, and fails closed - Complexity analysis and a plan for making repeated checks cheap - Test cases covering direct grants, inherited grants, missing grants and unknown names ### Follow-up Questions - Checks run on every request. How would you make them fast without searching each time, and keep the result correct when the hierarchy changes? - Add explicit deny rules. How does the search change, and which wins when an allow and a deny both apply? - Why breadth-first rather than depth-first here, and when would the difference matter? - The hierarchy is loaded from configuration and might contain a cycle. How do you detect and report it at load time?