SDE - Intern

You are given an undirected, connected and weighted graph G(V, E), consisting of V number of vertices (numbered from 0 to V-1) and E number of edges.

Find and print the total weight of the Minimum Spanning Tree (MST) using Kruskal's algorithm.

By definition, a minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

You have been given a curve whose edges are parallel to either x-axis or y-axis. You need to return another curve which will pass through the midpoints of all the edges of the curve. The curve will be given in the form of a linked list, where each node represents the coordinates of the curve.

The curve to be returned will also be in the form of a linked list, where each node may represent the coordinates of the midpoints of the edges.

Note

1. The coordinates of the curve will be given in non-descending order of x coordinate from start to end of the linked list and for every two adjacent coordinates either the x-coordinate or the y-coordinate will be the same.
2. All the coordinates will be pairwise distinct i.e there are no two coordinates (x1, y1) and (x2, y2) such that x1 = x2 and y1 = y2.
3. The first coordinate and the last coordinate in the input can be assumed as the starting point and the ending point of the curve respectively.
4. You may assume that the starting point and ending point of the curve will be the midpoint of the first edge, and the last edge of the input curve( in the order of input coordinates) respectively.
5. If the coordinates of the midpoint are not whole numbers, you may take the floor value of the coordinates. For example, the midpoint (3.5, 5) will be taken as (3, 5).

Given an array of ‘N’ integers and ‘Q’ queries. The query is defined as below :-

Given 2 integers ‘l’ and ‘r’ (‘l’ >= 0 and ‘r’ < N) find the maximum subarray sum between ‘l’ to ‘r’ (Inclusive).

Query( ‘l’ ,’r’) = max(arr[i] + arr[i+1] +...arr[j].( i >= ‘l’ and j <= ‘r’)

You are given a directed graph having ‘N’ nodes. A matrix ‘EDGES’ of size M x 2 is given which represents the ‘M’ edges such that there is an edge directed from node EDGES[i][0] to node EDGES[i][1].

Find whether the graph contains a cycle or not, return true if a cycle is present in the given directed graph else return false.

For Example :

In the following directed graph has a cycle i.e. B->C->E->D->B.

Note :

1. The cycle must contain at least two nodes.
2. It is guaranteed that the given graph has no self-loops in the graph.
3. The graph may or may not be connected.
4. Nodes are numbered from 1 to N.
5. Your solution will run on multiple test cases. If you are using global variables make sure to clear them.