SDE - 1

You are given an array arr of length N. You have to return a list of integers containing the NGE(next greater element) of each element of the given array. The NGE for an element X is the first greater element on the right side of X in the array. Elements for which no greater element exists, consider the NGE as -1.

For Example :

If the given array is [1, 3, 2], then you need to return [3, -1, -1]. Because for 1, 3 is the next greater element, for 3 it does not have any greater number to its right, and similarly for 2.

You are given a two-dimensional matrix of integers of dimensions N*M, where each cell represents the number of coins in that cell. Alice and Bob have to collect the maximum number of coins. The followings are the conditions to collect coins:

Alice starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (N-1, 0). Bob starts from top right corner, i.e., (0, M-1) and should reach bottom right corner, i.e., (N-1, M-1).

From a point (i, j), Alice and Bob can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

They have to collect all the coins that are present at a cell. If Alice has already collected coins of a cell, then Bob gets no coins if goes through that cell again.

For example :

If the matrix is 
0 2 4 1
4 8 3 7
2 3 6 2
9 7 8 3
1 5 9 4

Then answer is 47. As, Alice will collect coins 0+8+3+9+1 = 21 coins. Bob will collect coins 1+7+6+8+4 = 26 coins. Total coins is 21+26 = 47 coins.

You are given an array 'ARR' consisting of 'N' positive integers, and you need to reduce the size of the array to 1 by performing an operation several number of times. In a single operation, you can merge any two adjacent elements of the array, and the cost of merging will be equal to the sum of those two elements. Find the minimum cost of reducing the given array by performing this operation several number of times.

In a single merge operation, the two elements are removed, and their sum is inserted at its place, hence decreasing the size of the array by 1 after each operation. For eg: Consider the array A1, A2, Ai-2, Ai-1, Ai, Aj, Aj+1, Aj+2 ,,,, An. Let the operation be performed on two indices i and j, So after merging the array will look like A1, A2, Ai-2, Ai-1, Ai+Aj, Aj+1, Aj+2,,,, An.

Note:

Note that the given operation will be performed only 'N'-1 times, where 'N' is the size of the given array.

Given two strings ‘STR’ and ‘PTR’. Find all the starting indices of ‘PTR’ anagram substring in ‘STR’. Two strings are anagram if and only if one string can be converted into another string by rearranging the character.

For example, ‘ABCD’ and ‘ACBD’ are two anagram strings because ‘ACBD’ can be converted into ‘ABCD’ by rearranging the ‘B’ and ‘C’. ’ABA’ and ‘ABB’ are not anagram because we can’t convert ‘ABA’ to ‘ABB’ by rearranging the characters of particular strings.

‘ABACD’ and ‘CABAD’ are anagram because ‘ABACD’ can be converted into ‘CABAD’ by rearranging the first ‘A’ with ‘C’ and second ‘A’ with ‘B’.

Note:

Strings ‘STR’ and ‘PTR’ consist only of English uppercases.

Length of string ‘STR’ will always be greater than or equal to the length of string ‘PTR’.

The index is ‘0’ based.

In case, there is no anagram substring then return an empty sequence.

Explanation:

For example, the given ‘STR’ is ‘BACDGABCD’ and ‘PTR’ is ‘ABCD’. Indices are given

0-3 in ‘STR’ index 0,1,2,3 are ‘BACD’ and it is an anagram with ‘ABCD’
1-4 in ‘STR’ index 1,2,3,4 are ‘ACDG’ and it is not anagram with ‘ABCD’
2-5 in ‘STR’ index 2,3,4,5 are ‘CDGA’ and it is not anagram with ‘ABCD’
3-6 in ‘STR’ index 3,4,5,6 are ‘DGAB’ and it is not anagram with ‘ABCD’
4-7 in ‘STR’ index 4,5,6,7 are ‘GABC’ and it is not anagram with ‘ABCD’
5-8 in ‘STR’ index 5,6,7,8 are ‘ABCD’ and it is an anagram with ‘ABCD’

Hence there are 2 starting indices of substrings in the string ‘STR’ that are anagram with given ‘PTR’  which are index 0 and 5.