Data structures

Question: Write a function to delete every k th node from circular linked list until only one node is left. This has a story associated with it. Flavius Josephus was Jewish Historian from 1st century. He and 40 other soldiers were trapped in a cave by Romans. They decided to kill themselves rather than surrendering to Romans. Their method was like this. All the soldiers will stand in a circle and every k th soldier will be shot dead. Josephus said to have calculated the starting point so that he would remain alive. So we have similar problem at hand. We delete every kth node in a circular list. Eventually only one node will be left. e.g. Let us say this is our list And we are deleting every third node.  We will delete 30. Then we delete 60. Next we delete 10. Next it will be 50. Next to be deleted is 20. Next 80. This continues. Implementation   We can count k-1 nodes and delete next node. This can be repeated in  a loop. What must be the termina...

Question : Write a function to print the lowest common ancestor of two nodes in a binary search tree.  Lowest common ancestor of two nodes x and y in a binary tree is the lowest node that has both x and y as descendants. Here lowest common ancestor of 1 and 7 is 3. LCA of 13 and 7 is root - 8. And LCA of 6 and 7 is 6 itself. The program to find gets complicated for an ordinary binary tree. But for a binary search tree, it is quite simple. As we see from the diagram above, the paths to 1 and 4 are common till the node 3. And at 3 they branch in different directions. So 3 is our LCA. That is lowest common ancestor is the node where the paths to x and y from root deviate. As long as they branch in same direction, we continue to traverse. When they branch in different directions, that is the lowest common ancestor. So let us write a simple algorithm, set temp=root if temp->val >x and temp->val>y temp = temp->left else if temp->val<x and ...

Question : Write a function for in-order traversal of nodes in the range x to y from a binary search tree. This is quite a simple function. As a first solution we can just traverse our binary search tree in inorder and display only the nodes which are in the range x to y. But if the current node has a value less than x, do we have to traverse its left subtree? No. Because all the nodes in left subtree will be smaller than x. Similarly if the current node has a key value more than y, we need not visit its right subtree. Now we are ready to write our algorithm.     if nd is NOT NULL  if nd->val >=x then visit all the nodes of left subtree of nd recursively display nd->val if nd->val <y then visit all the nodes of right subtree of nd recursively  That's all. We have our function ready. void in_order_middle (NODEPTR nd, int x, int y) { if (nd) { if (nd -> val >= x) in_order_middle(nd...

Question : Write a function to mirror a binary tree. The mirror tree will have a left subtree and right subtree swapped. But this has to be done for each and every node. So to convert a tree to its mirror, we can write an algorithm like this               1) mirror left subtree recursively               2) mirror right subtree recursively               3) swap left and right children of the current node. Here is the function for it. void mirror_tree (NODEPTR root) { if (root != NULL ) { NODEPTR temp = root -> left; root -> left = root -> right; root -> right = temp; mirror_tree(root -> left); mirror_tree(root -> right); } }

Question: Write a program to remove all duplicates from a singly linked list. For example, if the list is 2-->4--->5--->7--->2---->5--->25--->2 after deletion, the output must be something like this 2-->4-->5-->7-->25 An easy solution would be to take one node at a time, compare its value with all the other nodes, and delete if there is a match. But that would be expensive. A better solution is to sort the list and then compare adjacent values. Here is how we do it. Take a sorted list Compare a node with its previous node. If they have same value, delete the node Move to next node Repeat steps 2 to 4 until end of list But you should be careful in step 4. Because if you say, node->next, you may use a dangling pointer. For sorting the list, you can use any algorithm. Insertion sort is easiest for linked lists. Let us look at the code. void remove_duplicates (NODEPTR head) { head = sort_list(head); NODEPTR temp ...

Question: How do you find the merge point of two linked lists? Merge point is the first common node of two linked lists. From this node onwards, the lists have same nodes. Note: we are not talking about values in the nodes, but the actual addresses themselves. In the diagram shown, 4 is the merge point of the two lists. You may think that easy solution is traverse two list parallely and compare the respective nodes of the lists. But that does not work. In the diagram shown, if you start with head of list1 and list2, if you compare addresses of 1 and 5, then addresses of 2 and 6, addresses of 3 and 4 and so on, you will never find a match. An easy solution would be  to take one node at a time from first list and compare this with all nodes in second list. Then move on to second node of first list, compare it with all nodes of second list and so on. And continue this process until a match is found. But this process has a complexity of O(n 2 ). Another method will b...

Question : Write a function to test if two binary trees are equal. The trees are equal only if the values are equal and also the structures are equal. Equal trees       89                                89   12      100                    12       100 2                                 2 Not equal trees         89                          ...

Qn: Write a function to swap the adjacent nodes of a singly linked list.i.e. If the list has nodes as 1,2,3,4,5,6,7,8, after swapping, the list should be 2,1,4,3,6,5,8,7 Image from: https://tekmarathon.com Though the question looks simple enough, it is tricky because you don't just swap the pointers. You need to take care of links as well. So let us try to understand how to go about it. Take two adjacent nodes p1 and p2 Let prevnode be previous node of p1 Now link prevnode to p2 Link p2 to p1 Link p1 to next node of p2 So the code will be prevnode -> next = p2; p1 -> next = p2 -> next; p2 -> next = p1; But what about the start node or head? head node does not have previous node If we swap head with second node, modified head should be sent back to caller  To take care of swapping first and second nodes, we can write p1 = head; p2 = head -> next; p1 -> next = p2 -> next; p2 -> next = p1; head = p2;  Now we are...

Towers of Hanoi is a popular mathematical puzzle invented in 1883 by French mathematician Eduoardo Lucas. It is also a popular example in coding world because it is a typical example where a recursive solution is much easier than iterative solution. In the puzzle, there are 3 rods and n discs of different sizes. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. Gif file from wikipedia Aim of the game is to transfer these  n discs to the 3rd rod, using 2nd rod as temporary location, but keeping in mind that only one disc can be moved at a time. a larger disc can not be placed above a smaller disc. How do we solve this puzzle? If some how we move n-1 discs to 2nd rod in correct order, we only have largest disc in 1st rod. And it can be moved to 3rd rod. So now we need to find a method of moving n-1 discs from 1st rod to 2nd rod in correct order. Again we can use 3rd rod for intermediate stora...

This is one of the interview questions. Given a binary tree, find out whether it is a binary search tree. A binary search tree is an ordered binary tree which satisfies  binary search tree property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree. A binary Search Tree   This diagram shows a BST, because each node has key value larger than left subtree and smaller than right subtree. Binary Tree but not a Binary search tree This is not a binary search tree because key value of left child of root is larger than 2. And key value of node 7 is has a right child whose value is lesser than 7. How to write a function If the in order traversal output does not give key values in ascending order, then the tree is not a binary search tree. But inorder is a recursive function. So we can not directly compare values. We need to use a global variable to store the valu...

How to you a write a function to rotate elements of a an array by n places. Save last element of array in temp Copy a[i-1] to a[i] for all i from len-1 to 1.                for(i=len-1;i>0;i--)                  a[i] = a[i-1]; Copy temp to a[0] Repeat these 3 steps n number of times void rotoateElements(int arr[],int len,int nbits) { int i,j; for(j=0;j<nbits;j++) { int temp=a[len-1]; //Save last element for(i=len-1;i>0;i--) { a[i]=a[i-1];//shift each element by one place } a[0] = temp;//copy last element to 0th element } }

How do we sort a linked list? Try this method - this is simple insertion sort method. Easily implementable in LL. 1) Create a new list called sorted list 2) Take one node from list, delete it. And add it to the sorted list 3) Take the next node - nodenew, traverse through sorted list till you find a node with key value greater than nodenew, and insert the nodenew before this node. Of course you have to delete nodenew from original list. 4) Continue this process until the original list is empty. The complexity - O(n 2 )  struct node { int n; struct node *next; }; typedef struct node *NODEPTR: NODEPTR sortList(NODEPTR head) { NODEPTR newList = NULL; while(head!=NULL) { NODEPTR temp = head; head = head->next; temp->next = NULL; newList = insertSorted(newList,temp); } printList(newList); return newList; } NODEPTR insertSorted(NODEPTR head,NODEPTR newnode) { NODEPTR temp, prevNode=head; if(head==NULL) ...