SDE - 1

You have been given a Binary Tree where the value of each node is either 0 or 1. Your task is to return the same Binary Tree but all of its subtrees that don't contain a 1 have been removed.

Note :

A subtree of a node X is X, plus every node that is a descendant of X.

For Example :

Look at the below example to see a Binary Tree pruning.
Input: [1, 1, 1, 0, 1, 0, 1, 0, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

Output: [1, 1, 1, -1, 1, -1, 1, -1, -1, -1, -1]

For example, the input for the tree depicted in the below image would be :

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree.

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

You are given a linked list of 'n' nodes and an integer 'k', where 'k' is less than or equal to 'n'.

Your task is to reverse the order of each group of 'k' consecutive nodes, if 'n' is not divisible by 'k', then the last group of nodes should remain unchanged.

For example, if the linked list is 1->2->3->4->5, and 'k' is 3, we have to reverse the first three elements, and leave the last two elements unchanged. Thus, the final linked list being 3->2->1->4->5.

Implement a function that performs this reversal, and returns the head of the modified linked list.

Example:

Input: 'list' = [1, 2, 3, 4], 'k' = 2

Output: 2 1 4 3

Explanation:
We have to reverse the given list 'k' at a time, which is 2 in this case. So we reverse the first 2 elements then the next 2 elements, giving us 2->1->4->3.

Note:

All the node values will be distinct.

You are given an array 'a' of size 'n'.

Print the Next Greater Element(NGE) for every element.

The Next Greater Element for an element 'x' is the first element on the right side of 'x' in the array, which is greater than 'x'.

If no greater elements exist to the right of 'x', consider the next greater element as -1.

For example:

Input: 'a' = [7, 12, 1, 20]

Output: NGE = [12, 20, 20, -1]

Explanation: For the given array,

- The next greater element for 7 is 12.

- The next greater element for 12 is 20. 

- The next greater element for 1 is 20. 

- There is no greater element for 20 on the right side. So we consider NGE as -1.

Given a sequence of numbers ‘ARR’. Your task is to return a sorted sequence of ‘ARR’ in non-descending order with help of the merge sort algorithm.

Example :

Merge Sort Algorithm -

Merge sort is a Divide and Conquer based Algorithm. It divides the input array into two-parts, until the size of the input array is not ‘1’. In the return part, it will merge two sorted arrays a return a whole merged sorted array.

The above illustrates shows how merge sort works.

Note :

It is compulsory to use the ‘Merge Sort’ algorithm.

Asked me to write a join query based on a problem statement. Do not remember it.

You have been given a Singly Linked List of integers, determine if it forms a cycle or not. If there is a cycle, remove the cycle and return the list.

A cycle occurs when a node's ‘next’ points back to a previous node in the list.

Design a parking lot.