SDE - 1

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.

You are given an undirected Tree having 'N' nodes. The nodes are numbered from 1 to 'N'. Your task is to find the sorted list of all such nodes, such that rooting the tree on that node gives the minimum height possible of the given tree.

A tree is a connected acyclic graph. The height of a rooted tree is the maximum value of the distance between the root and all nodes of the tree.

You are given an array 'ARR' of integers of length N. Your task is to find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can have negative numbers as well.

For example, the input [3, 4, -1, 1] should give output 2 because it is the smallest positive number that is missing in the input array.

Given an array “arr” of “N” integers. Your task is to find and return all the indices of local minima and local maxima in the given array. You need to return the indices in a 2-D list where the first(0th) row denotes the indices of local minima and the second row denotes the indices of local maxima. In case if there is no local minima or maxima return -1 as the only row element.

We say that an array element arr[i] is a local minimum if it is less than to its neighbours, and local maximum if it is greater than to its neighbours.

Note:

For corner elements, we need to consider only one neighbour for comparison.    

For Example:

For the given array :  10 5 20 30 40 35 50

The red circle at index 1,5 are local minima because elements at index 1, and 5 both are smaller to its neighbours.

The green circle at index 0,4,6 are local maxima, because element at index 4 is greater than its neighbours, and element at 0, and 4 are corner elements and also greater than its one neighbour.

Given an array/list of integer numbers 'CHOCOLATES' of size 'N', where each value of the array/list represents the number of chocolates in the packet. There are ‘M’ number of students and the task is to distribute the chocolate to their students. Distribute chocolate in such a way that:

1. Each student gets at least one packet of chocolate.

2. The difference between the maximum number of chocolate in a packet and the minimum number of chocolate in a packet given to the students is minimum.

Example :

Given 'N' : 5 (number of packets) and 'M' : 3 (number of students)

And chocolates in each packet is : {8, 11, 7, 15, 2}

All possible way to distribute 5 packets of chocolates among 3 students are -

( 8,15, 7 ) difference of maximum-minimum is ‘15 - 7’ = ‘8’
( 8, 15, 2 ) difference of maximum-minimum is ‘15 - 2’ = ‘13’ 
( 8, 15, 11 ) difference of maximum-minimum is ‘15 - 8’ = ‘7’
( 8, 7, 2 ) difference of maximum-minimum is ‘8 - 2’ = ‘6’
( 8, 7, 11 ) difference of maximum-minimum is ‘11 - 7’ = ‘4’
( 8, 2, 11 ) difference of maximum-minimum is ‘11 - 2’ = ‘9’
( 15, 7, 2 ) difference of maximum-minimum is ‘15 - 2’ = 13’
( 15, 7, 11 ) difference of maximum-minimum is ‘15 - 7’ = ‘8’
( 15, 2, 11 ) difference of maximum-minimum is ‘15 - 2’ = ‘13’
( 7, 2, 11 ) difference of maximum-minimum is ‘11 - 2’ = ‘9’

Hence there are 10 possible ways to distribute ‘5’ packets of chocolate among the ‘3’ students and difference of combination (8, 7, 11) is ‘maximum - minimum’ = ‘11 - 7’ = ‘4’ is minimum in all of the above.

The height of a tree is equal to the number of nodes on the longest path from the root to a leaf.

You are given an arbitrary binary tree consisting of 'n' nodes where each node is associated with a certain value.

Find out the height of the tree.

Example :

Input: Let the binary tree be:

Output: 2

Explanation: The root node is 3, and the leaf nodes are 1 and 2.

There are two nodes visited when traversing from 3 to 1.
There are two nodes visited when traversing from 3 to 2.

Therefore the height of the binary tree is 2.

Questions about the projects and tech stack I worked upon. Also, questions related to my specific role in those projects were asked.

What are your strengths and weaknesses?.