SDE

First, sort the array in non-increasing order. Then we will count the number of positive and negative integers.
Then swap the one negative and one positive number in the odd positions till we reach our condition.
This will rearrange the array elements because we are sorting the array and accessing the element from left to right according to our need.

Time Complexity: O(N*logN)

Space Complexity: O(1)

Create two array prefix and suffix of length n, i.e length of the original array, initialize prefix[0] = 1 and suffix[n-1] = 1 and also another array to store the product.
Traverse the array from second index to end.
For every index i update prefix[i] as prefix[i] = prefix[i-1] * array[i-1], i.e store the product upto i-1 index from the start of array.
Traverse the array from second last index to start.
For every index i update suffix[i] as suffix[i] = suffix[i+1] * array[i+1], i.e store the product upto i+1 index from the end of array
Traverse the array from start to end.
For every index i the output will be prefix[i] * suffix[i], the product of the array element except that element.

Time Complexity: O(n). 
The array needs to be traversed three times, so the time complexity is O(n).
Space Complexity: O(n). 
Two extra arrays and one array to store the output is needed so the space complexity is O(n)

Since we are given two sorted arrays, we can use the merging technique to get the final merged array. From this, we simply go to the k’th index.
Divide And Conquer Approach 
While the previous method works, can we make our algorithm more efficient? The answer is yes. By using a divide and conquer approach, similar to the one used in binary search, we can attempt to find the k’th element in a more efficient way.
Compare the middle elements of arrays arr1 and arr2, let us call these indices mid1 and mid2 respectively. Let us assume arr1[mid1] k, then clearly the elements after mid2 cannot be the required element. Set the last element of arr2 to be arr2[mid2].
In this way, define a new subproblem with half the size of one of the arrays.

Time Complexity: O(log n + log m)

Auxiliary Space: O(logn + logm)

The answer is 98 which is not intuitive. 
A uses the facts below to get 98. 

Consider the situation when A, B, and C die, only D and E are left. E knows that he will not get anything (D is senior and will make a distribution of (100, 0). So E would be fine with anything greater than 0.
Consider the situation when A and B die, C, D, and E are left. D knows that he will not get anything (C will make a distribution of (99, 0, 1)and E will vote in favor of C).
Consider the situation when A dies. B, C, D, and E are left. To survive, B only needs to give 1 coin to D. So distribution is (99, 0, 1, 0)
Similarly, A knows about point 3, so he just needs to give 1 coin to C and 1 coin to E to get them in favor. So distribution is (98, 0, 1, 0, 1).

The idea is to first sort the array and find the longest subarray with consecutive elements. 
After sorting the array and removing the multiple occurrences of elements, run a loop and keep a count and max (both initially zero). Run a loop from start to end and if the current element is not equal to the previous (element+1) then set the count to 1 else increase the count. Update max with a maximum of count and max.

This problem can be solved in O(n) time using an Efficient Solution. The idea is to use Hashing. We first insert all elements in a Set. Then check all the possible starts of consecutive subsequences.

Algorithm: 

Create an empty hash.
Insert all array elements to hash.
Do following for every element arr[i]
Check if this element is the starting point of a subsequence. To check this, simply look for arr[i] – 1 in the hash, if not found, then this is the first element a subsequence.
If this element is the first element, then count the number of elements in the consecutive starting with this element. Iterate from arr[i] + 1 till the last element that can be found.
If the count is more than the previous longest subsequence found, then update this.


Time complexity: O(nLogn). 
Time to sort the array is O(nlogn).
Auxiliary space : O(1). 
As no extra space is needed.

Approach: The idea is to traverse every array element and find the highest bars on the left and right sides. Take the smaller of two heights. The difference between the smaller height and height of the current element is the amount of water that can be stored in this array element.
Algorithm: 
Traverse the array from start to end.
For every element, traverse the array from start to that index and find the maximum height (a) and traverse the array from the current index to end, and find the maximum height (b).
The amount of water that will be stored in this column is min(a,b) – array[i], add this value to the total amount of water stored
Print the total amount of water stored.

We can implement the naive solution using recursion with the following optimal substructure property: 
Assuming that we already have k-1 partitions in place (using k-2 dividers), we now have to put the k-1 th divider to get k partitions. 
How can we do this? We can put the k-1 th divider between the i th and i+1 th element where i = 1 to n. Please note that putting it before the first element is the same as putting it after the last element.
The total cost of this arrangement can be calculated as the maximum of the following: 
a) The cost of the last partition: sum(Ai..An), where the k-1 th divider is 
before element i. 
b) The maximum cost of any partition already formed to the left of the k-1 th divider.
Here a) can be found out using a simple helper function to calculate sum 
of elements between two indices in the array. How to find out b) ? 
We can observe that b) actually is to place the k-2 separators as fairly as 
possible, so it is a subproblem of the given problem.