SDE - Intern

You have been given an array of integers 'ARR' and an integer ‘K’. You need to find the first negative integer in each window of size ‘K’.

Note :

If a window does not contain a negative integer, then print 0 for that window.

For example :

If N = 9, arr[ ] = {-10, 20, -30, -40, 50, 60, -70, 80, 90} and K = 3

then the output will be
{-10 -30 -30 -40 -70 -70 -70}

You have been given a binary tree with an integer value associated to each node. You are supposed to choose a subset of these nodes such that the sum of these chosen nodes is maximum. Keep in mind that no two of the chosen nodes must be adjacent to each other.

Note :

Two nodes are said to be adjacent to each other if they are directly connected to each other. This means that if a node is taken as part of the sum, then none of its children can be considered for the same and vice versa.

For example :

For the given binary tree

Nodes used in consideration for maximum sum such that no two of them are adjacent are highlighted. Maximum sum of nodes = 1 + 1 + 1 + 4 + 5 = 12.

You have been given a binary tree of integers with N number of nodes. Your task is to check if that input tree is a BST (Binary Search Tree) or not.

A binary search tree (BST) is a binary tree data structure which has the following properties.

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

Example :

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 subtrees for node 5 are empty.

Level 3:

For node 1:
The left and right subtrees for node 1 are empty.
For node 3:
The left and right subtrees for node 3 are empty.

Because all the nodes follow the property of a binary search tree, the above tree is a binary search tree.

There are 3 mislabeled jars, with apple and oranges in the first and second jar respectively. The third jar contains a mixture of apples and oranges. You can pick as many fruits as required to precisely label each jar. Determine the minimum number of fruits to be picked up in the process of labeling the jars.

There are 5 lanes on a race track. One needs to find out the 3 fastest horses among total of 25. Find out the minimum number of races to be conducted in order to determine the fastest three.