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 Graph, Build A New One With Reversed Edges

Given a strongly connected directed graph, build a new graph with the same number of nodes but every edge reversed. This is also called transposing a graph.

**Example**

Input: Any node of this graph:

Output: Any node of the new:

**Notes**

Input Parameters: Function has one argument pointing to a node of the given graph.

Output: Return any node of the new graph.

**Constraints:**

● 1

● Value in any node will be a unique integer between 1 and number of nodes, inclusive.

● No multiple edges (connecting any pair of nodes in one direction) or self loops (edges connecting a node with itself) in the input graph.

● You are not allowed to modify the given graph. Return a newly built graph.

To solve this problem simple DFS will work. We provided one sample solution.

**Time Complexity:**

Our DFS-like algorithm takes O(n + m) time where n is the number of nodes and m is the number of edges.

Without multiple edges or self loops (which problem statement guarantees) the number of edges m can be as big as n*(n-1) in the worst case. So O(n^2) is the time complexity in terms of n.

**Auxiliary Space Used:**

O(n) for the call stack used by the recursive function dfs() in the worst case.

**Space complexity:**

Same O(n + m) or O(n^2) as in Time Complexity. Both input and output graphs take that much space.

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

Given A Graph, Build A New One With Reversed Edges

Given a strongly connected directed graph, build a new graph with the same number of nodes but every edge reversed. This is also called transposing a graph.

**Example**

Input: Any node of this graph:

Output: Any node of the new:

**Notes**

Input Parameters: Function has one argument pointing to a node of the given graph.

Output: Return any node of the new graph.

**Constraints:**

● 1

● Value in any node will be a unique integer between 1 and number of nodes, inclusive.

● No multiple edges (connecting any pair of nodes in one direction) or self loops (edges connecting a node with itself) in the input graph.

● You are not allowed to modify the given graph. Return a newly built graph.

To solve this problem simple DFS will work. We provided one sample solution.

**Time Complexity:**

Our DFS-like algorithm takes O(n + m) time where n is the number of nodes and m is the number of edges.

Without multiple edges or self loops (which problem statement guarantees) the number of edges m can be as big as n*(n-1) in the worst case. So O(n^2) is the time complexity in terms of n.

**Auxiliary Space Used:**

O(n) for the call stack used by the recursive function dfs() in the worst case.

**Space complexity:**

Same O(n + m) or O(n^2) as in Time Complexity. Both input and output graphs take that much space.

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

Hosted By

Ryan Valles

Founder, Interview Kickstart