SDE - 1

You are given an array “ARR” of N integers. You are required to perform an operation on the array each time until it becomes empty. The operation is to select an element from the array(let’s say at ith index i.e ARR[i]) and remove one occurrence of the selected element from the array and remove all the occurrences of (ARR[i]-1) and (ARR[i]+1) from the array(if present). Your task is to maximize the sum of selected elements from the array.

For example, let’s say the given array is [2, 3, 3, 3, 4, 5].

The maximum possible sum for the given array would be 14. Because if we select one of the 3’s from the array, then one 3 and all occurrences of (3-1) and (3+1) i.e 2 and 4 will be deleted from the array. Now we left with {3,3,5} elements in the array. Then again we select 3 in the next two steps and in both steps 3 will be deleted also (3-1) and (3+1) doesn't exist in the array so nothing extra to delete in both steps. Now we left with only {5} and in the next step, we select the 5 and delete it. Then the array becomes empty. Thus the sum of selected elements will be 3+3+3+5 = 14.

You are given an array/list 'NUM' of integers. You are supposed to rearrange the elements of the given 'NUM' so that after rearranging the given array/list there are no two adjacent elements present in the rearranged 'NUM' which will be the same.

For example:

Input: NUM[] = {1,1,1,2,2,2} 
Output: {1,2,1,2,1,2}
Note: {2,1,2,1,2,1} is also valid because there are no two adjacent which are the same.

Aahad and Harshit always have fun by solving problems. Harshit took a sorted array consisting of distinct integers and rotated it clockwise by an unknown amount. For example, he took a sorted array = [1, 2, 3, 4, 5] and if he rotates it by 2, then the array becomes: [4, 5, 1, 2, 3].

After rotating a sorted array, Aahad needs to answer Q queries asked by Harshit, each of them is described by one integer Q[i]. which Harshit wanted him to search in the array. For each query, if he found it, he had to shout the index of the number, otherwise, he had to shout -1.

For each query, you have to complete the given method where 'key' denotes Q[i]. If the key exists in the array, return the index of the 'key', otherwise, return -1.

Note:

Can you solve each query in O(logN) ?

You are given an array ‘ARR’ consisting of ‘N’ strings. Your task is to find the longest common prefix among all these strings. If there is no common prefix, you have to return an empty string.

A prefix of a string can be defined as a substring obtained after removing some or all characters from the end of the string.

For Example:

Consider ARR = [“coding”, ”codezen”, ”codingninja”, ”coders”]
The longest common prefix among all the given strings is “cod” as it is present as a prefix in all strings. Hence, the answer is “cod”.

You are given an array 'ARR' of distinct positive integers. You need to find all numbers that are in the range of the elements of the array, but not in the array. The missing elements should be printed in sorted order.

Example:

If the given array is [4, 2, 9] then you should print "3 5 6 7 8". As all these elements lie in the range but not present in the array.