Compute Effective Letter Permissions in a DAG
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Compute Effective Letter Permissions in a DAG
Each node in a directed acyclic graph has two direct permission sets: letters it allows and letters it disallows. Allowed letters propagate from every ancestor to every descendant.
This practice version uses the reported variant in which disallow settings do **not** propagate. For a node, first union the direct allow sets on that node and all of its ancestors, then remove only that node's own direct disallow set. A node's direct disallow therefore affects its own result but not any descendant's result.
Implement:
```text
effectiveAllowedLetters(nodes, edges) -> string[][]
```
Each record in `nodes` is `[name, allowLetters, disallowLetters]`. Return one `[name, effectiveLetters]` record for every node, sorted by `name` in ascending lexicographic order. `effectiveLetters` must contain its distinct letters in alphabetical order with no separator; use the empty string when no letter is effective.
## Constraints
- `1 <= nodes.length <= 100,000`
- Every node name is unique and contains 1 to 100 lowercase English letters, digits, or underscores.
- Each permission string contains distinct lowercase English letters in any order.
- `0 <= edges.length <= 200,000`
- Every edge is `[parent, child]`, both names occur in `nodes`, and edges are unique.
- The complete directed graph is acyclic; a node may have more than one parent.
## Example 1
```text
Input:
nodes = [
["a", "ab", ""],
["b", "c", "b"],
["c", "", ""]
]
edges = [["a", "b"], ["b", "c"]]
Output:
[
["a", "ab"],
["b", "ac"],
["c", "abc"]
]
```
Node `b` removes `b` from its own result. That disallow does not propagate, so node `c` still inherits `b` from node `a`.
## Example 2
```text
Input:
nodes = [
["root", "az", ""],
["left", "b", "z"],
["right", "c", ""],
["leaf", "d", "a"]
]
edges = [
["root", "left"],
["root", "right"],
["left", "leaf"],
["right", "leaf"]
]
Output:
[
["leaf", "bcdz"],
["left", "ab"],
["right", "acz"],
["root", "az"]
]
```
The leaf combines allowed letters from both parent paths, removes its own `a`, and retains `z` because the disallow declared on `left` is local to `left`.
Quick Answer: Compute effective letter permissions for every node in a directed acyclic graph where allowed letters propagate through all ancestors but disallow settings remain local. The task requires deterministic alphabetical permission strings and lexical node ordering while handling multiple parents and transitive inheritance.
Each node in a directed acyclic graph has a direct allow string and a direct disallow string. Allowed letters propagate from every ancestor to every descendant. Disallow settings do not propagate: for each node, union the direct allow letters on that node and all its ancestors, then remove only that node's own direct disallow letters. Each node record is [name, allowLetters, disallowLetters], and each edge is [parent, child]. Return [name, effectiveLetters] for every node in ascending lexicographic name order. Each effectiveLetters string contains distinct letters alphabetically with no separator, or the empty string.
Constraints
- 1 <= nodes.length <= 100,000
- Every node name is unique and has 1 to 100 lowercase English letters, digits, or underscores.
- Each permission string contains distinct lowercase English letters.
- 0 <= edges.length <= 200,000
- Every edge names two existing nodes, edges are unique, and the complete graph is acyclic.
Examples
Input: ([['a', 'ab', ''], ['b', 'c', 'b'], ['c', '', '']], [['a', 'b'], ['b', 'c']])
Expected Output: [['a', 'ab'], ['b', 'ac'], ['c', 'abc']]
Explanation: A direct disallow on b changes b only; c still inherits b from a.
Input: ([['root', 'az', ''], ['left', 'b', 'z'], ['right', 'c', ''], ['leaf', 'd', 'a']], [['root', 'left'], ['root', 'right'], ['left', 'leaf'], ['right', 'leaf']])
Expected Output: [['leaf', 'bcdz'], ['left', 'ab'], ['right', 'acz'], ['root', 'az']]
Explanation: The leaf unions both parent paths, removes only its own a, and output rows are name-sorted.
Hints
- Topological order lets a node receive all parent contributions before it propagates to children.
- Keep the accumulated allow mask separate from the locally filtered effective mask.