Software Engineer

For a given array with N elements, you need to find the length of the longest subsequence from the array such that all the elements of the subsequence are sorted in strictly increasing order.

Strictly Increasing Sequence is when each term in the sequence is larger than the preceding term.

For example:

[1, 2, 3, 4] is a strictly increasing array, while [2, 1, 4, 3] is not.

You are given an array 'a' of size 'n'.

Print the Next Greater Element(NGE) for every element.

The Next Greater Element for an element 'x' is the first element on the right side of 'x' in the array, which is greater than 'x'.

If no greater elements exist to the right of 'x', consider the next greater element as -1.

For example:

Input: 'a' = [7, 12, 1, 20]

Output: NGE = [12, 20, 20, -1]

Explanation: For the given array,

- The next greater element for 7 is 12.

- The next greater element for 12 is 20. 

- The next greater element for 1 is 20. 

- There is no greater element for 20 on the right side. So we consider NGE as -1.

Ninja has been provided a matrix 'MAT' of size 'N X M' where 'M' is the number of columns in the matrix, and 'N' is the number of rows.

The weight of the particular row is the sum of all elements in it. Ninja wants to find the maximum weight amongst all the rows.

Your task is to help the ninja find the maximum weight amongst all the rows.

EXAMPLE:

Input: 'N' = 2, 'M' = 3, 'MAT' = [[1, 2, 3], [2, 0, 0]]
Output: 6

The weight of first row is 1 + 2 + 3 = 6
The weight of the second row is 2 + 0 + 0 = 2; hence the answer will be a maximum of 2 and 6, which is 6.

Given a sorted array of keys of BST and an array of frequency counts of each key in the same order as in the given inorder traversal. The frequency of an element is the number of searches made to that element. Construct a binary search tree from the given keys such that the total cost of all the searches is minimum.

Cost of searching a key is its frequency multiplied by its level number in the BST.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

For example:

Input keys = [ 1, 3, 5 ] 
Frequency = [ 3, 10, 7 ] 

All the unique BST possible from the given keys are: 

Among all these possible BST, the minimum cost is obtained from the below BST: 

Cost = 1 * (freq of 3) + 2 * (freq of 1) + 2 * (freq of 5) = 30 
where 1 is the level of node 3, 2 is the level of the node 1 and node 5. 

You are given two arbitrary binary trees. You need to find if both trees are isomorphic or not.

Two binary trees are said to be isomorphic with each other, if one of the trees can be obtained from the other, by performing the following operation any number of times:

Choose a node of the tree, swap its left and right subtree i.e the left subtree will become the right one, and vice versa.

Note:

1. A binary tree is a tree in which each node has at most two children.   

2. The left subtree of a node, is the tree in which the left child of the node is the root of that tree, and the same holds for the right subtree.

3. The given operation can be performed on any node at any level of the given trees.  

4. Two empty trees are also said to be isomorphic.

You are given an arbitrary unweighted rooted tree which consists of N nodes, 0 to N - 1. Your task is to find the largest distance between two nodes in the tree.

The distance between two nodes is the number of edges in a path between the nodes (there will always be a unique path between any pair of nodes since it is a tree).

Note :

Use zero-based indexing for the nodes.

The tree is always rooted at 0.