• Given a linked list how can you find the 5th last element ? The general version of the question would ask to find the nth last element of the linked list.

This is a common question on programming interviews and is sort of a trick question.

There are two ways of solving this question, one which is the usual accepted answer the second which you can mention to your interviewer to have an edge on other candidates. Let's start with the first answer which is usually expected.

If you are given a linked list, you would have to traverse it to get to the nth last element, however there's no way of knowing when the end of the linked list occurs until you actually hit the end of the linked list which is usually detected by the following if condition:

if(ptr->next == NULL){
  cout<<"You reached end of list"<<endl;
}

The problem occurs that if we hit the end of the linked list we can't go back to the nth last element since there are no back pointers. So this requires us to keep a track of previous elements seen. Let us assume that we are trying to find the 5th last element of the linked list. One way to do this is to create another pointer in addition to the one we use to traverse the linked list. We only start off this second pointer to traverse the linked list once the traverser pointer has already traversed the first 5 elements of the linked list. Moreover, we then always advance our second pointer by one element whenever we advance our traverser pointer by one element.

Note that in this scheme our traverser pointer will always be ahead of our second pointer by five elements. Bang ! that is what we exactly want! Note that when the traverser pointer reaches the end of the linked list our second pointer would be exactly five elements behind our traverser pointer and would in fact be pointing at the 5th last element.

This is the usual answer being sought by the interviewers however note that this requires us to traverse the entire linked list which means that if there are n elements in the linked list the time complexity of this scheme would be O(n).

Is there a way to do better than this ? Possibly O(1). Note that there is no magic in computers, if you want a better time complexity you would have to allocate more space or be smarter about your algorithms.

One possible way is to keep track of the nth element when you are actually creating the linked list. There are also two possible ways to construct a linked list. One is to add the new element at the end of the list and the other is to add the element at the start of the list. Let us try to achieve O(1) time by adding each new element at the beginning of the linked list.

Say we are again trying to find the 5th last element. We will always keep a count of the number of elements in the linked list. Note that as long as the number of elements in the linked list are less than 5 we don't have a 5th last element. If the linked list is exactly five elements long then the first element is also the 5th last element of the linked list. And if the linked list is more than 5 elements long then there will be additional element/elements behind the 5th last element.

The trick is that as we are adding elements in our linked list we immediately have a pointer point to the element that is added as the 5th element of the list. Note that even as more elements are added to the start of the list our pointer will keep pointing correctly to the 5th last element of the linked list. Thus at no additional cost we are able to track the nth last element. However note that this question becomes more complicated if deletions are allowed in the linked list.

If the deletions occur before the 5th last element in the list, it doesn't affect us but if a deletion takes place at or after the 5th last element then we have to update our 5th last element. Furthermore if successive deletions reduce our linked list to less than 5 elements then we can set our 5th last element pointer to NULL and wait for atleast 5 elements to be added.

Now to cater for the updates try to understand what happens when we make a deletion at or after the 5th last element. The only change is that our 5th last element would move one element BEHIND our current 5th last element. However since there are no back pointers we can't update our 5th last element pointer to the new 5th last element.

We can solve this problem by creating a hash table that given an element's address returns us back the address of the element immediately behind. Note that it is very easy to create this hash table at the same time we create the linked list. Similarly this hash table can be easily updated if any deletions occur. I wouldn't go into the details of the hash table maintainence and creation for the sake of brevity.

So once we are making a deletion we have to check if we are past our 5th last element or not. This is easy since deletion requires traversing the linked list anways so it can be checked along the way if we are past our 5th last element. If we are, we set a flag so that we can remember to update both the hash table for the element that is being deleted and our 5th last element pointer.

Say our flag is set then we know for sure that the new 5th last element is the element immediately behind the element to which our pointer currently points to. We simply send the address of our current 5th last element to the hash table which returns us with the address of the element immediately behind and we set our pointer with this returned address. Now for the elment that is being deleted we simply remove it's entry from the hash table and we update the previous address of the element ahead of it with the address of the element which is immediately behind. All this would take constant time if the hash function hashes without any collisions. Thus the overall time for keeping track of the 5th last element even with a dynamically increasing and decreaing linked list is still O(1) or constant time.

However, it is a very good idea to mention to your interviewer the pitfalls of this approach. One very obvious is the size of the hash table, which would be just as big as the original linked list. Note that candidates often ignore space complexity and focus only on the time complexity. As a last note, it is highly unlikely you will ever use a hash table for this purpose but this is the simplest approach to achieving constant time. If constant time is really needed in a practical situation it would probably involve some complex data structures to reduce the space complexity.