SDE - 1

Given a singly linked list of integers. Your task is to return the head of the reversed linked list.

For example:

The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then the reverse linked list is 4 -> 3 -> 2 -> 1 -> NULL and the head of the reversed linked list will be 4.

Follow Up :

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

You are given a binary tree having 'N' nodes. Each node of the tree has an integer value. Your task is to find the maximum average of node values of any subtree of the given tree.

You are given a string 'STR' of lowercase English alphabets. You need to find the repeated character present first in the string.

Example:

If the string is: “abccba”, then the first repeated character is ‘c’, but the repeated character that is present first in the string is ‘a’. You need to print ‘a’.

Note:

Keep in mind that you need to print the repeated character that is present first in the string and not the first repeating character.

You are given the ‘ROOT’ of a binary tree with ‘N’ nodes where each node in the tree has some coins, and there are ‘N’ coins total. In one move, we may choose two adjacent nodes and move one coin from one node to another.

Your task is to return the number of moves required to make every node have exactly one coin.

Note:

A move may be from parent to child or from child to parent.

For example,

Given ‘ROOT’ = [2,-1,0,-1,-1]

The tree would look like this : 

The answer would be 1, because the root node will transfer 1 coin to its right child. Thus both nodes have the same number of coins now.

You are given 'n' roses and you are also given an array 'arr' where 'arr[i]' denotes that the 'i^th' rose will bloom on the 'arr[i]^th' day.

You can only pick already bloomed roses that are adjacent to make a bouquet. You are also told that you require exactly 'k' adjacent bloomed roses to make a single bouquet.

Find the minimum number of days required to make at least 'm' bouquets each containing 'k' roses. Return -1 if it is not possible.

Example :

Input: n = 9,  arr = [ 1, 2, 1, 2, 7, 2, 2, 3, 1 ], k = 3, m = 2

Output: 3. 

Explanation: This is because on the 3rd day: all the roses with 'arr[i]' less than equal to 3 have already bloomed, this means every rose except the 5th rose has bloomed. Now we can form the first bouquet from the first three roses and the second bouquet from the last three roses.

Ninja is stuck in a maze which is in a form of a binary tree. He needs your help in order to get out.

Ninja is presently at the node ‘X’. The only exit points of the maze are the leaf nodes of the tree. You need to tell him the distance to the nearest exit point from his current location. This will help him decide which path he should take in order to escape from the maze.

Example:

Suppose, Ninja is stuck at node 62. The possible exit points in the maze are: 40, 10, and 20. From all the possible exit points the closest ones are 10 and 20 which are at a distance of 1 unit.

A thief wants to loot houses. He knows the amount of money in each house. He cannot loot two consecutive houses. Find the maximum amount of money he can loot.