Compute effective permissions on DAG and prune tree
Problem A: Effective Allow/Disallow Letters on a DAG
You are given a directed acyclic graph (DAG) with n nodes labeled 0 to n-1. Each node u contains two (possibly empty) sets of lowercase letters:
allow[u]— letters explicitly allowed atudeny[u]— letters explicitly disallowed atu
Transitivity Rule (Inheritance along Edges): If there is a directed edge u -> v, then v inherits all rules from u (and from all of u’s ancestors).
Define for each node v:
A(v): union ofallow[x]over all ancestorsxofv(includingvitself)D(v): union ofdeny[x]over all ancestorsxofv(includingvitself)effective(v) = A(v) \ D(v)(denies override allows)
Task: For every node v, output its effective(v) set.
Notes/Assumptions:
- The graph is guaranteed to be a DAG.
- Letters are from
'a'..'z'. - If a letter appears in both allow and deny along the ancestry, it is not effective (i.e.,
D(v)overridesA(v)).
Problem B: Tree Pruning / Depth Constraints (3 Related Tasks)
You are given a rooted tree with n nodes labeled 0 to n-1, rooted at node 0. The depth of the root is 0.
Deleting a node removes that node and its entire subtree.
Task B1
You are given a list/set of nodes to delete. After performing all deletions, the remaining nodes form a forest.
Output: The maximum depth (in the original tree’s depth numbering) among all remaining nodes. If nothing remains, output -1.
Task B2
Given an an integer N, delete the minimum number of nodes (each deletion removes a whole subtree) so that the maximum remaining depth is at most N.
Output: The minimum number of deleted nodes.
Task B3 (Bonus)
Same as Task B2, but if multiple deletion plans achieve the minimum number of deletions, choose one that maximizes the sum of depths of the deleted nodes.
Output:
- The minimum number of deleted nodes, and
- The maximum possible sum of depths of deleted nodes among minimum-deletion solutions.
Constraints (You may assume for all tasks):
1 <= n <= 2e5- Tree given as parent array or edge list.
- DAG given as edge list.
- Aim for near-linear or
O((n+m) * 26)/O((n+m) * word_bitset)type solutions.
AI interview prep
Core dilemma
Efficiently propagating and resolving complex state (sets for Problem A, depth constraints for Problem B) across graph structures (DAGs and trees) to achieve optimal outcomes under strict performance constraints, often requiring dynamic programming or greedy strategies.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Compute effective permissions on DAG and prune tree
Problem A: Effective Allow/Disallow Letters on a DAG
You are given a directed acyclic graph (DAG) with n nodes labeled 0 to n-1. Each node u contains two (possibly empty) sets of lowercase letters:
allow[u]— letters explicitly allowed atudeny[u]— letters explicitly disallowed atu
Transitivity Rule (Inheritance along Edges): If there is a directed edge u -> v, then v inherits all rules from u (and from all of u’s ancestors).
Define for each node v:
A(v): union ofallow[x]over all ancestorsxofv(includingvitself)D(v): union ofdeny[x]over all ancestorsxofv(includingvitself)effective(v) = A(v) \ D(v)(denies override allows)
Task: For every node v, output its effective(v) set.
Notes/Assumptions:
- The graph is guaranteed to be a DAG.
- Letters are from
'a'..'z'. - If a letter appears in both allow and deny along the ancestry, it is not effective (i.e.,
D(v)overridesA(v)).
Problem B: Tree Pruning / Depth Constraints (3 Related Tasks)
You are given a rooted tree with n nodes labeled 0 to n-1, rooted at node 0. The depth of the root is 0.
Deleting a node removes that node and its entire subtree.
Task B1
You are given a list/set of nodes to delete. After performing all deletions, the remaining nodes form a forest.
Output: The maximum depth (in the original tree’s depth numbering) among all remaining nodes. If nothing remains, output -1.
Task B2
Given an an integer N, delete the minimum number of nodes (each deletion removes a whole subtree) so that the maximum remaining depth is at most N.
Output: The minimum number of deleted nodes.
Task B3 (Bonus)
Same as Task B2, but if multiple deletion plans achieve the minimum number of deletions, choose one that maximizes the sum of depths of the deleted nodes.
Output:
- The minimum number of deleted nodes, and
- The maximum possible sum of depths of deleted nodes among minimum-deletion solutions.
Constraints (You may assume for all tasks):
1 <= n <= 2e5- Tree given as parent array or edge list.
- DAG given as edge list.
- Aim for near-linear or
O((n+m) * 26)/O((n+m) * word_bitset)type solutions.