SDE - 1

For a given integer array/list 'ARR' of size 'N' containing all distinct values, find the total number of 'Inversions' that may exist.

An inversion is defined for a pair of integers in the array/list when the following two conditions are met.

A pair ('ARR[i]', 'ARR[j]') is said to be an inversion when:

1. 'ARR[i] > 'ARR[j]' 
2. 'i' < 'j'

Where 'i' and 'j' denote the indices ranging from [0, 'N').

An expression is called the postfix expression if the operator appears in the expression after the operands.

Example :

Infix expression: A + B  *  C - D 

Postfix expression:  A B + C D - *

Given a postfix expression, the task is to evaluate the expression. The answer could be very large, output your answer modulo (10^9+7). Also, use modular division when required.

Note:

1. Operators will only include the basic arithmetic operators like '*', '/', '+', and '-'.

2. The operand can contain multiple digits. 

3. The operators and operands will have space as a separator between them.

4. There won’t be any brackets in the postfix expression.

You are given a string of lowercase characters. Your task is to rearrange (reorder) the string in such a way that no two adjacent characters are the same.

You have to return the rearranged string. If there exists more than one solution you can return any of them.If there is no such string you have to return “NO SOLUTION”. If your returned value is correct the program will print ‘CORRECT’ else ‘INCORRECT’.

For example :

If we are given a string "aabb", then the possible solutions are:

(i) abab
(ii) baba

We can see no two adjacent characters are the same in both strings.

So both (i) and (ii) are valid solutions.

You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to return the list of all pairs of elements such that each sum of elements of each pair equals 'S'.

Note:

Each pair should be sorted i.e the first value should be less than or equals to the second value. 

Return the list of pairs sorted in non-decreasing order of their first value. In case if two pairs have the same first value, the pair with a smaller second value should come first.

You are given a 2-dimensional array/list having N rows and M columns, which is filled with ones(1) and zeroes(0). 1 signifies land, and 0 signifies water.

A cell is said to be connected to another cell, if one cell lies immediately next to the other cell, in any of the eight directions (two vertical, two horizontal, and four diagonals).

A group of connected cells having value 1 is called an island. Your task is to find the number of such islands present in the matrix.

You are given a sorted doubly linked list of distinct nodes that means no two nodes present in the list have the same data. You are also given an integer 'X'.Your task is to count the number of triplets in the list that sum up to a given value 'X'.

A doubly linked List (DLL) contains an extra pointer, called the previous pointer, together with the next pointer and data, which are there in the singly linked list such that both forward and backward navigation is possible.

For example, DLL is 1<->2<->3<->4 NULL and the given integer 'X' is 9, then the number of triplets having the sum 9 is only one, and that is (2,3,4).

Note:

1. If no such triplets exist, return zero.
2. At least three elements will always be present in the linked list.