Interview Coding Problems: Linked Lists

Solving an Interview Coding Problem

This post is part of the Interview Coding Problems series. Throughout the posts, I am following the same guide for solving problems. Inspired by John Sonmez’s Pluralsight Course and Gayle Laakmann’s Cracking the Coding Interview: 150 Programming Questions and Solutions, I put together five steps to address every coding problem.

Question

Find the nth element from the end of a single-linked list.

I guess some of you already thought of recursion. It’s true that problems like this are usually solved easily recursively. This question is a good opportunity to discuss the pros and cons of that approach.

Guide

The Environment

Before we dive in and start to think about how to handle the question we must define the environment. We are practicing for technical interviews, so we have to keep two things in mind:

  1. Communication. Talk your thoughts even if you have not yet reached an optimal solution. If you are struggling a good interviewer may give you a hint. I find it useful to do that as I practice even if no one listens
  2. Practice on paper or whiteboard. The chances are that you are not going to write code on IDE through the interview. I know it’s not easy and that’s why you should practice it.

Now, let’s dive in.

Step 1: Understand the question.

According to John Sonmez, this is the main reason for failure. The first thing you want to do is to read through the question as many times as it takes to understand it. You wouldn’t want to start solving the wrong problem.

In many occasions, the questions are not very clear. You can ask the interviewer for clarifications and assumptions that have to be made in order to solve it. Sometimes asking the right questions is part of the solution.

On this particular problem, some good questions are:

  • Can the list nodes be fewer than n? – No
  • Can we use recursion? -Yes
  • Can we use extra variables? -Yes

Keep in mind that questions like this might affect on a big scale our code.

Step 2: Design a solution

Most of the times the design won’t just pop out in your mind. A good beginning towards the right design would be to start with simple examples. On this particular problem, we can think of a list of 10 nodes and let the n be 7. We can immediately answer 3 if the first node starts at 1.

If this was a double-linked list the solution would be obvious. In a single-linked list, however, we have to find a way to keep track of the distance from the last node of the list. As we can traverse the list only from the start a simple counter wouldn’t be so helpful.

Simplest Solution

The simplest way to find the nth element from the end of the list is to find its size k and then count kn from the first node. This means that we have to traverse all the nodes to find out the size k and then start again until we reach the kn node. With this approach, we do not use any space except a counter variable and the worst case time complexity is O(2k) (when n is the last node).

Even if you know that maybe there is a better way to implement it, you should speak your mind. Say why you think that there is a better way and if you know the complexity of your solution even better. The interviewer might share a tip if he/she sees that you are on the right track.

Finding A Better Solution

So, can we find a better way to implement our solution? That’s what the interviewer wants to eventually see.

I mentioned earlier that this problem is a good opportunity to compare recursion and iteration. In order to accomplish that we will try to solve it both ways.

  • Iteration:

The main problem with our simple approach is that we have to traverse the list two times. The first to find the size of the list and the second to get the element we want. Is there a way to traverse the list only once and get the nth from the end? Remember, we can use extra variables. What if we keep two pointers pointing at the first node of the list and start the second one when the first one reaches the nth node from the start? Then we can continue until the first one reaches the end. The second pointer will have traversed knodes.

  • Recursion:

Recursion for this particular problem is a little bit tricky. We can traverse the list only from start to end which can be easily done by recursively getting the next node. We need to find a way to get the value we need while returning from these recursive calls.  To be able to get the nth element from the end of the list we will need a recursive function that will accept the node, the and a counter as parameters.

Step 3: Pseudocode

The first step is the pseudocode. Many young developers skip this part, but I think it’s an essential step. It makes writing the actual code much easier.

  • Iteration:

Since we know that the cannot be less than the list size we don’t need to check for that.

List of nodes.
pointer1 pointing to the first node.
pointer2 pointing to the first node.
For n times:
    move pointer1 to the next node.
While pointer1 has next node:
    move pointer1 to the next node.
    move pointer2 to the next node.
return the node of pointer2.
  • Recursion:

The recursion implementation needs some calculations after the recursive call to our function so we can check if the value that is being returned is the node that we need to return. The advantage of recursion is that in some problems it’s more readable than iteration because it follows the programmer’s approach to the solution.

List of nodes.
findByRecursion(node, n, counter):
    if node has next:
        result = findByRecursion(next node, n, coutner+1)
    else:
        if n = 0 return counter else return -counter
    if result < 0 and result + counter = -n:
        return counter
    else return result

Step 4: Code

After writing the pseudocode down and checking your assumptions it’s time to write your actual code. Having a correct pseudocode this should be the easiest part, but keep in mind that you are probably going to be writing this on paper.

For this problem, I used a simple list implementation that you can check here.

  • Iteration:
public static Node findByIteration(Node first, int n) {
        Node iterator1 = first;
        Node iterator2 = first;
        for(int i = 0; i < n; i++) {
            iterator1 = iterator1.getNext();
        }
        while (iterator1.hasNext()) {
            iterator1 = iterator1.getNext();
            iterator2 = iterator2.getNext();
        }
        return iterator2;
    }
  • Recursion:
public static int findByRecursion(Node node, int n, int counter) {
    	int result;
	    if (node != null && node.hasNext()) {
		    result = findByRecursion(node.getNext(), n, counter + 1);
	    }
	    else {
		    return n == 0 ? counter : -counter;
	    }
	    if (result < 0 && result + counter == -n)
		    return counter;
	    return result;
    }

The most important drawback of recursion is that every call to the function allocates a stack frame. This means that if many calls are made we might get a stack overflow error. A usual way to optimize the recursion is to make sure that the recursive call is the last command in the function. This is called tail recursion and many compilers won’t allocate a new stack frame for a tail call. In Java, however, there is no tail call optimization so we don’t expect to get any benefits.

Step 5: Testing

For the final part, we have to show that we know how to test cover our code. This should not be a difficult task since we ought to have already thought corner cases while searching for our optimal implementation.

For the tests, we are utilizing the helper functions (getSize(), etc) that we have in our SingledLinkedList implementation, but we could also put raw numbers. This is also done in order to be able to compare easily iteration to recursion by just changing the list size in the setUp() method.

SingleLinkedList list;

    public void setUp() {
	    list = new SingleLinkedList();
	    for (Integer i = 1; i <= 10; i++) {
		    list.add(i.toString());
	    }
    }

	@Test
    public void testIterator() {
    	int n = 3;
        Node nthFromLast = Problem2.findByIteration(list.getFirst(), n);
	    assertEquals(list.get(list.getSize() - n).getData(), nthFromLast.getData());
    }

	@Test
	public void testIteratorFirst() {
		Node firstFromLast = Problem2.findByIteration(list.getFirst(), 0);
		assertEquals(list.get(list.getSize()).getData(), firstFromLast.getData());
	}

	@Test
	public void testIteratorLast() {
		Node lastFromLast = Problem2.findByIteration(list.getFirst(), list.getSize());
		assertEquals(list.getFirst().getData(), lastFromLast.getData());
	}

	@Test
	public void testRecursion() {
    	int n = 3;
		int nthFromLast = Problem2.findByRecursion(list.getFirst(), n, 0);
		assertEquals(list.get(list.getSize() - n).getData(), list.get(nthFromLast).getData());
	}

	@Test
	public void testRecursionFirst() {
		int nthFromLast = Problem2.findByRecursion(list.getFirst(), 0, 0);
		assertEquals(list.get(list.getSize()).getData(), list.get(nthFromLast).getData());
	}

	@Test
	public void testRecursionLast() {
		int nthFromLast = Problem2.findByRecursion(list.getFirst(), list.getSize(), 0);
		assertEquals(list.getFirst().getData(), list.get(nthFromLast).getData());
	}

Running the above tests will actually not show any difference between iteration and recursion for small list sizes, but it will for bigger ones. If you try a list above with more than 1000 nodes you will probably start having some of the recursion tests throwing stack overflow errors.

Conclusion

For this problem, we tried two different implementations and had the opportunity to compare iteration and recursion. If you are programming in Java the odds are that most of the times iteration will be the best solution. There are cases though that recursion might make more sense and make the code easier to maintain There are even languages that heavily depend on recursive calls like Prolog and Haskell.

Personally, I always try to find an iterative solution first even for problems that you might be tempted to use recursion.

You can find the code for this problem here and the tests here.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.