FastPrepGenerate a Connected Graph and Find a Shortest Path
Problems/Generate a Connected Graph and Find a Shortest Path

Generate a Connected Graph and Find a Shortest Path

The Walt Disney Company logoThe Walt Disney Company● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report asks to generate a random connected undirected graph from N, then print a shortest path between two vertices. This practice retains both graph generation and path search. It supplies a seeded pseudorandom generator, a connecting-parent plus extra-edge construction, exact draw order, lexicographic path ties and an adjacency-plus-path return value. About 80% of the reported task is represented; these repeatability and output details are authored practice, not reported original requirements.

Generate a connected, undirected, unweighted graph with n nodes numbered 0 through n-1, then find a shortest path from source to target. The graph must be generated from the supplied seed; it is not a graph supplied as input.

For this exercise, use this exact pseudorandom construction so a run is reproducible:

  1. Set state=seed. Each random draw replaces state with (1103515245*state+12345) mod 2147483648 and returns that new state. Compute the multiplication exactly.
  2. For v=1,2,...,n-1, draw once, set u=draw mod v, and add the undirected edge u-v. These edges connect each new node to an earlier node.
  3. Visit every pair (u,v) with u<v in increasing u, then increasing v. Skip an edge already present without drawing. Otherwise draw once and add the edge exactly when draw mod 4 equals zero.

For this exercise, return an array with n+1 rows. Rows 0 through n-1 are the generated adjacency lists, each sorted by increasing neighbor ID. The final row is the lexicographically smallest shortest path from source to target, including both endpoints. Equal endpoints give a one-node path. There are no self-loops or duplicate edges.

The seed, generator, extra-edge rule, path tie rule and returned representation are practice choices omitted by the report. A caller can vary the seed for different runs; the same seed reproduces the same graph and different seeds may still produce the same graph. This is not a uniform sampler over all connected graphs.

Function

randomGraphPath(n: int, source: int, target: int, seed: int) → int[][]

Examples

Example 1

n = 4source = 0target = 3seed = 0return = [[1,2,3],[0],[0,3],[0,2],[0,3]]

The parent-stage draws are 12345, 1406932606 and 654583775, giving edges 0-1, 0-2 and 2-3. Of the remaining pairs, only 0-3 is added. The adjacency rows are [1,2,3], [0], [0,3] and [0,2]. The added edge gives shortest path [0,3].

Example 2

n = 3source = 1target = 2seed = 0return = [[1,2],[0],[0],[1,0,2]]

The parent stage creates edges 0-1 and 0-2, and the remaining pair 1-2 is not added. The adjacency rows are [1,2], [0] and [0]. From node 1 to node 2, return path [1,0,2] after those rows.

Constraints

  • 1 <= n <= 100
  • 0 <= source < n and 0 <= target < n
  • 0 <= seed <= 2147483647

More The Walt Disney Company problems

  • Find All Paths for a Name in a File SystemPHONE SCREEN · Seen Nov 2026
  • Resizable Array-Backed Integer SetPHONE SCREEN · Seen Sep 2026
  • Shortest Path with Directional Move CostsPHONE SCREEN · Seen Sep 2026
All The Walt Disney Company interview questionsSee The Walt Disney Company hiring insights
Saved
class Solution {
    public int[][] randomGraphPath(int n, int source, int target, int seed) {
        // Write your code here
    }
}
Checking account…