SDE - Intern

You are given an 'N' * 'M' sized binary-valued matrix 'MAT, where 'N' is the number of rows and 'M' is the number of columns. You need to return the maximum size (area) of the submatrix which consists of all 1’s i.e. the maximum area of a submatrix in which each cell has only the value ‘1’.

In the above image, areas in green, red, and violet color are all submatrices of the original 4x4 matrix.

Note:

1. Binary valued matrix has only two values in each cell : 0 and 1.
2. A submatrix is a matrix formed by selecting certain rows and columns from a larger matrix.
3. The area of a matrix with 'h' rows and 'w' columns is equal to 'h' * 'w'. 

You are given a binary tree having 'n' nodes. Each node of the tree has an integer value.

Your task is to find the maximum possible sum of a simple path between any two nodes (possibly the same) of the given tree.

A simple path is a path between any two nodes of a tree, such that no edge in the path is repeated twice. The sum of a simple path is defined as the summation of all node values in a path.

You have been given an array 'ARR' of 'N' distinct elements.

Your task is to find the minimum no. of swaps required to sort the array.

For example:

For the given input array [4, 3, 2, 1], the minimum no. of swaps required to sort the array is 2, i.e. swap index 0 with 3 and 1 with 2 to form the sorted array [1, 2, 3, 4].

You are given a string denoting a valid Prefix expression containing ‘+’, ’-’, ’*’, ‘/’ and lowercase letters.

Convert the given Prefix expression into an Infix expression.

Note:

Infix notation is a method of writing mathematical expressions in which operators are placed between operands. For example, "a + b" represents the addition of a and b.

Prefix notation is a method of writing mathematical expressions in which operators are placed before the operands. For example, "+ a b" represents the addition of a and b.

Expression contains lowercase English letters, ‘+’, ‘-’, ‘*’, and  ‘/’. 

Example:

Input: /-ab+-cde

Output: ((a-b)/((c-d)+e))

Explanation:
In this test case, there are four operators ‘/’, ‘-’, ‘+’, ‘-’.
Prefix expression:  /-ab+-cde. 
The operator between  ‘a’ and ‘b’ is ‘-’. Resulting expression: /(a-b)+-cde.
The operator between  ‘c’ and ‘d’ is ‘-’. Resulting expression: /(a-b)+(c-d)e.
The operator between ‘c-d’ and ‘e’ is +. Resulting expression: /(a-b)((c-d)+e).
The operator between ‘a-b’ and ‘((c-d)+e)’ is ‘/’. Resulting expression: ((a-b)/((c-d)+e)).