top k from n (k << n)

Bhai was asked this problem in one of the interviews he faced.

Given n objects and associated scores, find top k objects s.t. k is much smaller compared to n.

The most trivial approach is of course to sort n objects based on their scores and pick top k. The best known comparison based sort will do this in O(n log n) with additional pass to pick top k. And of course, this is not what is expected! We need complexity to be lower than O(n log n).

Let's focus on last part of the problem statement. What additional benefit does it give us to know that k << n? One obvious thing that comes to mind is, we are interested in correct ordering of just top k objects, remaining n-k could be unordered at the benefit of having lower complexity. Thinking in the same direction, one can try to pick k such objects such that remaining n-k are virtually ignored! But, there has to be some mechanism to pick top k. The same thing considered in opposite way will give us better insights - i.e. we get lower complexity at the expense of neglecting ordering of non-top n-k objects; meaning we don't care about them, specifically their position in ordered list.

So, is there any way where we can selectively pick elements s.t. the highest score is picked first then the second highest scored and so on? well.. this suggests none other than a max-heap! a max-heap allows you to get maximum element one at a time with delete operation. Let's see the algorithm.

1. Build heap of n objects given.
2. for i=1 to k do
1. get max element (delete from heap)

Let's see the complexity if we are doing any better than O(n log n). Step 1 above takes O(n). Refer Complexity of building heap for analysis. Step 2.1 takes O(log n) and thus step 2 takes O(k log n). In first read, one might think the complexity is O(n) + O(k log n). Let's analyze more with examples.

• n = 1024, k = 10
• n+k log n ~ 1024 + 10 * 10 ~ 1024 -> O(n)

• n = 1024, k = 200
• n+k log n ~ 1024 + 200 * 10 ~ 2000 -> O(k log n) which will approach O(n log n) as k -> n

Of course, if k -> n, this algorithm will degenerate to O(n log n)  but in given setting where k << n, case 1 above will result in linear time algorithm.
:)

Maximum contiguous subsequence

Given an array of N numbers (positive, zero, negative), find maximum contiguous subsequence i.e. a subsequence which is contiguous and which has maximum sum i.e. mathematically, sum of k elements A[k] where k ranges from i to j, such that 0<=i<=j<=N-1, is maximized.

Let's take an example. If A is {2,4,1,5,6,7}, well! the answer is the whole array itself. And that's why we need to consider a generalized case in which the array contains positive as well as negative elements. Similarly, for the array A={-2,-10,-9,-1}, the sum better be zero than negative and the the answer is empty subsequence. Thus, these two are degenerate cases.

Now, let's consider the general case. We can come up with a trivial algorithm as follows. We want to find a subsequence of the form 0<=i<=j<=N-1, thus we can straightaway write 2 loops as follows.

for i=0 to N-1
       for j=i to N-1
             keep sum of A[i] through A[j], keep track of max sum seen so far and corresponding i and j values
       end for
end for

As one can see, this is O(N^3) algorithm. If you think it's O(N^2), please take a look at the step in which we compute the sum. This sum needs to be computed over all subintervals and thus it causes another for loop, giving rise to the complexity of O(N^3).

Now, of course the question is - Can we do better? We can definitely do this in O(N^2) as you must have realized by now. (I took quite a lot of time to get to this :D) Basically, we can eliminate the innermost loop over K using following fact. If we denote sum of A[i] through A[j] as Sum(i,j) then we can write
       sum(i,j+1) = sun(i,j)+A[j+1]
Thus, we need not go through all values again and we save one loop here, thus getting O(N^2) complexity.

We can still do better btw! At this moment I myself asked a question - how much better? Can we go sub linear? And I think, we cannot. The reason is - as the input array is not sorted or in any order, we cannot judge for more elements based on small number of elements. Remember what we do in binary search - comparison with one element at the middle (small number of elements) gives us an indication of half of the array (more number of elements) being useless for further steps. Such indication we cannot get here and thus we HAVE TO look at EVERY element at least once and as we will see - also at most once! Thus, we cannot hope for sub linear complexity but it has to be linear.

The algorithm, which I am not writing here is of the complexity O(N). It can be arrived at by two different methods. The underlying principle is the same for both the methods. The hints for the two methods are as follows. I think, if you get one of them, the other one will be trivial.
1. Biggest hint for method 1: The array contains negative elements too and any negative sum is worse than sum=0
2. If you have solved this by method 1, then this hint may be redundant: Use dynamic programming

nJoy!! :)

Rotated sorted array

Part A: Given a sorted array which is rotated either to the left or to the right by k positions (0<=k<=n-1), find the maximum element. Trivial solution:
Check for each possible k, whether it is the maximum element by checking adjacent values i.e. a[k-1], a[k] and a[k+1] circularly (meaning, for k=0, check a[n-1], a[0] and a[1]). This is obviously O(n) due to k's range and because 3 comparisons per k can be considered as O(1) being constant time access to array elements. Thus, of course we aim at sub linear time.

So the main issue is - how to reduce problem size so that we solve smaller and smaller problems, discarding some part of the input and get quickly to the problem of size small enough (ideally 1). What if we have the middle element, i.e. a[m]? In order to decide which part to discard, one must be able to visualize the rotated sorted array, which is shown as follows. Let the new index of maximum element be k.


Now, one can see that m will always lie on upward slope and thus slope trick will not work. But, we can now distinguish between left and right part around k as follows. If m<=k, m will always be more than the first element in the rotated array, because the sorted order is retained. Thus, by comparing a[m] and a[i], one can easily decide which part to throw. If a[m] >= a[i] we can throw left half else right half. Once we reduce problem size to 1, m and k collide. This works in O(log n).

Array with a mountain shape

Given an array in which initially elements start increasing till some index k and then they decrease. Find k.

Of course this asks us to find k in sub linear time. Otherwise, the most obvious solution is to check every element till elements increase and then at first drop in value, you get k. Sub linear acts as a hint for logarithmic. Logarithmic gives hint for dividing and throwing away some part, so that we reach a singleton or small enough set quickly. Let's see whether we can discard some part of the array. What if we pick the middle as we do in binary search? This gives us m=(i+j)/2 and m<=k or m>k. If we can somehow establish this relation between m and k (note: k is unknown, we have to find it), we can throw away the remaining part. How can we do this then? We know that k is the index such that on its left, the line plot of the array is ascending and on its right, it is descending. This means, if we are on left of k, we are on upward slope as against when we are on the right part of k. This hint is enough I guess. Once we get m, check a[m-1], a[m] and a[m+1] to get an indication about the region of slope where m belongs to, by comparison. Once we know that we are on upward slope, we know that m<=k, so we discard this part. Similarly for the case when m>k. Once we reduce problem size from n to n/2 at every iteration, we are in logarithmic space. Thus the algorithm performs in O(log n).