SDE - Intern

You are given an array consisting of N elements and you need to find a subsequence consisting of three elements such that the elements, in the subsequence, are in strictly increasing order.

Note:

There may be multiple such subsequences, so return any one of them.

Example:

Let the array be [100, 22, 13, 45, 59, 26]. The possible subsequences of size 3, whose elements follow increasing order are {22, 45, 59}, {13, 45, 59}.

You are given two arbitrary binary trees consisting of N and M number of nodes respectively, your task is to check whether the two trees are mirror of each other or not.

Two trees are said to be mirror of each other, if

1. Roots of both the given trees are same.
2. Left subtree of the root of the first tree is the mirror of the right subtree of the root of the second tree.
3. Right subtree of the root of the first tree is the mirror of the left subtree of the root of the second tree.

For example,both the given trees are mirror image of each other:

You have been given a Binary Search Tree of integers. You are supposed to convert it to a greater sum tree such that the value of every node in the given BST is replaced with the sum of the values of all the nodes which are greater than the value of the current node in the tree.

A Binary Search Tree is a tree, whose internal nodes each store a value greater than all the values in the node's left subtree and less than those in its right subtree.

Note :

You need to modify the given tree only. You are not allowed to create a new tree.

For example:

For the given binary search tree

11 will be replaced by {15 + 29 + 35 + 40}, i.e. 119.
2 will be replaced by {7 + 11 + 15 + 29 + 35 + 40}, i.e. 137.
29 will be replaced by {35 + 40}, i.e. 75.
1 will be replaced by {2 + 7 + 11 + 15 + 29 + 35 + 40}, i.e. 139.
7 will be replaced by {11 + 15 + 29 + 35 + 40}, i.e. 130.
15 will be replaced by {15 + 29 + 35 + 40}, i.e. 104.
40 will be replaced by 0 {as there is no node with a value greater than 40}.
35 will be replaced by {40}, i.e. 40.

The Ultimate Ninja Ankush was bored, so his friend Ninja Nikhil decided to give him a puzzle to keep him entertained. Nikhil gave Ankush ‘N’ integers and asked how many groups of sizes 2 and 3 can be formed such that the sum of the group is divisible by 3. Although the Ultimate Ninja Ankush is brilliant, some extra help is always appreciated. Can you help The ultimate ninja Ankush with this so that he can prove to Nikhil that he, in fact, is the ultimate ninja?

More formally, Given an array of size ‘N’, we can form a group of two or three. The group should be such that the sum of all elements in that group is a multiple of 3. Count all possible numbers of groups that can be generated in this way.

For example

Given:
‘N’ = 5, ‘ARR’ = [1, 2, 3, 4, 5].
The answer will be two since 8 since 8 pairs can be formed and those are  (1,2), (1,5), (2,4), (4,5),(1,2,3), (3,4,5), (1,3,5), (2,3,4). Therefore the final answer is 8.