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
```
Overview: 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.
Read the full Figma Software Engineer interview experience this question came from
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.