Prepare IT Interviews

Question:  How would you find a loop in a singly-linked list? Answer:  This is a very typical tech interview question that has a very elegant solution that runs in O(n) time and O(1) space. Also referred to as the “Tortoise and Hare Algorithm”,  the solution uses a fast pointer (traversing the list two items at a time) and a slow pointer (traversing the list one item at a time). If there is a loop, then the fast pointer will go around the loop twice as fast as the slow pointer. At one point, these two pointers will point to the same item. Here’s some code to make this clearer. bool hasLoop( Node *startNode ) { Node *slowNode, *fastNode; slowNode = fastNode = startNode; while( slowNode && fastNode && fastNode->next ) { if( slowNode == fastNode->next || slowNode == fastNode->next->next ) { return true; } slowNode = slowNode->next; fastNode = fastNode->next->next; ...

Question:  Reverse a Linked-list. Write code in C. Answer:  There are multiple ways to go about this. Let’s first look at a recursive solution. Node * reverse( Node * ptr , Node * previous) { Node * temp; if(ptr->next == NULL) { ptr->next = previous; return ptr; } else { temp = reverse(ptr->next, ptr); ptr->next = previous; return temp; } } reversedHead = reverse(head, NULL); Now for a non-recursive solution. Node * reverse( Node * ptr ) { Node * temp; Node * previous = NULL; while(ptr != NULL) { temp = ptr->next; ptr->next = previous; previous = ptr; ptr = temp; } return previous; } I personally prefer the non-recursive solution but it is always good to know both of them.

Question:  You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C. Answer:  To delete a node, you have to redirect the next pointer of the previous node to point to the next node instead of the current one. Since we don’t have a pointer to the previous node, we can’t redirect its next pointer. So what do we do? We can easily get away by moving the data from the next node into the current node and then deleting the next node.  This solution has O(1) runtime. Here’s some code to illustrate this simple logic. void deleteNode( Node * node ) { Node * temp = node->next; node->data = node->next->data; node->next = temp->next; free(temp); } Some things to consider. This method could pose potential problems. For instance, let’s consider we have a linked list A -> B -> C -> D and we are given a pointer to B to delete it. Theoretical...

uestion:  Devise an algorithm to determine the Nth-to-Last element in a singly linked list of unknown length. If N = 0, then your algorithm must return the last element. Answer:  Given that the only way to traverse a singly linked list is forwards from the head, it is not possible to just count N elements from the end of the linked list. Furthermore, the length of the linked list is unknown. We could traverse the list once to determine the number of elements and then traverse the list again to stop at the Nth element from the last element. But this seems a little inefficient. What if we could use 2 pointers? So what if we use a current pointer and another pointer that is N elements behind the current pointer. When the current pointer reaches the end of the list, the second pointer will be pointing to the element N elements from the end of the list. Here’s some code to illustrate this logic. Node * findNToLastNode( Node *head, int N ) { int i = 0; Node *current...