SDE - Intern

You have a binary tree of 'N' unique nodes and a Start node from where the tree will start to burn. Given that the Start node will always exist in the tree, your task is to print the time (in minutes) that it will take to burn the whole tree.

It is given that it takes 1 minute for the fire to travel from the burning node to its adjacent node and burn down the adjacent node.

For Example :

For the given binary tree: [1, 2, 3, -1, -1, 4, 5, -1, -1, -1, -1]
Start Node: 3

    1
   / \
  2   3
     / \
    4   5

Output: 2

Explanation :
In the zeroth minute, Node 3 will start to burn.

After one minute, Nodes (1, 4, 5) that are adjacent to 3 will burn completely.

After two minutes, the only remaining Node 2 will be burnt and there will be no nodes remaining in the binary tree. 

So, the whole tree will burn in 2 minutes.

You are given a string str consisting only of the characters 'L' and 'R'. Imagine a pivot on a compass that is initially pointing North (N).

Your task is to determine the final direction of the pivot after performing a series of rotations as described by the input string.

'L' represents a 90-degree left (counter-clockwise) rotation.

'R' represents a 90-degree right (clockwise) rotation.

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.

Given an infinite supply of Indian currency i.e. [1, 2, 5, 10, 20, 50, 100, 500, 1000] valued coins and an amount 'N'.

Find the minimum coins needed to make the sum equal to 'N'. You have to return the list containing the value of coins required in decreasing order.

For Example

For Amount = 70, the minimum number of coins required is 2 i.e an Rs. 50 coin and a Rs. 20 coin.

Note

It is always possible to find the minimum number of coins for the given amount. So, the answer will always exist.

You are given an array A of 'N' integers and 'Q' queries.

For each query, you are given a start index L and an end index R (1-based), which define a subarray A[L...R].

Your task is to find the median of this subarray. The median of a subarray is defined as the element that would be at the middle position if the subarray were sorted in non-decreasing order.

If the subarray's length is len, the median is the element at index floor((len + 1) / 2) of the sorted subarray (1-based index).

• Explain the different types of base classes in OOP.
• What is the difference between a shallow copy and a deep copy? (Learn)