DSA interview question

Graph Representation in Java (Weighted Directed Graph)

Easy · Data structures · Topics: graph, java

The problem

A logistics service in Java models one-way delivery routes between depots, each with a travel cost: a weighted directed graph. Represent it the idiomatic Java way, as a List<List<int[]>> where adj.get(u) holds {v, w} pairs for every route u → v with cost w. Then compute every depot's in-degree (how many routes arrive there), which the scheduler needs later. Directed edges are stored once, only at their source, unlike undirected graphs.

Example: n = 3, routes (0→1, 5), (0→2, 3), (2→1, 1) → 0:[1 w5, 2 w3] 1:[] 2:[1 w1], in-degrees [0, 2, 1].

Function signature

static List<List<int[]>> buildGraph(int n, int[][] edges);   // edges: {u, v, w}
static int[] inDegrees(List<List<int[]>> adj);

Test cases

Input `(n, edges)`	Output	Explanation
`(3, [[0,1,5],[0,2,3],[2,1,1]])`	`0:[1 w5, 2 w3] 1:[] 2:[1 w1] in-degree [0, 2, 1]`
`(4, [[1,0,2],[2,0,4],[3,0,1]])`	`0:[] 1:[0 w2] 2:[0 w4] 3:[0 w1] in-degree [3, 0, 0, 0]`	Everything flows into 0
`(1, [[0,0,7]])`	`0:[0 w7] in-degree [1]`	A self-loop
`(2, [])`	`0:[] 1:[] in-degree [0, 0]`

(Confirm: edges are directed; parallel edges and self-loops are allowed; vertices are 0..n−1.)

How interviewers phrase it

"How would you represent a weighted directed graph in Java? Build it from an edge list and report the in-degree of every vertex."

Clarifying questions to ask

Directed and weighted? (Yes.)
Can there be parallel edges or self-loops? (Allowed here.)
Which Java types? (A List<List<int[]>> or a small Edge record; int[][] for a matrix.)

Follow-ups to expect

"Why List<List<int[]>>?"
"Why can't you use new ArrayList[n] directly?"
"How do you compute out-degree and in-degree?"
"Where are in-degrees used?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview