SDE - 1

You are given an array of n integers (a1, a2,....,an), you need to find if the array contains a pythagorean triplet or not.

An array is said to have a pythagorean triplet if there exists three integers x,y and z in the array such that x^2 + y^2 = z^2.

Note

1. The integers x,y and z might not be distinct , but they should be present at different locations in the array i.e if a[i] = x, a[j] = y and a[k] = z, then i,j and k should be pairwise distinct.
2. The integers a,b and c can be present in any order in the given array.

You have been given an integer array/list(arr) and a number 'Sum'. Find and return the total number of pairs in the array/list which when added, results equal to the 'Sum'.

Note:

Given array/list can contain duplicate elements.

(arr[i],arr[j]) and (arr[j],arr[i]) are considered same.

For eg - Wear Socks then Wear Shoes Brush before Wear Socks 

Output - Brush Wear Socks Wear Shoes

You are given a number 'N' in the form of a string 'S', which is a palindrome. You need to find the greatest number strictly less than 'N' which is also a palindrome.

Note:

1. A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward, such as madam, racecar, 1234321, etc.
2. The numerical value of the given string S will be greater than 0.
3. A single-digit number is also considered a palindrome.
4. The answer number should not contain any leading zeros, except for the case when the answer is 0.
5. Note that the length of the string is nothing but the number of digits in N.

You will be given a stream of numbers, and you need to find the 'kth' largest number in the stream at any given time.

As the stream of numbers can not be given during compile time, so you need to design a data structure which can accept infinite numbers and can return the 'kth' largest number at any given time.

The stream of numbers is nothing but a large collection of numbers from which integers are read at runtime, such as the user will never know the upper limit on the number of integers that will be read.

The implemented data structure must support the following operations:

1. add(DATA) :
   This function should take one argument of type and store it in its pool and returns the 'kth' largest number from the current pool of integers.

You will be given 'q' queries:

val - For this query, insert the integer into your current pool of integers and return the 'kth' largest integer from the existing pool of integers.

Note

 1. The maximum number of integers that will be given will always be under memory limits.

 2. You will also be given an initial pool of integers whose size equals k.

 3. The maximum number of queries will be less than 10^5.

 4. The 'kth' largest element is not the 'kth' distinct element but the 'kth' largest element in the sorted order.

 5. There will be at least one query of type 2.

You have been given a long type array/list 'arr’ of size 'n’.

It represents an elevation map wherein 'arr[i]’ denotes the elevation of the 'ith' bar.

Print the total amount of rainwater that can be trapped in these elevations.

Note :

The width of each bar is the same and is equal to 1.

Example:

Input: ‘n’ = 6, ‘arr’ = [3, 0, 0, 2, 0, 4].

Output: 10

Explanation: Refer to the image for better comprehension:

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Given a string, representing a chemical formula, return the count of each atom.

An atomic element always starts with an uppercase character, then zero or more lowercase letters follow, representing the name.

One or more digits representing that element's count may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, H2O and H2O2 are possible, but H1O2 is impossible.

Two formulas can be concatenated together to produce another formula. For example, H2O2He3Mg4 is also a formula.

A formula placed in parentheses, and a count (optionally added) is also a formula. For example, (H2O2) and (H2O2)3 are formulas.

Given a formula, return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

Note :

The given formula consists of English alphabets, digits, ‘(‘ and ’)’.

The given formula is always valid.