Software Engineer Intern

You are given a matrix ‘ARR’ of size N * M. Each entry in this matrix is either 0 or 1.

Find the largest area of a rectangular sub-matrix that has an equal number of 0’s and 1’s in it.

Example :

If ‘N’ = 4 and ‘M’ = 5, and the matrix is:
0 1 0 1 1
0 1 0 1 0
0 1 0 1 1
0 1 0 1 1

Then clearly, the submatrix containing all the elements of the first four columns contains has equal number of 0’s and 1’s, the area of this submatrix is equal to 4 * 4 = 16, therefore we will print 16.

Follow Up :

Try to solve it in less than O( N^2 * M^2 ) time complexity.

You have been given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges. Each edge connecting two nodes (‘X’,’Y’) will have a weight denoting the distance between node ‘X’ and node ‘Y’.

Your task is to find the shortest path distance from the source node, which is the node labeled as 0, to all vertices given in the graph.

Example:

Input:
4 5
0 1 5
0 2 8
1 2 9
1 3 2
2 3 6

In the given input, the number of vertices is 4, and the number of edges is 5.

In the input, following the number of vertices and edges, three numbers are given. The first number denotes node ‘X’, the second number denotes node ‘Y’ and the third number denotes the distance between node ‘X’ and ‘Y’.

As per the input, there is an edge between node 0 and node 1 and the distance between them is 5.

The vertices 0 and 2 have an edge between them and the distance between them is 8.
The vertices 1 and 2 have an edge between them and the distance between them is 9.
The vertices 1 and 3 have an edge between them and the distance between them is 2.
The vertices 2 and 3 have an edge between them and the distance between them is 6.

Note:

1. There are no self-loops(an edge connecting the vertex to itself) in the given graph.

2. There can be parallel edges i.e. two vertices can be directly connected by more than 1 edge.

We are given some inequalities like a > b or c < d, some of the inequalites are between two variables and some are between one variable and one constant number, find if all the inequalities can hold true simultaneously or not.

You are given a linked list and a number ‘x’, You have to partition the linked list in such a way that all nodes with a value less than 'x' comes before the nodes with values greater than or equal to 'x'. The original relative order should be preserved.