How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Snowflake.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snowflake during technical interviews.

Compute effective permissions on DAG and prune tree

Q: Compute effective permissions on DAG and prune tree

This set of problems evaluates proficiency in graph and tree algorithms, specifically transitive state propagation and conflict resolution on a DAG (effective allow/deny sets) and subtree deletion and selection under depth constraints in rooted trees.

Problem A — Effective allow/disallow letters on a DAG

You are given a directed acyclic graph (DAG) with n nodes labeled 0..n-1.

Each node u contains two (possibly empty) sets of lowercase letters:

allow[u] — letters explicitly allowed at u
deny[u] — letters explicitly disallowed at u

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 of allow[x] over all ancestors x of v (including v itself)
D(v) : union of deny[x] over all ancestors x of v (including v itself)
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.

You are given a rooted tree with n nodes labeled 0..n-1, rooted at node 0. 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 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.

Problem A — Effective allow/disallow letters on a DAG

You are given a directed acyclic graph (DAG) with n nodes labeled 0..n-1.

Each node u contains two (possibly empty) sets of lowercase letters:

allow[u] — letters explicitly allowed at u
deny[u] — letters explicitly disallowed at u

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 of allow[x] over all ancestors x of v (including v itself)
D(v) : union of deny[x] over all ancestors x of v (including v itself)
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.

You are given a rooted tree with n nodes labeled 0..n-1, rooted at node 0. 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 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.

Compute effective permissions on DAG and prune tree

Quick Overview

Problem A — Effective allow/disallow letters on a DAG

Task B1

Task B2

Task B3 (bonus)

Comments (0)

Compute effective permissions on DAG and prune tree

Quick Overview

Problem A — Effective allow/disallow letters on a DAG

Task B1

Task B2

Task B3 (bonus)

Comments (0)

Compute effective permissions on DAG and prune tree

Quick Overview