SWE Intern

Ninja, on his birthday, decided to give a treat to 'N' children in his neighbourhood. Ninja took every child to a nearby candy shop and bought them candies. The shop contains ‘M’ types of candies with an unlimited supply of each candy. The cost of each candy is between 1 and M, inclusive and distinct.

The shopkeeper has marked every candy with a number between 1 and M, inclusive. To make this process fascinating, Ninja found a way. He asked every child three integers, ‘L’, ‘R’, and ‘X’. Then he bought exactly ‘X’ pieces of each candy from [L to R] , i.e., “L, L+1, L+2,..., R-1, R”.

Your task is to find the lexicographically smallest array “A” of ‘M’ integers where each element represents the cost of the ith candy, such that the total cost spent by Ninja is minimum.

Note:

The cost array is a permutation of the first M natural numbers.
The shop has unlimited supplies of candies.
In case of multiple permutations, print one which is lexicographically minimum. 

For example:

Let’s say ‘N’ = 3 , ‘M’ = 5  
The integers told by children are { {2 , 4 , 1} ,{1 , 3 , 2} , {3, 3 , 5} }  

The optimal permutation will  be {3 2 1 4 5}    
Costs paid by Ninja are 7, 12, and 5, respectively.  
The total cost would be 7 + 12 + 5 = 24

You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to return the list of all pairs of elements such that each sum of elements of each pair equals 'S'.

Note:

Each pair should be sorted i.e the first value should be less than or equals to the second value. 

Return the list of pairs sorted in non-decreasing order of their first value. In case if two pairs have the same first value, the pair with a smaller second value should come first.

Ninja and his friends are on a trip. They have come across a river and want to cross the river with the help of boats. There are a total of 'N' people on the trip including Ninja himself. The weight of each person is given in an array 'ARR'. One boat can accommodate at most two persons only if the sum of their weight does not exceed 'L', i.e., the maximum weight capacity of the boat, otherwise, the boat will accommodate only one person. Given the weight of each person and the maximum weight capacity 'L', your task is to find the minimum number of boats required to ensure that everyone crosses the river.

You are given an unsorted array/list 'ARR' of 'N' integers. Your task is to return the length of the longest consecutive sequence.

The consecutive sequence is in the form ['NUM', 'NUM' + 1, 'NUM' + 2, ..., 'NUM' + L] where 'NUM' is the starting integer of the sequence and 'L' + 1 is the length of the sequence.

Note:

If there are any duplicates in the given array we will count only one of them in the consecutive sequence.

For example-

For the given 'ARR' [9,5,4,9,10,10,6].

Output = 3
The longest consecutive sequence is [4,5,6].

Follow Up:

Can you solve this in O(N) time and O(N) space complexity?

You have been given a binary search tree of integers with ‘N’ nodes. Your task is to convert it into a balanced BST with the minimum height possible.

A binary search tree (BST) is a binary tree data structure that 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.

A Balanced BST is defined as a BST, in which the height of two subtrees of every node differs no more than 1.

For Example:

For the given BST:

The modified BST will be: