SDE - 2

You are given an array 'ARR' of 'N' positive integers. Your task is to find if we can partition the given array into two subsets such that the sum of elements in both subsets is equal.

For example, let’s say the given array is [2, 3, 3, 3, 4, 5], then the array can be partitioned as [2, 3, 5], and [3, 3, 4] with equal sum 10.

Follow Up:

Can you solve this using not more than O(S) extra space, where S is the sum of all elements of the given array?

Given a binary tree with N number of nodes, check if that input tree is Partial BST (Binary Search Tree) or not. If yes, return true, return false otherwise.

A binary search tree (BST) is said to be a Partial BST if it follows the following properties.

• The left subtree of a node contains only nodes with data less than and equal to the node’s data.
• The right subtree of a node contains only nodes with data greater than and equal to the node’s data.
• Both the left and right subtrees must also be partial binary search trees.

Example:

Input:

Answer:

Level 1: 

All the nodes in the left subtree of 4 (2, 1, 3) are smaller 
than 4, all the nodes in the right subtree of the 4 (5) are 
larger than 4.

Level 2 :

For node 2:
All the nodes in the left subtree of 2 (1) are smaller than 
2, all the nodes in the right subtree of the 2 (3) are larger than 2.
For node 5:
The left and right subtree for node 5 is empty.

Level 3:

For node 1:
The left and right subtree for node 1 are empty.
For node 3:
The left and right subtree for node 3 are empty.
Because all the nodes follow the property of a Partial binary 
search tree, the above tree is a Partial binary search tree.

You are given an 'N * N' 'MAZE' where some cells have a door while some do not and a key that can be used only once to open a door.

You need to find if there exists a path from the top-left cell to the bottom right cell of the maze provided only downward and rightward movements are allowed.

Note:

1. You have only one key. And a key once used is exhausted and no more available with you during the journey through that path in a maze.

2. A cell with value 1, means the door or path is closed. And you have to spend a key to open the door/ reach that cell.

3. A cell with value 0, means that the cell is free to move / door is always open.

4. Top left cell in the maze and bottom-right cell in the maze may also have a door.

5. Downwards movement: From cell (i, j) to (i, j+1).

6. Rightwards movement: From cell (i, j) to (i+1, j).

Ninja just got an offer letter from a reputable company. The company sent him an offer letter along with the salary bifurcation.

In that bifurcation,Total Salary was not mentioned but instead a ‘basicSalary’ and an upper case character representing grade was mentioned, depending on which the Total Salary is calculated.

Help Ninja in calculating his total salary, where total salary is defined as:

‘totalSalary’ = ‘basic’ + ‘hra’ + ‘da’ + ‘allowance’ - ‘pf’

The above terms are as follows:

‘hra’ = 20% of ‘basic’
‘da’ = 50% of ‘basic’
‘allowance’ = 1700 if grade = ‘A’
‘allowance’ = 1500 if grade = ‘B’
‘allowance’ = 1300 if grade = ‘C' or any other character
‘pf’ = 11% of ‘basic’.

Note :

Round off the ‘totalSalary’ and then print the integral part only.

'x.5' type values will always be round up, for example, 1.5, 2.5 will be round off to 2, 3 respectively.

Introduce yourself
Why do you want to join us?
What are your hobbies?
What do you think makes you a better choice than the other candidates?
What are your strengths and weaknesses?