Check Graph Reachability For File Permissions
Company: Figma
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a graph representing simplified file permission inheritance. In part 1, the graph is directed and may contain cycles. Return whether there is a path from `source` to `destination`. In part 2, treat relationships as bidirectional and answer the same query. In part 3, support a set of blocked edges that cannot be used during traversal.
Function signature:
```python
def has_path_directed(n: int, edges: list[tuple[int, int]], source: int, destination: int) -> bool:
pass
def has_path_undirected(n: int, edges: list[tuple[int, int]], source: int, destination: int) -> bool:
pass
def has_path_with_blocked_edges(n: int, edges: list[tuple[int, int]], blocked: set[tuple[int, int]], source: int, destination: int) -> bool:
pass
```
Constraints:
- `0 <= source, destination < n`.
- The graph may contain cycles.
- Use BFS or DFS with a visited set.
- For blocked edges in an undirected traversal, clarify whether both directions are blocked.
Examples:
```text
n = 3, edges = [(0,1),(1,2)], source = 0, destination = 2
Directed output: True
```
```text
n = 3, edges = [(1,0)], source = 0, destination = 1
Directed output: False; undirected output: True
```
Quick Answer: Practice graph reachability for simplified file-permission inheritance under directed, undirected, and blocked-edge variants. The prompt is useful for reviewing DFS or BFS, visited sets, cycle handling, and clarifying traversal semantics.
Return whether a path exists between two nodes under one of three modes: directed, undirected, or directed with blocked edges.
Constraints
- Nodes are labeled 0..n-1.
- The graph may contain cycles.
Examples
Input: (3, [(0,1),(1,2)], 0, 2, 'directed')
Expected Output: True
Input: (3, [(1,0)], 0, 1, 'directed')
Expected Output: False
Hints
- Use a visited set.
- Clarify whether blocked edges apply to one or both directions.