Shortest Distance
Ninjaland is a country consisting of ‘N’ states and ‘M’ paths. There are two types of paths that connect any two states. One is the normal path, and the other is a special path. Both paths have their respective lengths. You can use either of the paths to travel between two states. Your task is to determine the shortest distance between the two given states such that at most, one(possibly zero) special path is included in this path.

Note:

1. All the paths are directed. 2. Multiple paths can be present between two states. 3. All the states are connected with each other. 4. It does not have any self-loop. 5. At least one path always exists between the two given states.

For Example:

If ‘N’ = 3, ‘M’ = 2, and given values of paths are [ [1, 2, 2, 3], [2, 3, 4, 2] ] You have to calculate the shortest distance between ‘X’ = 1 and ‘Y’ = 3

In the diagram, we can observe no direct edge from state 1 to state, 3 but we can go from state 1 to state 2 using the normal path of length 2 and then from state 2 to state 3 using the special path of length 2. So the total length will be 4, and we can clearly see that no other path can be smaller than this. Hence, the answer is 4.

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases. The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the number of states and the number of paths, respectively. The next ‘M’ lines contain four space-separated integers, ‘A’, ‘B’, ‘W1’, ‘W2’, denoting a normal path from ‘A’ to ‘B’ having a length ‘W1’ and a special path having a length ‘W2’. The last line of each test case contains two space-separated integers, ‘X’ and ‘Y’, denoting the states between which the shortest distance has to be calculated.

Output Format:

For each test case, print an integer denoting the shortest path length between the two given states. Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1

Question

Shortest Distance

Ninjaland is a country consisting of ‘N’ states and ‘M’ paths. There are two types of paths that connect any two states. One is the normal path, and the other is a special path. Both paths have their respective lengths. You can use either of the paths to travel between two states. Your task is to determine the shortest distance between the two given states such that at most, one(possibly zero) special path is included in this path.

Note:

1. All the paths are directed.

2. Multiple paths can be present between two states.

3. All the states are connected with each other.

4. It does not have any self-loop.

5. At least one path always exists between the two given states.

For Example:

If ‘N’ = 3, ‘M’ = 2, and given values of paths are 
[ [1, 2, 2, 3],
  [2, 3, 4, 2] ]
You have to calculate the shortest distance between ‘X’ = 1 and ‘Y’ = 3

diagram

In the diagram, we can observe no direct edge from state 1 to state, 3 but we can go from state 1 to state 2 using the normal path of length 2 and then from state 2 to state 3 using the special path of length 2. So the total length will be 4, and we can clearly see that no other path can be smaller than this. Hence, the answer is 4.

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the number of states and the number of paths, respectively.

The next ‘M’ lines contain four space-separated integers, ‘A’, ‘B’, ‘W1’, ‘W2’, denoting a normal path from ‘A’ to ‘B’ having a length ‘W1’ and a special path having a length ‘W2’.

The last line of each test case contains two space-separated integers, ‘X’ and ‘Y’, denoting the states between which the shortest distance has to be calculated.

Output Format:

For each test case, print an integer denoting the shortest path length between the two given states. 

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N < 10^3
N-1 <= M <= 10^3
1 <= A,B,X,Y <= N
1 <= W1,W2 <= 10^6

Time Limit: 1 sec

Accepted Answer

1)First calculate how many steps you need to travel on the x-axis to reach the destination
2)Then calculate how many steps you need to travel on the y-axis to reach the destination
3)Add the no of steps you got from step1 and step2.

Accepted Answer

Special PathsSpace Complexity: O(1)Explanation: Time Complexity: O(1)Explanation:
Python (3.5)

'''

    Time Complexity: O(N + M * log N)

    Space Complexity: O(N),



    Where N is the total number of nodes and M is the total number of edges present in the graph.

'''



from heapq import heappop, heappush

class Edge:

    def __init__(self, node, d1, d2):

        self.node = node

        self.d1 = d1

        self.d2 = d2



class QueueLink:

    def __init__(self, node, dis, special):

        self.node =node

        self.dis = dis

        self.special = special

    def __lt__(self, nxt):

        if self.dis == nxt.dis :

            return self.special < nxt.special

        return self.dis < nxt.dis





def findShortestDistance(n, edges, src, dst):

    # Initialize a list of list of Edges to form the graph

    graph = [[] for i in range(n+1)]



    for edge in edges:

        node1 = edge[0]

        node2 = edge[1]

        d1 = edge[2]

        d2 = edge[3]

        graph[node1].append(Edge(node2, d1, d2))



    # Initialize a list to store the shortest distance of each node from the source node.

    minDist = [[0 for i in range(n+1)] for j in range(2)]

    # Initialize a boolean list to keep track of whether a node has been already visited or not.

    visited = [[False for i in range(n+1)] for j in range(2)]

   

    # Initially, keep distance of every node from the source node as a really large number.

    # Initially, every node is unvisited.

    for i in range(1,n+1):

        minDist[0][i] = 900000000

        minDist[1][i] = 900000000

        visited[0][i] = False

        visited[1][i] = False



    # Start applying Dijkstra's Algorithm by declaring a priority queue.

    pq = []



    # The ditance of source node from itself will be 0.

    minDist[0][src] = 0

    minDist[1][src] = 0



    heappush(pq, QueueLink(src, 0, False))

    heappush(pq, QueueLink(src, 0, True))



    while (len(pq)>0) :



        currLink = pq[0]

        heappop(pq)

        # If the current link is normal link

        if (currLink.special == False and visited[0][currLink.node] == False):

            visited[0][currLink.node] = True

            for i in range(len(graph[currLink.node])):

                edge = graph[currLink.node][i]



                minDist[0][edge.node] = min(minDist[0][edge.node], minDist[0][currLink.node] + edge.d1)

                minDist[1][edge.node] = min(minDist[1][edge.node], minDist[0][currLink.node] + edge.d2)



                heappush(pq, QueueLink(edge.node, minDist[0][edge.node], False))

                heappush(pq, QueueLink(edge.node, minDist[1][edge.node], True))



        # If the current link is special link

        elif (currLink.special == True and visited[1][currLink.node] == False):

            visited[1][currLink.node] = True

            for  edge in graph[currLink.node]:

                minDist[1][edge.node] = min(minDist[1][edge.node], minDist[1][currLink.node] + edge.d1)

                heappush(pq, QueueLink(edge.node, minDist[1][edge.node], True))

          

    # Return the minimum value  

    return min(minDist[1][dst], minDist[0][dst])

Java (SE 1.8)

/*
    Time Complexity: O(N + M * log N)
    Space Complexity: O(N),

    where 'N' is the number of nodes and 'M' is the number of edges present in the graph.
*/

import java.util.*;

public class Solution {
    public static class Edge {

        int node;
        int d1;
        int d2;

        public Edge(int node, int d1, int d2) {
            this.node = node;
            this.d1 = d1;
            this.d2 = d2;
        }
    }

    public static class QueueLink implements Comparable < QueueLink > {

        int node;
        int dis;
        int special;

        public QueueLink(int node, int dis, int special) {
            this.node = node;
            this.dis = dis;
            this.special = special;
        }

        @Override
        public int compareTo(QueueLink o) {
            if (dis == o.dis) {
                return special - o.special;
            }

            return dis - o.dis;
        }
    }

    public static int findShortestDistance(int n, ArrayList < ArrayList < Integer >> edges, int src, int dst) {
        // Initialize a vector of vector of Edges to form the graph.
        Map < Integer, List < Edge >> graph = new HashMap < > ();

        for (ArrayList < Integer > edge: edges) {
            int node1 = edge.get(0);
            int node2 = edge.get(1);
            int d1 = edge.get(2);
            int d2 = edge.get(3);

            graph.putIfAbsent(node1, new ArrayList < > ());
            graph.get(node1).add(new Edge(node2, d1, d2));
        }

        // Initialize an array to store the shortest distance of each node from the source node.
        int[][] minDist = new int[2][n + 1];
        Arrays.fill(minDist[0], Integer.MAX_VALUE);
        Arrays.fill(minDist[1], Integer.MAX_VALUE);

        // Initialize an array to keep track of whether a node has been already visited or not.
        int[][] visited = new int[2][n + 1];

        // Start applying Dijkstra's Algorithm by declaring a priority queue.
        PriorityQueue < QueueLink > pq = new PriorityQueue < > ();

        // The ditance of source node from itself will be 0.
        minDist[0][src] = 0;
        minDist[1][src] = 0;

        pq.add(new QueueLink(src, 0, 0));
        pq.add(new QueueLink(src, 0, 1));

        while (!pq.isEmpty()) {

            QueueLink currLink = pq.poll();

            // If the current link is normal link.
            if (currLink.special == 0 && visited[0][currLink.node] == 0) {
                visited[0][currLink.node] = 1;
                for (Edge link: graph.getOrDefault(currLink.node, new ArrayList < > ())) {

                    minDist[0][link.node] = Math.min(minDist[0][link.node], minDist[0][currLink.node] + link.d1);
                    minDist[1][link.node] = Math.min(minDist[1][link.node], minDist[0][currLink.node] + link.d2);

                    pq.add(new QueueLink(link.node, minDist[0][link.node], 0));
                    pq.add(new QueueLink(link.node, minDist[1][link.node], 1));
                }
            }

            // If the current link is special link.
            else if (currLink.special == 1 && visited[1][currLink.node] == 0) {
                visited[1][currLink.node] = 1;
                for (Edge link: graph.getOrDefault(currLink.node, new ArrayList < > ())) {
                    minDist[1][link.node] = Math
                        .min(minDist[1][link.node], minDist[1][currLink.node] + link.d1);
                    pq.add(new QueueLink(link.node, minDist[1][link.node], 1));
                }
            }
        }

        // Return the minimum value.
        return Math.min(minDist[1][dst], minDist[0][dst]);
    }
}

C++ (g++ 5.4)

/*

    Time Complexity: O(N + M * log N)

    Space Complexity: O(N),



    where N is the number of nodes and M is the number of edges present in the graph.

*/



struct Edge {

    int node, d1, d2;

    Edge(int node, int d1, int d2) {

        this->node = node;

        this->d1 = d1;

        this->d2 = d2;

    }

};



struct QueueLink {

    int node;

    bool special;

    int dis;

    QueueLink(int node, int dis, bool special) {

        this->node = node;

        this->dis = dis;

        this->special = special;

    }

};

struct cmp

{

    bool operator()(QueueLink* a, QueueLink* b)

    {

        if(a->dis == b->dis) return a->special > b->special;

        return a->dis > b->dis;

    }

};



int findShortestDistance(int n, vector> &edges, int src, int dst) {

    

    // Initialize a vector of vector of Edges to form the graph

    vector> graph(n+1);



    for (vector edge : edges) {

        int node1 = edge[0];

        int node2 = edge[1];

        int d1 = edge[2];

        int d2 = edge[3];

        graph[node1].push_back(Edge(node2, d1, d2));

    }



    // Initialize a vector to store the shortest distance of each node from the source node.

    vector> minDist(2, vector (n+1));

    

    // Initialize a boolean vector to keep track of whether a node has been already visited or not.

    vector> visited(2, vector (n+1));



    // Initially, keep distance of every node from the source node as a really large number.

    // Initially, every node is unvisited.

    for (int i = 1; i < n + 1; i++) {

        minDist[0][i] = 900000000;

        minDist[1][i] = 900000000;

        visited[0][i] = false;

        visited[1][i] = false;

    }



    // Start applying Dijkstra's Algorithm by declaring a priority queue.

    priority_queue, cmp> pq;



    // The ditance of source node from itself will be 0.

    minDist[0][src] = 0;

    minDist[1][src] = 0;



    pq.push(new QueueLink(src, 0, false));

    pq.push(new QueueLink(src, 0, true));



    while (!pq.empty()) {



        QueueLink* currLink = pq.top();

        pq.pop();



        // If the current link is normal link

        if (currLink->special == false && visited[0][currLink->node] == false) {

            visited[0][currLink->node] = true;

            for (Edge edge : graph[currLink->node]) {



                minDist[0][edge.node] = min(minDist[0][edge.node], minDist[0][currLink->node] + edge.d1);

                minDist[1][edge.node] = min(minDist[1][edge.node], minDist[0][currLink->node] + edge.d2);



                pq.push(new QueueLink(edge.node, minDist[0][edge.node], false));

                pq.push(new QueueLink(edge.node, minDist[1][edge.node], true));

            }



        }



        // If the current link is special link

        else if (currLink->special == true && visited[1][currLink->node] == false) {

            visited[1][currLink->node] = true;

            for (Edge edge : graph[currLink->node]) {

                minDist[1][edge.node] = min(minDist[1][edge.node], minDist[1][currLink->node] + edge.d1);

                pq.push(new QueueLink(edge.node, minDist[1][edge.node], true));

            }



        }



    }



    // Return the minimum value

    return min(minDist[1][dst], minDist[0][dst]);

}

Note:

For Example:

Input Format:

Output Format:

Note:

Constraints:

Top Optum Associate Software Engineer interview questions & answers

Popular interview questions of Associate Software Engineer

Top HR questions asked in Optum Associate Software Engineer