How should I practice Directed Graph Reachability Queries?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen and onsite interview problems in FastPrep.

Is Directed Graph Reachability Queries associated with Google?

FastPrep tags this as a Google phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

Directed Graph Reachability Queries

Google● HardFULLTIMENEW GRADPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

You are given a directed graph with n vertices numbered from 0 to n - 1. Each pair [from, to] in edges adds a directed edge from from to to.

For every pair [source, target] in queries, determine whether a directed path exists from source to target.

A vertex is reachable from itself through a path of length zero. Duplicate edges do not change reachability. Return one Boolean answer per query in the same order as queries. You do not need to reconstruct any path.

Function

answerReachabilityQueries(n: int, edges: int[][], queries: int[][]) → boolean[]

Examples

Example 1

n = 4edges = [[0,1],[1,2],[2,3]]queries = [[0,3],[3,0],[1,1],[0,2]]return = [true,false,true,true]

The path 0 -> 1 -> 2 -> 3 makes 3 reachable from 0. There is no path from 3 back to 0. Vertex 1 reaches itself, and 0 reaches 2.

Example 2

n = 5edges = [[0,1],[1,2],[2,0],[2,3],[2,3]]queries = [[3,0],[0,3],[4,4],[4,0],[2,1]]return = [false,true,true,false,true]

Vertices 0, 1, and 2 form a directed cycle, and that cycle reaches 3. Vertex 4 is isolated but still reaches itself through a length-zero path. Repeating the edge 2 -> 3 has no effect.

Example 3

n = 6edges = [[0,1],[0,2],[1,3],[2,3],[4,5]]queries = [[0,3],[1,2],[4,5],[5,4],[3,3]]return = [true,false,true,false,true]

Vertex 0 reaches 3 through either branch. The branches do not reach one another. The separate edge 4 -> 5 works only in its listed direction, and 3 reaches itself.

Constraints

1 <= n <= 500.
0 <= edges.length <= 100000.
1 <= queries.length <= 100000.
Every entry in edges and queries contains exactly two valid vertex indices.
The graph may contain cycles, self-loops, duplicate edges, and disconnected vertices.