How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Design 2D DP on a DAG | Amazon Coding Question

Quick Overview

Design 2D DP on a DAG evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Design 2D DP on a DAG

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a directed acyclic graph G(V, E) with N nodes, M edges, a designated source s, and an integer L, design a 2D dynamic program dp[u][k] that computes, for all nodes u and 0 ≤ k ≤ L, the number of distinct paths from s to u using exactly k edges. Specify the state definition, base cases, transition function, and iteration order using a topological sort. Analyze time and space complexity, describe how to reduce space via rolling arrays, and discuss adaptations for weighted edges (e.g., shortest/longest path with at most/exactly k edges) and for counting paths to a target t.

Quick Answer: Design 2D DP on a DAG evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a directed acyclic graph (DAG) with `n` nodes labeled `0..n-1`, a list of directed `edges` where each `edges[i] = [u, v]` represents an edge `u -> v`, a designated `source` node, and an integer `L`, compute a 2D DP table `dp` where `dp[u][k]` is the number of distinct paths from `source` to node `u` that use exactly `k` edges, for every node `u` and every `k` with `0 <= k <= L`. Return `dp` as an `n x (L+1)` 2D list (row `u`, column `k`). Use a topological order so each node is finalized before its successors are relaxed. Base case: `dp[source][0] = 1`, all other entries `0`. Transition: for each node `u` in topological order and each edge `u -> v`, add `dp[u][k]` into `dp[v][k+1]` for `0 <= k < L`. Example: n=4, edges=[[0,1],[0,2],[1,3],[2,3]], source=0, L=2. There are two distinct 2-edge paths from 0 to 3 (0->1->3 and 0->2->3), so dp[3][2] = 2. Assumptions: the graph is guaranteed acyclic; node indices are valid; counts fit in a 64-bit integer for the given test sizes.

Constraints

1 <= n <= 10^4
0 <= L <= 200
0 <= edges.length <= 5 * 10^4
Each edge is [u, v] with 0 <= u, v < n; the graph is acyclic.
0 <= source < n
Path counts fit in a signed 64-bit integer for the given inputs.

Examples

Input: (4, [[0,1],[0,2],[1,3],[2,3]], 0, 2)

Expected Output: [[1, 0, 0], [0, 1, 0], [0, 1, 0], [0, 0, 2]]

Explanation: Diamond DAG. Node 3 has two distinct 2-edge paths from 0 (0->1->3 and 0->2->3), so dp[3][2]=2. Nodes 1 and 2 are each reached by one 1-edge path.

Input: (1, [], 0, 0)

Expected Output: [[1]]

Explanation: Base case: the only path from source 0 to itself using exactly 0 edges is the empty path, so dp[0][0]=1.

Input: (3, [[0,1],[1,2],[0,2]], 0, 3)

Expected Output: [[1, 0, 0, 0], [0, 1, 0, 0], [0, 1, 1, 0]]

Explanation: Node 2 is reachable both directly (0->2, 1 edge) and via node 1 (0->1->2, 2 edges), so dp[2][1]=1 and dp[2][2]=1.

Input: (5, [[0,1],[1,2],[2,3],[3,4]], 0, 4)

Expected Output: [[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]]

Explanation: A simple chain: the only way to reach node i is via the unique i-edge path, so dp[i][i]=1 along the diagonal.

Input: (3, [[0,1]], 0, 2)

Expected Output: [[1, 0, 0], [0, 1, 0], [0, 0, 0]]

Explanation: Node 2 is unreachable from source 0, so its entire row stays 0 — covering the disconnected/unreachable edge case.

Input: (2, [], 0, 1)

Expected Output: [[1, 0], [0, 0]]

Explanation: No edges: only dp[0][0]=1; node 1 is unreachable and there are no 1-edge paths from the source at all.

Hints

Process nodes in topological order so dp[u][*] is fully computed before you push its contributions to successors.
Base case is dp[source][0] = 1 (the zero-edge path from source to itself); every other entry starts at 0.
Transition: for edge u -> v, every length-k path to u extends to a length-(k+1) path to v, so dp[v][k+1] += dp[u][k] for 0 <= k < L.
To save memory when you only need exactly-L paths to one target, keep just two layers (k and k+1) and roll them — O(N) instead of O(N*L).

Quick Overview