Explore topic-wise InterviewSolutions in .

This section includes InterviewSolutions, each offering curated multiple-choice questions to sharpen your knowledge and support exam preparation. Choose a topic below to get started.

1.

A given linked list is sorted based on absolute values. Write a function to sort the list based on actual values in O(n) time.

Answer»

All the NEGATIVE elements can be found in the reverse ORDER. Therefore, as we traverse the list, whenever we find an ELEMENT that is out of order, it is MOVED to the front of the linked list.

Auxiliary Space: O(1)

Implementation:

void sortList(Node** head){ // Initialize the previous and the current nodes Node* previous = (*head); Node* current; // list traversal for(current = (*head)->next; current != NULL; current = current->next) { // continue if the current element // is at its right place if (current->value >= previous->value) { previous = current; } // If current is smaller than previous, then // it must be moved to head else { // Detach current from the linked list previous->next = current->next; // MOVE the current node to the beginning current->next = (*head); (*head) = current; // Update current current = previous; } }}
Discussion
2.

Given a linked list and a number n, you have to find the sum of the last n nodes of the linked list in a single traversal. Explain your approach in brief.

Answer»

The use of two-pointers will REQUIRE a single traversal. We will have to maintain two pointers – reference pointer and main pointer. Both these pointers will be initialized to head. First, the reference pointer will be moved to N nodes from the head, and while traversing, we will keep adding the VALUES and store them into a variable called sum1. Now both the pointers will move simultaneously until the reference pointer reaches the end of the list and while traversing, we will keep adding the values of the nodes. The reference pointer is storing this sum in the variable sum1, and the main pointer will be storing it in sum2. Now, (sum1 – sum2) is the answer, that is the REQUIRED sum of the last n nodes.

int getSum(Node* head, int n){ if (n <= 0) return 0; int sum1 = 0, sum2 = 0; struct Node* ptr1 = head; struct Node* ptr2 = head; // the sum of the first n nodes is to be CALCULATED for (ptr1 = head; ptr1 != NULL; ptr1 = ptr1->next;) { sum += ptr1->value; n--; if(n == 0) break; } // now there is a distance of n nodes between the two pointers // move to the end of the linked list while (ptr1 != NULL) { // sum of all the nodes sum1 += ptr1->value; // sum of the first length - n nodes sum2 += ptr2->value; ptr1 = ptr2->next; ptr2 = ptr2->next; } // returning the required sum return (sum1 - sum2);}

Time Complexity is O(n) and space complexity is O(1).
Discussion
3.

How will you modify a linked list of integers so that all even numbers appear before all odd numbers in the modified linked list? Also, keep the even and odd numbers in the same order.

Answer»

Example:
Input: 17->15->8->12->10->5->4->1->7->6->NULL
Output: 8->12->10->4->6->17->15->5->1->7->NULL

Algorithm:
The approach is to divide the linked list into two sections, one with all even nodes and the other with all odd nodes. In order to split the Linked List, traverse the original Linked List and move all odd nodes to a new Linked List. The original list will include all the even nodes at the end of the loop, while the odd node list will have all the odd nodes. We must place all the odd nodes at the end of the odd node list to maintain the same ordering of all nodes. And, in order to do it in real-time, we'll need to maintain track of the last pointer in the odd node list. Finally, the odd node linked list is to be ATTACHED after the even node linked list.

Implementation:

Node* separateEvenOdd(struct Node *head){ // Starting node of the list having // even VALUES Node *evenStart = NULL; // Starting node of the list having odd values Node *oddStart = NULL; // Ending node of the list having even values Node *evenEnd = NULL; // Ending node of the list having odd values Node *oddEnd = NULL; // Node for list traversal. Node *currentNode; for(currentNode = head; currentNode != NULL; currentNode = currentNode -> next) { int value = currentNode -> value; // If the current value is even, add // it to the list of even values. if(value % 2 != 0) { if(oddStart != NULL) { oddEnd -> next = currentNode; oddEnd = oddEnd -> next; } else { oddStart = currentNode; oddEnd = oddStart; } } // If current value is odd, add // it to the list of odd values. else { if(evenStart != NULL) { evenEnd -> next = currentNode; evenEnd = evenEnd -> next; } else { evenStart = currentNode; evenEnd = evenStart; } } } // If any of the two- odd list or even list is empty, // no change is required if(!oddStart || !evenStart) { return; } // Add the odd list after the even list. evenEnd -> next = oddStart; oddEnd -> next = NULL; // Modify the head pointer to // the start of the even list. head = evenStart; return head;}

Time Complexity: O(n)
SPACE Complexity: O(1)
Discussion
4.

A linked list of coordinates is given, with neighboring points forming either a vertical or horizontal line. Remove points in between the starting and ending points of the horizontal or vertical line from the linked list.

Answer»

The objective is to KEEP track of the current node, the next node, and the node after that. Continue deleting the next node when it is the same as the next-next node. We must keep a watch on the shifting of pointers and check for NULL values throughout the entire procedure.

Time Complexity is O(n).
Space Complexity is O(1)

Implementation:

VOID deleteNode(Node *head, Node *t){ head->next = t->next; t->next = NULL; free(t);}// This function deletes the intermediate nodes in a sequence of// horizontal and vertical line segments represented by a// linked list.Node* deleteMiddleNodes(Node *head){ if (head == NULL || head->next == NULL || head->next->next == NULL) return head; Node* t = head->next; Node *tt = t->next; // Check whether this is a vertical line or horizontal line if (t->y == head->y) { // Find intermediate nodes with same y value, and delete them while (tt != NULL && t->y == tt->y) { deleteNode(head, t); // UPDATE t and tt for the next iteration t = tt; tt = tt->next; } } // check for vertical line else if (t->x == head->x) { // Find intermediate nodes with same x value, and delete them while (tt != NULL && t->x == tt->x) { deleteNode(head, t); // Update t and tt for the next iteration t = tt; tt = tt->next; } } // Adjacent points must EITHER have same x or same y else { cout<<"GIVEN linked list is not valid"; return NULL; } // Recursion for the next segment deleteMiddleNodes(head->next); return head;}
Discussion
5.

Construct a doubly linked list out of a ternary tree.

Answer»

A ternary tree is similar to a binary tree, except that instead of two nodes, it has three: LEFT, middle, and right.

The ATTRIBUTES of the doubly linked list should be as follows:

  • The ternary tree's left pointer should be used as the previous pointer in a doubly-linked list.
  • The ternary tree's middle pointer should not point to anything.
  • The ternary tree's right pointer should be the doubly linked list's next pointer.
  • Each ternary tree node is entered into a doubly-linked list before its subtrees, with the left child of each node being inserted first, followed by the middle and right child (if any).

The approach is to make a preorder traversal of the tree. When we visit a node, we will use a tail pointer to INSERT it into a doubly-linked list at the end. That's how we keep the required insertion order. Then, in that order, we call for the left child, middle child, and right child.

Implementation:

//Utility function that creates a doubly linked list//by inserting the current node at the end of the doubly//linked list by employing a tail pointervoid push(Node** tail_reference, Node* n){ // the tail pointer is to be initialized if (*tail_reference == NULL) { *tail_reference = n; // set left, middle and right child to point // to NULL n->left = NULL; n->middle = NULL; n->right = NULL; return; } // using tail pointer, insert node in the end (*tail_reference)->right = n; // the middle and right child are set to point to NULL n->right = NULL; n->middle = NULL; // set previous of the node n->left = (*tail_reference); // now tail pointer is pointing to the inserted node (*tail_reference) = n;}// From a ternary tree, create a doubly linked list,// by making a preorder traversal of the treeNode* ternaryTreeToList(Node** head_reference, Node* root){ // Base case if (!root) return NULL; //a static tail pointer to be created static Node* tail = NULL; // left, middle and right nodes to be stored // for FUTURE calls. Node* left = root->left; Node* middle = root->middle; Node* right = root->right; // set the head of the doubly linked list // as the root of the ternary tree if (*head_reference == NULL) *head_reference = root; // push the current node in the end of the doubly linked list push(&tail, root); //recursion for left, middle and right child ternaryTreeToList(head_reference, left); ternaryTreeToList(head_reference, middle); ternaryTreeToList(head_reference, right);}

Time COMPLEXITY: O(n)
Space Complexity: O(1)
Discussion
6.

The task is to determine pairs in a doubly-linked list whose sum equals the provided value ‘val’ without consuming any extra space for a given sorted doubly-linked list of positive distinct entries. The expected complexities are O(n) time and O(1) space.

Answer»

The approach is as FOLLOWS:

  • Two pointer variables are to be initialized to find the possible ELEMENTS in the sorted DOUBLY linked list. Initialize num1 with the head of the doubly linked list,i.e., num1=head, and num2 with the last node of the doubly linked list, i.e., num2=lastNode.
  • If the current sum of num1 and num2 is less than Val, then we advance num1 in the forward direction. If the current total of the num1 and num2 is greater than x, then num2 is moved in the backward direction.
  • When the two POINTERS cross each other (num2->next = num1) or they become equal (num1 == num2), the loop ends. The condition "num1==num2" will handle the CIRCUMSTANCE where no such pairs are present.

Implementation:

vector<pair<int,int>> sumPair(struct Node *head, int val){ // Two pointers are to be set, one to the beginning // and the other to the last of the DLL. struct Node *num1 = head; struct Node *num2 = head; while (num2->next != NULL) //to get to the last node num2 = num2->next; vector<pair<int,int>> ans; // The loop ends when two pointers // cross each other or they are equal while (num1 != num2 && num2->next != num1) { if ((num1->value + num2->value) == val) { ans.push_back(make_pair(num1->value,num2->value)); // move num1 in the forward direction num1 = num1->next; // move num2 in the backward direction num2 = num2->prev; } else { if ((num1->value + num2->value) > val) num2 = num2->prev; else num1 = num1->next; } } return ans;}

Time Complexity: O(n)
Space Complexity: O(1)
Discussion
7.

Given a 2-D matrix. You need to convert it into a linked list matrix such that each node is linked to its next right and down node and display it.

Answer»

The idea is to create a new node for each ELEMENT of the matrix and then create its next down and right nodes in a recursive manner.

Implementation:

Node* construct(int A[][3], int m, int n, int i, int j){ // check if i or j is out of bounds if (i &GT; n - 1 || j > m - 1) return NULL; // a new node for current i and j is created // and its down and right pointers are //recursively allocated Node* t = new Node(); t->value = A[i][j]; t->right = construct(A, m, n, i, j + 1); t->down = construct(A, m, n, i + 1, j); return t;}// FUNCTION to display linked list datavoid printData(Node* head){ // POINTER to MOVE down Node* d; // pointer to move down Node* r; // loop till node->down is not NULL for( d = head; d!=NULL; d = d->down) { for( r = d; r!=NULL; r = r->right) { // loop till node->right is not NULL cout << r->value << " "; } cout << endl; }}

Time Complexity: O(m * n)
Space Complexity: O(1), ignoring the space required for the final answer.
Discussion
8.

Extract all leaves from a Binary Tree into a Doubly Linked List (DLL).

Answer»

It's worth noting that the DLL must be created in place. Assume that the DLL and Binary Tree node structures are identical, with the exception that the meanings of the left and right pointers. Left denotes the previous pointer, whereas right denotes the next pointer in DLL.

All of the leaves must be traversed and connected by ADJUSTING the left and right pointers. By adjusting the left or right pointers in parent NODES, we can also delete them from the Binary Tree. There are NUMEROUS options for resolving this issue. We add leaves to the beginning of the current linked list and update the list's head using the pointer to head pointer in the following code. We must process leaves in reverse order because we insert from the beginning. We traverse the right subtree first, then the left subtree, in reverse order. To update the left and right pointers in parent nodes, we employ RETURN values.

Implementation:

// The function extracts all the// leaves from a given Binary Tree.// The function returns new root of// the Binary Tree. The function also sets// *head_reference as the head of the DLL.// The left pointer of the tree is used as prev // and the right pointer is used as next in the DLL.Node* extractLeaf(Node **head_reference, Node *root){ if (!root) return NULL; if (root->right == NULL && root->left == NULL) { // This node will be added to the doubly linked // list of leaves. We will have to // set the right pointer of this node // as the previous head of DLL. We // don't need to set the left pointer // as the left is already NULL. root->right = *head_reference; // Change the left pointer of previous head if (*head_reference) (*head_reference)->left = root; // Change the head of the linked list *head_reference = root; return NULL; } // Recursion for right and left SUBTREES root->right = extractLeaf(&head_reference, root->right); root->left = extractLeaf(&head_reference, root->lef); return root;}

Time Complexity: O(n)
Space Complexity: O(1), ignoring the recursion stack space
Discussion
9.

Write a program to delete all odd positioned nodes from a circular linked list. (Consider 1-based indexing).

Answer»

The approach is to begin traversing the circular linked list by keeping track of the current node's POSITION USING a count VARIABLE. Delete the current node if it is at an odd position.

Implementation:

// l is the length of the linked listvoid DeleteAllOddNodes(struct Node** head_reference, int l){ int CNT = 0; struct Node *prev = *head_reference, *next = *head_reference; // check if the list is empty if (*head_reference == NULL) { cout<<"List is empty"<<endl; return; } // check if there is a single node in the list if (l == 1) { // Function to delete first node *head_reference=NULL; return; } while (l > 0) { // delete first position node as it is odd if (cnt == 0) { struct Node *t1 = *head_reference, *t2 = *head_reference; if (t1->next == t1) { *head_reference = NULL; } while(t1->next!=*head_reference) { t1 = t1->next; t2 = t1->next; } t1->next = t2->next; *head_reference = t1->next; free(t2); } // if the position is odd, delete that node if (cnt % 2 == 0 && cnt != 0) { struct Node* tmp = head_reference; if (head_reference == prev) { head_reference = prev->next; } while (tmp->next != prev) { tmp = tmp->next; } tmp->next = prev->next; free(prev); } prev = prev->next; next = prev->next; cnt++; l--; }turn; re}

TIME Complexity: O(n^2)
Space Complexity: O(1)
Discussion
10.

Why is merge sort a better option than quicksort for linked lists?

Answer»
  • When it comes to linked lists, there are a few things to keep in mind. The issue is unique due to the memory allocation differences between arrays and linked lists. Unlike arrays, linked list nodes in memory may not be adjacent.
  • We can insert items in the MIDDLE of a linked list in O(1) extra space and O(1) time if we are GIVEN a reference/pointer to the previous node, unlike an array. As a result, the merge SORT operation can be accomplished WITHOUT the need for additional linked list space.
  • We can do random access in arrays since the elements are continuous in memory. In contrast to arrays, we can't access a linked list at random.
  • Quick Sort necessitates a great deal of this type of access. Because we don't have a continuous block of memory, we have to travel from the head to the i'th node to get to the i'th index in a linked list. Merge sort accesses data in a sequential manner, with less requirement for random access.
Discussion
11.

What algorithm will you implement to find similar elements from two Linked Lists given and return the result in the form of a Linked List? Assume there are no duplicates.

Answer»

Create an empty hash table and set the result list to NULL. While TRAVERSING List1, INSERT the element in the hash table for each element visited in List1. While traversing List2, look for the entries in the hash table for each element visited in List2. If the element is already existing, ADD it to the result list. If the element isn't present, it is to be ignored.

The overall time and space complexity are linear.

NODE* getIntersection(Node* head1, Node* head2){ unordered_map &LT; int > m; Node* n1 = head1; Node* n2 = head2; Node* head = NULL; // loop stores all the elements of list1 in hset while (n1) { m[n1->value] = 1; n1 = n1->next; } // For every element of list2 present in hset // loop inserts the element into the result while (n2 != null) { if (m[n2->value] == 1) { Node* temp = new Node(); temp->value = n2->value; temp->next = head; head = temp; } n2 = n2->next; } return head;}
Discussion
12.

How will you remove a cycle from a linked list?

Answer»

One method of identifying the cycle is Floyd's cycle detect technique, popularly known as the tortoise and hare algorithm since it uses two pointers/references that move at opposite SPEEDS. If there is a cycle, after a limited number of steps, the two pointers (say, slow and fast) will point to the same element.

It's interesting to note that the element where they meet will be the same distance from the loop's start (continuing to traverse the list in the same, forward direction) as the loop's start is from the list's head. That is, if the linear component of the list contains k ELEMENTS, the two pointers will meet inside a loop of length m at a location m-k from the loop's start or k elements from the loop's 'end' (of course, it's a loop, so there is no 'end' - it's just the ‘start' again). That gives us a technique to FIND the loop's beginning.

Once a cycle has been detected, keep fast pointing to the element where the loop for the previous step ended, but reset slow to point back to the beginning of the list. Now, one element at a time, move each pointer. Fast will keep looping because it started inside the loop. Slow and fast will meet again after k steps (equivalent to the distance between the start of the loop and the head of the list). This will serve as a pointer to the beginning of the loop.

It's now simple to set slow (or fast) to point to the loop's STARTING element and traverse the loop until slow returns to the starting element. Slow is referring to the 'last' element list at this point, and its next pointer can be adjusted to null.

Implementation:

Node* getLastNode(Node* head) { Node* slow = head; Node* fast = head; // find the intersection point USING Tortoise and Hare algorithm while (fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; } //check if there is no loop if (fast->next == NULL) { return NULL; } slow = head; // run this loop till both the references are one short of the start of the loop while (slow->next != fast->next) { slow = slow->next; fast = fast->next; } // Now the fast pointer is pointing to the start of the loop return fast;}Node* getLastNode = findStartOfLoop(head);getLastNode->next = null;

Time Complexity: O(n)
Space Complexity: O(1)
Discussion
13.

How will you convert a binary tree into a doubly-linked list?

Answer»

In a converted doubly linked list, the left and right pointers in nodes of a binary TREE will be used as previous and next pointers, respectively. The nodes in the doubly linked list must be in the same order as the provided Binary Tree's INORDER. The HEAD node of the doubly linked list must be the first node of Inorder TRAVERSAL (leftmost node in the binary tree).

void btToDLL(Node *root, Node **head_reference, Node **previous){ if (!root) return; // RECURSIVE conversion of left subtree btToDLL(root->left, head_reference, previous); if (*head_reference == NULL) *head_reference = root; else { root->left = *previous; *previous->right = root; } *previous = root; // Recursive conversion of right subtree btToDLL(root->right, head_reference, previous);}

Time Complexity: O(n)
Auxiliary Space: O(1)
Discussion
14.

How will you find the middle element of a singly linked list without iterating the list more than once?

Answer»

To SOLVE this problem, we can use the two-pointer method. You have two pointers, one fast and one slow, in the two-pointer approach. The fast pointer travels two nodes per step, while the slow pointer only moves one. The slow pointer will point to the middle node of the LINKED list when the fast pointer points to the last node, i.e. when the next node is null.

Node* getMiddle(Node *head){ STRUCT Node *slow = head; struct Node *fast = head; if (head) { while (fast != NULL && fast-&GT;next != NULL) { fast = fast->next->next; slow = slow->next; } } return slow;}

Time Complexity: O(n)
Space Complexity: O(1)
Discussion