Spring Intern

You have been given a string 'S' which only consists of lowercase English-Alphabet letters.

Your task is to find the shortest(minimum length) substring of 'S' which contains all the characters of 'S' at least once. If there are many substrings with the shortest length, then find one which appears earlier in the string i.e. substring whose starting index is lowest.

For example-

If the given string is S = "abcba", then the possible substrings are "abc" and "cba". As "abc" starts with a lower index (i.e. 0, "cba" start with index 2), we will print "abc" as our shortest substring that contains all characters of 'S'.

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 ‘STR’ containing lowercase and uppercase letters. You need to sort the string so that the resulting string contains uppercase and lowercase letters at alternate positions but in sorted order.

Note

If any lowercase or uppercase letters remains left after alternate positioning, then append them at the last of the string in sorted order.

For Example

If the given string STR = “rDaBfS” then after sorting  STR = “aBfDrS”. In the sorted string, lowercase letters a,f,r, and uppercase letters B, D, S are in sorted order and alternate positions.

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.

You are given an array 'ARR' of strings having 'N' strings. You are also given a string 'S'. Your task is to find all the occurrences of each string of the array 'ARR' as substrings in the string 'S'.

For example:

Consider the array 'ARR' = { "ab", "aa" } and the string 'S' = "aabab". 
The substring "ab" is present at index 1 and index 3 of the String 'S' and the substring "aa" is present at index 0 of the String S.

Why BFS for this question why not DFS

• Why Cisco?
• What is your short term goal?
• What do you know about Cisco?
• Did you intern any where?
• How soon will you join if you are offered with internship?
•  Are you willing to relocate?