Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

Given a weighted directed acyclic graph (DAG), find the longest path between two nodes.

**Example**

Input:

dag_nodes = 4

dag_from = [1 1 1 3]

dag_to = [2 3 4 4]

dag_weight = [2 2 4 3]

from_node = 1

to_node = 4

Output: [1, 3, 4]

Total there are two paths from node 1 to node 4:

1) 1 -> 4 with length 4.

2) 1 -> 3 -> 4 with length 2 + 3 = 5.

The latter is the longest one.

**Notes**

Input Parameters: There are six arguments.

1. An integer dag_nodes

2. An integer array dag_from

3. An integer array dag_to

4. An integer array dag_weight

5. An integer from_node

6. An integer to_node

The first four arguments cumulatively describe the weighted DAG: there are dag_nodes nodes and there is an edge from dag_from[i] node to dag_to[i] node with length dag_weight[i].

Output: Return an array of integers, the nodes in the longest paths from from_node to to_node (including both ends). If from_node=to_node, return [from_node]. If there are multiple longest paths, return any one.

**Constraints:**

● There will be at most one edge connecting any pair of nodes in one direction, i.e. no multi edges.

● to_node is reachable from from_node.

● 1

● 1

● 1

● Total number of edges in the graph

Make sure to use an appropriate data type to store the integer values, e.g. long long int in C++.

Given graph is a DAG. In a DAG we can divide our nodes in different levels, with "each edge" going from upper level to lower level.

So we can start updating maximum length level wise, starting from upper level and then moving to level below it!

To divide nodes level wise with each edge going from upper level to lower level, we can use topological sort.

The sample solution we provided uses this approach.

**Time Complexity:**

O(number of nodes + number of edges). Given the constraints it is equivalent to O(number of edges).

**Auxiliary Space Used: **

O(number of nodes + number of edges) = O(number of edges).

**Space Complexity: **

O(number of nodes + number of edges) = O(number of edges).

Note that the complexities aren’t equal to just O(numberber of nodes) because the number of edges in a DAG can be way larger than the number of nodes.

Note: Input and Output will already be taken care of.

Given a weighted directed acyclic graph (DAG), find the longest path between two nodes.

**Example**

Input:

dag_nodes = 4

dag_from = [1 1 1 3]

dag_to = [2 3 4 4]

dag_weight = [2 2 4 3]

from_node = 1

to_node = 4

Output: [1, 3, 4]

Total there are two paths from node 1 to node 4:

1) 1 -> 4 with length 4.

2) 1 -> 3 -> 4 with length 2 + 3 = 5.

The latter is the longest one.

**Notes**

Input Parameters: There are six arguments.

1. An integer dag_nodes

2. An integer array dag_from

3. An integer array dag_to

4. An integer array dag_weight

5. An integer from_node

6. An integer to_node

The first four arguments cumulatively describe the weighted DAG: there are dag_nodes nodes and there is an edge from dag_from[i] node to dag_to[i] node with length dag_weight[i].

Output: Return an array of integers, the nodes in the longest paths from from_node to to_node (including both ends). If from_node=to_node, return [from_node]. If there are multiple longest paths, return any one.

**Constraints:**

● There will be at most one edge connecting any pair of nodes in one direction, i.e. no multi edges.

● to_node is reachable from from_node.

● 1

● 1

● 1

● Total number of edges in the graph

Make sure to use an appropriate data type to store the integer values, e.g. long long int in C++.

Given graph is a DAG. In a DAG we can divide our nodes in different levels, with "each edge" going from upper level to lower level.

So we can start updating maximum length level wise, starting from upper level and then moving to level below it!

To divide nodes level wise with each edge going from upper level to lower level, we can use topological sort.

The sample solution we provided uses this approach.

**Time Complexity:**

O(number of nodes + number of edges). Given the constraints it is equivalent to O(number of edges).

**Auxiliary Space Used: **

O(number of nodes + number of edges) = O(number of edges).

**Space Complexity: **

O(number of nodes + number of edges) = O(number of edges).

Note that the complexities aren’t equal to just O(numberber of nodes) because the number of edges in a DAG can be way larger than the number of nodes.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart