Software Engineer Interview Questions to Know (Entry Level) — LinkedLists

If you’ve just stumbled onto this series, make sure to check out the introduction here.

Question 1: Given a node in a singly linked LinkedList, determine if the LinkedList is circular.

Variations

• Determine if there is a cycle/loop in a singly linked LinkedList.
• What is the fast-pointer, slow-pointer technique?

What They’re Really Asking

• Do you understand the concept of a LinkedList? Do you know how to traverse a LinkedList?
• The fast-pointer, slow-pointer technique is used relatively frequently in LinkedList questions. Have you worked with LinkedList algorithms before?
• Although the optimal solution has O(N) runtime complexity and constant memory complexity, a very common solution has O(N) runtime and memory complexity. Can you iteratively develop your code to find this optimal solution?
• This question can have different solutions for a singly linked list and a doubly linked list. Do you know the different types of LinkedLists? Do you understand how this would affect the solution?

Tools for Our Answer

• A LinkedList is an abstract data type that stores nodes in a linear order. Each node has some information (i.e. a value, String, etc.) and a reference to the next node. If there is no next node, this reference is null. The beginning node is defined as the head node.
• Nodes in a LinkedList are stored at non-contiguous locations in memory. A LinkedList does not support indexing or constant time access to an arbitrary element. However, the size can grow in constant time and elements can be inserted/deleted in constant time as well.

Node Class in Java with Linked List Creation. Code source here.

• A LinkedList can be singly linked or doubly linked. A singly linked this is described and implemented above. A doubly linked list has a reference to the next node and a reference to the previous node.

Singly and Doubly Linked List

• A LinkedList is circular if a path exists from any node to itself. Some examples of this are shown below.

Examples of Circularly Linked Lists

• It is important to note that we are given any node in the LinkedList. We are not necessarily given the head node or even a node guaranteed to be in the loop. Note also that in the second example, we would be given 2 or 3 and we would not be able to view 1,4, or 5. They are left for explanatory purposes.
• It is equivalent to say a circular LinkedList contains a loop or a cycle. The difference is semantics.
• One solution would be to begin at our current node and store each value in a HashMap. If we try to store a node in our HashMap and it already exists, we know we have seen this node before. Therefore, the LinkedList is circular. This is shown below.

Solution Using HashMap. Code source here.

• However, this has O(N) memory complexity. We can do better. We are looking for collisions here. We’ll define a collision here as two variables pointing to (referencing) the same object.
• Suppose our LinkedList is circular. We know we have a finite number of nodes effectively repeated infinitely. We can leverage this fact using Floyd’s Tortoise and Hare Algorithm.
• This algorithm uses two pointers — a fast pointer (the hare) and a slow pointer (the tortoise). The fast pointer moves two nodes at a time (i.e. node = node.next.next). The slow pointer moves one node at a time (i.e. node= node.next). If the LinkedList is non-circular, the fast pointer will find a null value. If it is not, the fast and slow pointers will eventually point to the same object.
• For those with some background in modular arithmetic and elementary number theory, a proof of the above is written below.

Proof that Floyd’s Algorithm Guarantees a Collison. See an additional proof here.

• Great! Now we can implement the algorithm as below. We check if our fast pointer is ever null and we check if our fast and slow pointers ever collide, as shown below.

Floyd’s Tortoise and Hare / Slow and Fast Pointer Algorithm. Code source here.

My Answer

In a singly linked LinkedList, a naive solution would be to iterate through the LinkedList and store each solution in a HashMap. At each node, we can check if our HashMap already contains this value. If it does, we know we have found a cycle. If we reach a null value, we know our LinkedList does not have a cycle. This is shown in the code below.

Naive Solution using HashMap

This has both O(N) memory and space complexity where N is the number of distinct elements in our LinkedList. However, we can use Floyd’s Tortoise and Hare Algorithm to detect a cycle. This maintains our time complexity but reduces our memory complexity to O(1).

Floyd’s Algorithm maintains two pointers — a slow pointer and a fast pointer. The slow pointer (“the tortoise”) iterates through the LinkedList one node at a time. The fast pointer (“the hare”) iterates through the LinkedList two nodes at a time. Using modular arithmetic and number theory, we can show this guarantees a collision. An implementation of Floyd’s Algorithm is below. Similarly to the above, if our fast pointer reaches a null value, we know our LinkedList is not circular.

Implementation of Floyd’s Algorithm

This is an optimal solution to our problem in terms of asymptotic runtime and memory complexity.

Concluding Note

One improvement to the HashMap solution above is to forgo the HashMap and simply store the memory address of the first node in the LinkedList. At first glance, this ostensibly works and runs in O(1) memory. But suppose we are given the head node of the LinkedList below. We don’t know which nodes are in the cycle and which ones aren’t. We cannot guarantee we are storing the address of a node in the cycle in the LinkedList. We can only do this by storing all N nodes — making our memory complexity O(N).

Example Circular Linked List

The Tortoise and Hare Algorithm comes up many times in LinkedList questions. For example, the same algorithm can be used to find the middle element of a LinkedList. Simply iterate down the LinkedList until your fast pointer reaches the end. At this point, your slow pointer will be in the middle. Floyd’s Algorithm is a great one to know when dealing with LinkedList questions.

Question 2: Given the head node in a singly linked LinkedList, reverse the LinkedList.

Variations

• Reverse a singly linked LinkedList iteratively and recursively.

What They’re Really Asking

• Do you understand the concept of a LinkedList? Do you know how to traverse a LinkedList?
• Do you understand pointers well? Do you understand how assigning and updating references in memory can be used to solve this problem?

Tools for Our Answer

• We’ll use the same definitions for a LinkedList as above. As a refresher, a LinkedList is a series of nodes, with a node as defined below.

Node Class used in LinkedList

• For this question, we’ll be dealing with a singly linked list. This problem is trivial for a doubly linked list as it is already reversed (simply traverse to the end of the LinkedList and return the last node).
• We are going to make use of three additional nodes: curr, prev, and next. As you may guess, this represents the current node, previous node, and next node in the LinkedList. We start at the head of our LinkedList and define curr and next as expected. Since we are at the head of our LinkedList, we define prev as null.
• We’ll also need to ensure our parameter head and head.next are non-null. If they are null, we can simply return head. The initial variable definition is below.

Definition of Variables

• The next step is to iterate through our LinkedList and update our values appropriately. We want our curr node to now point backward to prev. Then we can simply move all our variables up one node. The implementation is below.

Iteration and Updating to Reverse LinkedList. Code source here.

• Let’s take a look at a toy example of a LinkedList with 3 nodes.

• And there it is — a fully reversed LinkedList!
• This problem can also be solved recursively. Contributor DPGoel on GeeksForGeeks has a great article here for those interested.
• Note that a recursive algorithm would have to make calls to the Call Stack. These calls use more memory than our iterative algorithm. Since both algorithms run in O(N) time, our iterative solution is more optimal. Additionally, it is more clearly understood and remembered.

My Answer

To solve this problem, we’ll need to use 3 additional references to our LinkedList — curr, prev, and next. This represents the current node, previous node, and next node in the LinkedList. We’ll build a while loop to iterate over our LinkedList. For each node, we are going to assign curr.next to our prev reference. We will then move curr, prev, and next to the next Node in our LinkedList. We then add an additional if statement at the beginning of our code to handle the case when we are given a null node or only one node (i.e. one that cannot be reversed).

The above is implemented in the code below.

Final Implementation of Reversing LinkedList. Code source here.

Concluding Note

When dealing with LinkedList problems, always always always draw a picture. When you are dealing with multiple references and variables, problems can become confusing and overwhelming quickly. I’ve answered this question in multiple interviews and written the solution on LeetCode and HackerRank many times. But even as I began to write this article, I had to take out a notebook and draw an example LinkedList.

One trick to remember the code inside the while loop above is to break it into line 1 and lines 2–4. In line 1, we reverse the list. In lines 2–4, we move our references down the list in order. We move prev, then curr, then next. Although it is tempting, do not memorize this algorithm. Just think about what you are doing and you’ll never get it wrong.

Check out Part 5 here!

Questions? Comments? Send me an email at andrew.oliver.medium@gmail.com! I’d love to hear from you.