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.
Community answers
Answer by troyxd
function solution(input) {
// the grader passes one array, so unpack its values first
const [n, edges, source, destination, mode = 'directed', blocked = []] = input;
const graph = new Map();
const visited = new Set();
for (const [from, to] of edges) {
if (!graph.has(from)) graph.set(from, []);
graph.get(from).push(to);
if (mode === 'undirected') {
// [1, 0] also allows 0 -> 1, so save the reverse connection
if (!graph.has(to)) graph.set(to, []);
graph.get(to).push(from);
}
}
const blockedEdges = new Set();
for (const [from, to] of blocked) {
// separate [1, 2] arrays don't match, but identical '1,2' strings do
blockedEdges.add(from + ',' + to);
// an undirected edge is one connection, so neither side can cross it
if (mode === 'undirected') {
blockedEdges.add(to + ',' + from);
}
}
// keep DFS inside solution so it needs no external helper functions
function dfs(node) {
// mark before exploring so a cycle cannot bring us back again
visited.add(node);
// a node with no outgoing connections has nothing left to explore
const neighbors = graph.get(node) || [];
for (const next of neighbors) {
// skip this connection; another neighbor may still reach the destination
if (blockedEdges.has(node + ',' + next)) continue;
if (!visited.has(next)) dfs(next);
}
}
dfs(source);
// reaching the destination through any allowed route is enough
return visited.has(destination);
}