SDE - Intern

Prateek is a kindergarten teacher. He wants to give some candies to the children in his class. All the children stand in a line and each of them has a grade according to his or her performance in the class. Prateek wants to give at least one candy to each child. If two children are standing adjacent to each other, then the one with the higher rating must get more candies than the other. Prateek wants to minimize the total number of candies he must buy.

Given an array 'STUDENTS' of size 'N' that contains the grades for each student, your task is to find what is the minimum number of candies Prateek must buy so that he can distribute them among his students according to the criteria given above.

Example :

Given students' ratings : [5, 8, 1, 5, 9, 4]. 
He gives the students candy in the following minimal amounts : [1, 2, 1, 2, 3, 1]. He must buy a minimum of 10 candies.

Note :

1. If two students having the same grade are standing next to each other, they may receive the same number of candies.
2. Every student must get at least a candy.

Ninja Yuki is in the mood of shopping ninja blades today, and why should he not be, its finally the time for the Spring Fair in his Village. Initially, he has 0 number of blades and aims to buy ‘N’ of them from the fair. But the blade shopkeeper being a cunning man himself, presents a weird way of pricing the number of ninja blades Yuki can buy.

Suppose at any instance Yuki has ‘K’ number of blades, then:

1) Yuki can buy 1 more blade with cost 'A.’ He now has ‘K+1’ Ninja blades.
2) Yuki could buy a ‘K’ number of blades with cost 'B.’ He now has ‘2*K’ blades.
where 'A' and 'B' are predefined and constant.

Yuki does not want to get robbed in the fair. Being his nerd friend can you tell him the minimum price he needs to pay to buy exactly ‘N’ ninja blades, considering he has 0 blades initially?

Note:

There can be two or more ways with the exact cost. You can consider any one of them, but the overall cost to reach from 0 to 'N' must be minimized.

For example:

Consider Yuki need to buy 5 blades, the cost of adding 1 blade is 2, and the cost of doubling the blades is 1 then you have to perform the following operations:
1) Doubling 0 will result in 0 only, so add 1 blade to 0 blades with cost 2. Total cost becomes 2.

2) Next, you can either double 1 to reach 2 or add 1 blade. But since the cost of doubling is less than that of adding, so double 1 with cost 1. Total cost becomes 3.

3) Doubling 2 will result in 4 with a cost of 1. Total becomes 4.

4) Adding 1 in 4 will result in 5 (which is the desired number) with a cost of 2. The total cost to reach 5 becomes 6.

You are given a string A consisting of lower case English letters. You have to find the first non-repeating character from each stream of characters.

For Example: If the given string is 'bbaca', then the operations are done as:

The first stream is “b” and the first non-repeating character is ‘b’ itself, so print ‘b’. 
The next stream is “bb” and there are no non-repeating characters, so print nothing.
The next stream is “bba” and the first non-repeating character is ‘a’, so print ‘a’. 
The next stream is “bbac” and the first non-repeating character is ‘a’, so print ‘a’. 
The next stream is “bbaca” and the first non-repeating character is ‘c’, so print ‘c’. 

Given a 2-dimensional boolean matrix mat of size N x M, modify the matrix such that if an element is 1, set its entire row and column to 1 i.e. if mat[i][j] = 1, then make all the elements of the ith row and the jth column as 1.

Note :

You need to make the modifications in the input matrix.

You do not need to print anything, it has already been taken care of. 

You are given an array 'ARR' consisting of 'N' elements, and you need to find the maximum value of sum(i * ARR[i]) among all possible rotations of the given array. The rotations allowed are left rotation, and right rotation, and these rotations can be performed any number of times on the array.

Sum(i * ARR[i]) denotes the summation of all values (i * ARR[i]) for every 'i', where 0 <= 'i' <= 'N' - 1.

Note :

1. The array follows 0-based indexing.
2. In one rotation operation, all elements of the array will shift either towards the left or right by one index.
3. The element at the extreme left index (i.e. 0th index) will shift to the 'N-1'th index after applying one left rotation on the array and the rest all the elements will shift to the 'i-1'th index.
4. The element at the extreme right index (i.e. 'N-1'th index) will shift to the 0th index after applying one right rotation on the array and the rest of the elements will shift to the 'i' + 1'th index.

You are given an arbitrary binary tree consisting of 'N' nodes numbered from 1 to 'N', and each node is associated with some positive integer value. Your task is to find the average of all the levels in the given tree, i.e you have to find the average of all the node values present on the level, for each level.

Two nodes of a tree are said to be at the same level ‘K’ if both of them are at equal distance( 'K' ) from the 'ROOT' node. The 'ROOT' node is said to be at level 0.

Note :

1. Two nodes may have the same value associated with it.
2. Average of any level is computed as the sum of the values of all the nodes at that level divided by the number of nodes at that level.
3. You will be given the 'ROOT' node of the binary tree.
4. You need to print the floor value for each average. For example,  if the average of node values at some level is 3.5 then you have to print 3.