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.
:)

n-th last element in the list

Given a singly linked list, find n-th element from the last.

The most obvious way is to traverse the list once and get its length say L. Then traverse again first L-n nodes to get to the n-th last node. This is linear in complexity but we need to traverse the list twice. Can we eliminate this?

We can, using extra pointer. Let's have a pointer to the list say *first and one more say *second. We traverse the list using *first till n nodes are traversed. Now imagine that at this moment we start traversing the list with second pointer, say *second. Then, by the time *first reaches towards the end of the list, *second will fall short by n nodes from the end of the list. That's precisely the node we want - n-th node from the end. So the solution is clear. After *first reaches the n-th node, start traversing with *second and continuing with *first till *first reached the last node.

Note: This will take care of the error in input when n > length of the list as *first will reach NULL sooner than expected.

Missing number in an array

Given an array of N elements which contain numbers from 1 to N+1 in random order, each only once and one of them missing, find the missing number in the best way you can.

Let's first see with an example that we have understood the question correctly. The array size is say, N=5, it contains numbers from {1,2,..,6} each except one exactly once, in random order - e.g. {2,3,1,5,6}. Given this, we have to find the missing number i.e. 4 here.
This problem seems quite easy and indeed it is! You know beforehand what the value of N is and you can traverse the array one by one, keeping track of which element you have seen till now. This requires additional storage and setting of flags per element i.e. theta(N) space. But, logically this works correct. At the end, you emit that number for which the "saw it" flag is not set.
Can we somehow eliminate this extra storage? This needs some extra insight in the problem statement. What if I tell you, the array has numbers from {2,5,7,9,15} and one of them is missing. The above approach of setting flags will work here also as long as you know the numbers that you expect to see. So, what is the difference that makes original problem a special case of this generic problem? As you might have noticed, the given array has a nice property. The elements are not arbitrary chosen but they all come from {1,..N}. Now, in order to remove the need of extra space, one has to think of aggregating the results in some way. Thus instead of storing per value, one flag and setting it, can we aggregate the information we have seen so far? Such aggregation will eliminate extra space requirement. One obvious way to aggregate is : take sum. And here comes the above mentioned property handy! We know that sum of first N numbers can be easily calculated as given in this. Call this S. Now traverse the array and keep the track of sum seen, call this S'. The missing number is S-S'!

Delete the given node in an SLL

Given a node in a singly linked list, and given no other node - not even header, can you delete this node?

Ans.- While deleting a node from a linked list, we need to point 'next' of previous node to the 'next' of current node and make the current node isolated and then free it. With singly linked list, we need to keep track of previous node in order to make above mentioned modifications. This is possible only when header node is provided so that we can traverse the list till this node. As header is not available and the list being singly linked, main point to note is: we can only traverse from the given node in forward direction. This leads us to the solution. We target next node. Copy next node's data to the current node and make current node point to next of next of current node. This way we have removed data to be deleted and next node is isolated in this process, so we then free it up.
Trick- This will not work for all cases. The constraint is in terms of the input. Can you identify it?
Ans.- Think what happens when the given node is the last node in the singly linked list.