Software Engineer

Given a binary tree of integers, you are supposed to modify the given binary tree to a sum tree where each node value is replaced by the sum of the values of both left and right subtrees in the given tree. The value of leaf nodes is changed to zero.

Example:

Below is the example showing the input tree and its sum tree.  

Given a Binary Search Tree (BST) and a range [min, max], remove all keys which are outside the given range. The modified tree should also be BST.

You are given a ‘Binary Tree’.

Return the level-order traversal of the Binary Tree.

Example:

Input: Consider the following Binary Tree:

Output: 
Following is the level-order traversal of the given Binary Tree: [1, 2, 3, 5, 6, 4]

You are given an array of integers. You need to sort the array in ascending order using quick sort.

Quick sort is a divide and conquer algorithm in which we choose a pivot point and partition the array into two parts i.e, left and right. The left part contains the numbers smaller than the pivot element and the right part contains the numbers larger than the pivot element. Then we recursively sort the left and right parts of the array.

Example:

Let the array = [ 4, 2, 1, 5, 3 ]
Let pivot to be the rightmost number.

After the 1st level partitioning the array will be { 2, 1, 3, 4, 5 } as 3 was the pivot. After 2nd level partitioning the array will be { 1, 2, 3, 4, 5 } as 1 was the pivot for the left part and 5 was the pivot for the right part. Now our array is sorted and there is no need to divide it again.

You are given a square matrix of non-negative integers 'MATRIX'. Your task is to rotate that array by 90 degrees in an anti-clockwise direction using constant extra space.

For example:

For given 2D array :

    [    [ 1,  2,  3 ],
         [ 4,  5,  6 ],
         [ 7,  8,  9 ]  ]

After 90 degree rotation in anti clockwise direction, it will become:

    [   [ 3,  6,  9 ],
        [ 2,  5,  8 ],
        [ 1,  4,  7 ]   ]

An expression is called the postfix expression if the operator appears in the expression after the operands.

Example :

Infix expression: A + B  *  C - D 

Postfix expression:  A B + C D - *

Given a postfix expression, the task is to evaluate the expression. The answer could be very large, output your answer modulo (10^9+7). Also, use modular division when required.

Note:

1. Operators will only include the basic arithmetic operators like '*', '/', '+', and '-'.

2. The operand can contain multiple digits. 

3. The operators and operands will have space as a separator between them.

4. There won’t be any brackets in the postfix expression.