SDE - Intern

You are given an array ‘ARR’ containing ‘N’ integers, and you are also given an integer ‘TARGET’.

You task is to find the count of triplets i, j, k ( 0 ≤ i < j < k < N ), such that 'ARR[i]' + 'ARR[j]' + 'ARR[j]' is less than the value of ‘TARGET’.

For Example :

If ‘N’ = 7, ‘ARR’ = { 1, 5, 2, 3, 4, 6, 7 } and ‘TARGET’ = 9

Then, there are three triplets with sum less than 9:
1) {1, 5, 2}
2) {1, 2, 3}
3) {1, 2, 4}
4) {1, 3, 4}

Thus, the output will be 4.

You are given an N-ary tree where every node has at most ‘N’ child nodes. You need to find the level order traversal of this tree

Note:

Note that the level order traversal must not contain any null values, simply return the tree in level order.

You are given a binary tree consisting of ‘N’ nodes. Your task is to replace all the half nodes present in the binary tree with its child node. Half nodes are those nodes that have only one child.

For Example:

In this given binary tree, nodes 7, 5, and 9 are half nodes because they have only one child node. So we have to replace these nodes with their child. The inorder traversal of the updated binary tree is [1, 6, 11, 2, 4]. Hence, the answer is [1, 6, 11, 2, 4].

Example:

Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. 

The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

You are given an array of ‘N’ integers. You need to return another array ‘product’ such that ‘product[i]’ contains the product of all the arrays except the element at the ith position in the given array.

Note

As the product of elements can be very large you need to return the answer in mod (10^9+7).

Follow Up

Try to do this without using the division operator ‘/’, in constant space. The output array does not count as extra space for the purpose of space complexity analysis.

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.

Given a string 'S' of length 'L', return the length of the longest substring without repeating characters.

Example:

Suppose given input is "abacb", then the length of the longest substring without repeating characters will be 3 ("acb").