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.
Tuesday, 8 December 2009
Monday, 7 December 2009
Must Read
This post will be kept updated with links as and when I find them. While browsing, if you come across any of the dangling / dead links or redirections, please let me know.
- A collection of dynamic programming
problems very well explained.
- A collection of dynamic programming
problems very well explained.
for loop in C
Following code has a bug. Can you find that out? Hint: Well, this code is intended to print "hi " **20** times, does it?
int i, n=20;
for (i=0; i < n; i--) { printf("hi "); }
If you have found the bug, can you now make it print "hi " 20 times by replacing one character.
Well, the answer is too simple (once known :D). Just a hint: Make sure you understand how for loop works, specially at the beginning of the loop.
(Spoiler alert: Solution in comment)
int i, n=20;
for (i=0; i < n; i--) { printf("hi "); }
If you have found the bug, can you now make it print "hi " 20 times by replacing one character.
Well, the answer is too simple (once known :D). Just a hint: Make sure you understand how for loop works, specially at the beginning of the loop.
(Spoiler alert: Solution in comment)
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!! :)
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
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!! :)
Thursday, 3 December 2009
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).
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).
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).
Tuesday, 1 December 2009
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'!
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'!
Multiply given number by 7..
Multiply given number by 7 without using multiplication operator.
Obvious answer: Add number to itself 7 times!
But, then think - why the Que asks you multiplying specifically by 7. The above trick of adding numbers is generic and can be applied for any multiplier other than 7. The trick here is as follows. If the given number is 'x', x*7 = x*(8-1) = x*8 - x. At this point, you might note that this involved multiplication again. But here is the main step - Multiplication by any number which is a power of 2, can be done easily by shifting the bits in the binary representation of the number. For binary representation, see this. And this gives the answer - Shift x's bits 3 positions to left and subtract x from it!
Obvious answer: Add number to itself 7 times!
But, then think - why the Que asks you multiplying specifically by 7. The above trick of adding numbers is generic and can be applied for any multiplier other than 7. The trick here is as follows. If the given number is 'x', x*7 = x*(8-1) = x*8 - x. At this point, you might note that this involved multiplication again. But here is the main step - Multiplication by any number which is a power of 2, can be done easily by shifting the bits in the binary representation of the number. For binary representation, see this. And this gives the answer - Shift x's bits 3 positions to left and subtract x from it!
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.
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.
Subscribe to:
Posts (Atom)