Are you confused about selecting a job? Do you want to know which field best suits your talents? Wisdom jobs is all about training people to find better jobs that improve their skills. Being an expert at handling different programming language operations, Linked list jobs are the right choice for you. A linked list is defined as a data structure that is formed by linearly collecting data elements but each element is defined as a separate object ( node). Each node consists of two items- one is data and the other is a reference to next object. Wisdomjobs.com has constructed LinkedList job interview questions and answers page to help you enhance your innate skills and to score an interview. Register to our job portal to find necessary information needed to grab a job.
Question 1. How To Find Middle Element Of A Singly Linked List In One Pass?
Answer :
You should clarify what does mean by one pass in this question. If Interviewer says that you cannot loop twice and you just have to use one loop, then you can use the two pointer approach to solving this problem. In the two pointer approach, you have two pointers, fast and slow. In each step, the fast pointer moves two nodes, while slow pointer just steps one node. So, when fast pointer will point to the last node i.e. where next node is null, the slow pointer will be pointing to the middle node of the linked list.
Answer :
This is another interesting linked list problem which can be solved using the two pointer approach discussed in the first question. This is also known as tortoise and hare algorithm. Basically, you have two pointers fast and slow and they move with different speed i.e. fast moves 2 notes in each iteration and slow moves one node. If linked list contains cycle then at some point in time, both fast and slow pointer will meet and point to the same node, if this didn't happen and one of the pointer reaches the end of linked list means linked list doesn't contain any loop.
Question 3. How To Reverse A Linked List In Java?
Answer :
This is probably the most popular linked list interview question, which is asked to both junior programmers with 2 to 3 years of experience and senior developers containing 4 to 6 years of experience. Some of you may think this is the simplest of linked list problem but when you actually go doing it, you will be stuck and many places. The simplest approach to solving this problem is by using recursion because linked list is a recursive data structure as shown in the solution article.
Question 4. How To Reverse A Singly Linked List Without Recursion In Java?
Answer :
The previously linked list interview question becomes even more challenging when the interviewer asked you to solve the problem without recursion. you need to keep reversing links on the node until you reach the end, which will then become new head.
Question 5. How Would You Remove A Node From A Doubly Linked List?
Answer :
This is one of the frequently asked linked list interview questions, mostly asked freshers and computer science college graduates. In order to remove a node from the doubly linked list, you need to go through that node and then change the links so that it points to the next node. Removing nodes from head and tail is easy in linked list but removing a node from the middle of the linked list requires you to travel to the node hence take O(n) time. If you want to learn more about basic operations on linked list data structure, please read a good book on Data Structure and Algorithms e.g. Introduction to Algorithms by Thomas H. Carmen.
Question 6. Write A Program To Convert A Binary Tree Into A Doubly Linked List?
Answer :
This problem is opposite of question 25 where you need to write a program to convert a double linked list to the balanced binary tree. The left and right pointers in nodes of a binary tree will be used as previous and next pointers respectively in converted doubly linked list. The order of nodes in the doubly linked list must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in the binary tree) must be the head node of the doubly linked list.
Question 7. How To Remove Duplicate Nodes In An Unsorted Linked List?
Answer :
This problem is similar earlier problems related to String and arrays i.e. removing duplicate elements in an array (see) or removing duplicate characters from given String (see here). You need to write a program to remove all duplicate nodes from an unsorted linked list in Java. For example if the linked list is 22->21->22->31->41->23->21 then your program should convert the list to 22->21->31->41->23. This question is also given in the famous Cracking the Coding Interview book so you can look at their solution as well.
Question 8. How To Find The Length Of A Singly Linked List In Java?
Answer :
This is one of the easiest linked list questions you can expect in an interview. That's why it is often asked on telephonic interviews. In order to find the length of linked list, you can iterate over linked list and keep a count of nodes until you reach the end of the linked list where next node will be null. The value of the counter is the length of linked list.
Question 9. Write Code To Print Out The Data Stored In Each Node In A Singly Linked List?
Answer :
This is another simplest question which just tests whether you know linked list traversal or not. You can get the value from the node by accessing its value property, you just need to traverse through linked list, access each node and print value.
Answer :
You can print nodes of linked list in reverse order by using Stack data structure in two steps:
Step 1: Traverse the linked list from the head and put the value of each node into Stack until you reach the last node. This will take O(n) time.
Step 2: Pop the elements out from the stack and print. This will take O(1) time.
Input: 1->2->3
Output: 3 2 1
Question 11. How To Find The Kith Node From The End In A Singly Linked List?
Answer :
Question 12. How To Delete Alternate Nodes Of A Linked List?
Answer :
You are given a Singly Linked List. Starting from the second node delete all alternate nodes of it. For example, if the given linked list is 1->4->8->10->15 then your function should convert it to 1->8->15.
Question 13. What Is The Difference Between An Array And Linked List In Java?
Answer :
This is one of the frequently asked linked list questions on programming job interviews. There is much difference between an array and linked list but the most important is how they are stored into the memory location. Array stores elements at the adjacent memory location, while linked list stores them at scattered, which means searching is easy in an array and difficult in linked list but adding and removing an element from start and end is easy in linked list. See here for more differences between array and linked list.
Question 14. Difference Between Singly And Doubly Linked List In Java?
Answer :
The key difference between a single and double linked list data structure in java is that singly linked list only contains pointer to next node, which means you can only traverse in one direction i.e. forward, but doubly linked list contains two points, both previous and next nodes, hence you can traverse to both forward and backward direction.
Question 15. How To Implement A Linked List Using Generics In Java?
Answer :
It's not easy to implement a linked using generics in Java, especially if have not written any parametric or generic class, but it's a good exercise to get familiar with both linked list data structure as well generics in Java.
Question 16. How To Insert A Node At The Beginning Of The List?
Answer :
Inserting a node at the beginning of the list is probably the easiest of all operations. Let’s talk about what is involved here referring to the diagram above. This involves creating a new node (with the new data, say int 10), making its link point to the current first node pointed to by head (data value 2) and lasting changing head to point to this new node. Simple, right.
Question 17. How To Insert A Node At The End Of The List?
Answer :
This case is a little bit more evolved. If you have a tail pointer, it is as easy as inserting at the beginning of the list. If you do not have a tail pointer, you will have to create the new node, traverse the list till you reach the end (i.e. the next pointer is NULL) and then make that last node’s next pointer point to the new node.
Question 18. How Do You Traverse A Linked List In Java?
Answer :
There are multiple ways to traverse a linked list in Java e.g. you can use traditional for, while, or do-while loop and go through the linked list until you reach the end of the linked list. Alternatively, you can use enhanced for loop of Java 1.5 or Iterator to traverse through a linked list in Java. From JDK 8 onwards, you can also use java.util.stream.Stream for traversing a linked list.
Question 19. How Do You Find The Sum Of Two Linked List Using Stack In Java?
Answer :
This is a relatively difficult linked questions when you compare this to reversing a linked list or adding/removing elements from the linked list. In order to calculate the sum of linked list, you calculate the sum of values held at nodes in the same position, for example, you add values at first node on both the linked list to find the first node of resultant linked list. If the length of both linked list is not same then you only add elements from shorter linked list and just copy values for remaining nodes from the long list.
Answer :
This is one of the difficult linked list questions you will find on interviews. You need to write a program to convert a given doubly Linked, which is sorted in ascending order to construct a Balanced Binary Search Tree which has same the values as the given doubly linked list. The challenge is usually increased by putting a restriction to construct the BST in-place i.e. no new node should be allocated for tree conversion)
Input: A Doubly linked list 10 20 30 40 50 60 70
Output: A balanced binary search tree BST
40
/
20 60
/ /
10 30 40 70
Question 21. How Do You Calculate The Sum Of Two Linked List Using Recursion In Java?
Answer :
This is another interesting linked list based algorithm question for Java programmers. You cannot use the java.util.LinkdList class but you have to write your own linked list implementation in Java to solve this problem.
Question 22. How To Implement Lru Cache In Java Using Linked List?
Answer :
An LRU cache is the cache where you remove least recently used an element when the cache is full or about to fill. It's relatively easy in Java if you are allowed to use one of the Collection class e.g. you can use a LinkedHashMap to implement LRU cache in Java, but you should also prepare how you can use a doubly linked list to create an LRU cache.
Question 23. How Do You Reverse Every Alternate K Nodes Of A Linked List In Java?
Answer :
This is another difficult linked list algorithm question which is mostly asked to experienced programmers e.g. programmer having 3 to 6 years of experience. You have been given a singly linked list and you need to write a function to reverse every alternate k nodes (where k is an input to the function) in an efficient way. You also need to calculate the time and space complexity of your algorithm.
Example:
Inputs: 1->2->3->4->5->6->7->8->9->NULL and k = 3
Output: 3->2->1->4->5->6->9->8->7->NULL.
Question 24. How Do Add Two Numbers Represented Using Linked List In Java?
Answer :
You have given two numbers represented by two linked lists, write a function that returns the sum of these two lists. The sum list is linked list representation of addition of two input numbers. There are two restrictions to solve this problem i.e. you cannot modify the lists and you are not allowed to use explicit extra space. You can use recursion to solve this problem.
Input:
First List: 1->2->3 // represents number 123
Second List: 9->9->9 // represents number 999
Output:
Resultant list: 1->1->2->2 // represents number 1122
That's all about some of the frequently asked linked list based coding questions from Programming Interviews. As I said, linked list is one of the essential data structure and you should have a good command over it, especially if you are preparing for Google or Amazon job interview. Once you solve these problems, you can try solving questions given in Algorithm Design Manual by Steven S. Skiena. They are tougher but can really improve your data structure and algorithm skills.
Question 25. What Is A Linked List?
Answer :
Linked list is an ordered set of data elements, each containing a link to its successor (and typically its predecessor).
Question 26. How Many Pointers Are Required To Implement A Simple Linked List?
Answer :
You can find generally 3 pointers engaged:
Question 27. How Many Types Of Linked Lists Are There?
Answer :
Singly linked list, doubly linked list, multiply linked list, Circular Linked list.
Question 28. How To Represent A Linked List Node?
Answer :
The simplest representation of a linked list node is wrapping the data and the link using a typedef structure and giving the structure as a Node pointer that points to the next node. An example representation in C is
/*ll stands for linked list*/
typedef struct ll
{
int data;
struct ll *next;
} Node;
Question 29. Describe The Steps To Insert Data At The Starting Of A Singly Linked List?
Answer :
Inserting data at the beginning of the linked list involves creation of a new node, inserting the new node by assigning the head pointer to the new node next pointer and updating the head pointer to the point the new node. Consider inserting a temp node to the first of list
Node *head;
void InsertNodeAtFront(int data)
{
/* 1. create the new node*/
Node *temp = new Node;
temp->data = data;
/* 2. insert it at the first position*/
temp->next = head;
/* 3. update the head to point to this new node*/
head = temp;
}
Question 30. How To Insert A Node At The End Of Linked List?
Answer :
This case is a little bit more complicated. It depends on your implementation. If you have a tail pointer, it’s simple. In case you do not have a tail pointer, you will have to traverse the list till you reach the end (i.e. the next pointer is NULL), then create a new node and make that last node’s next pointer point to the new node.
void InsertNodeAtEnd(int data)
{
/* 1. create the new node*/
Node *temp = new Node;
temp->data = data;
temp->next = NULL;
/* check if the list is empty*/
if (head == NULL)
{
head = temp;
return;
}
else
{
/* 2. traverse the list till the end */
Node *traveller = head;
while (traveler->next != NULL)
traveler = traveler->next;
/* 3. update the last node to point to this new node */
traveler->next = temp;
}
}
Question 31. How To Insert A Node In Random Location In The List?
Answer :
As above, you’d initial produce the new node. Currently if the position is one or the list is empty, you’d insert it initially position. Otherwise, you’d traverse the list until either you reach the specified position or the list ends. Then you’d insert this new node. Inserting within the middle is that the difficult case as you have got to make sure you do the pointer assignment within the correct order. First, you’d set the new nodes next pointer to the node before that the new node is being inserted. Then you’d set the node to the position to purpose to the new node. Review the code below to get an idea.
void InsertNode(int data, int position)
{
/* 1. create the new node */
Node *temp = new Node;
temp->data = data;
temp->next = NULL;
/* check if the position to insert is first or the list is empty */
if ((position == 1) || (head == NULL))
{
// set the new node to point to head
// as the list may not be empty
temp->next = head;
// point head to the first node now
head = temp;
return;
}
else
{
/* 2. traverse to the desired position */
Node *t = head;
int currPos = 2;
while ((currPos < position) && (t->next != NULL))
{
t = t->next;
currPos++;
}
/* 3. now we are at the desired location */
/* 4 first set the pointer for the new node */
temp->next = t->next;
/* 5 now set the previous node pointer */
t->next = temp;
}
}
Question 32. How To Delete A Node From Linked List?
Answer :
Question 33. How To Reverse A Singly Linked List?
Answer :
Question 34. Compare Linked Lists And Dynamic Arrays?
Answer :
Question 35. What Is A Circular Linked List?
Answer :
In the last node of a singly linear list, the link field often contains a null reference. A less common convention is to make the last node to point to the first node of the list; in this case the list is said to be ‘circular’ or ‘circularly linked’.
Question 36. What Is The Difference Between Singly And Doubly Linked Lists?
Answer :
A doubly linked list whose nodes contain three fields: an integer value and two links to other nodes one to point to the previous node and other to point to the next node. Whereas a singly linked list contains points only to the next node.
Question 37. What Are The Applications That Use Linked Lists?
Answer :
Both stacks and queues are often implemented using linked lists, other applications are skip list, binary tree, unrolled linked list, hash table, heap, self-organizing list.
Question 38. How To Remove Loops In A Linked List (or) What Are Fast And Slow Pointers Used For?
Answer :
The best solution runs in O(N) time and uses O(1) space. This method uses two pointers (one slow pointer and one fast pointer). The slow pointer traverses one node at a time, while the fast pointer traverses twice as fast as the first one. If the linked list has loop in it, eventually the fast and slow pointer will be at the same node. On the other hand, if the list has no loop, obviously the fast pointer will reach the end of list before the slow pointer does. Hence we detect a loop.
Answer :
Double-linked lists require more space per node than singly liked lists, and their elementary operations such as insertion, deletion are more expensive; but they are often easier to manipulate because they allow fast and easy sequential access to the list in both directions. On the other hand, doubly linked lists cannot be used as persistent data structures. So, for traversing through a list of node, doubly linked list would be a better choice.
Linked List Related Tutorials | |
---|---|
C++ Tutorial | Data Warehousing Tutorial |
Data Structures Tutorial | Data Structure & Algorithms Tutorial |
All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.