Coding Tricks

Posts

A maths puzzle in Javascript

I have written an app called Hundred. The app has a grid of 3 by 3. Some numbers in the grid are given. You have to fill the rest of the numbers with the condition that sum of each row and sum of each column is 100. I have written the same using HTML and java script now. Here is the source code of the same. HTML <!DOCTYPE html> <html> <head> <meta charset="utf-8" /> <meta name="viewport" content="width=device-width, initial-scale=1"> <style> .grid-container { width:auto; display: grid; grid-row-gap:2px; grid-column-gap:2px; grid-template-columns: 80px 80px 80px ; padding: 10px; } .grid-item { background-color: rgba(255, 255, 255, 0.8); border: 1px solid rgba(0, 0, 0, 0.8); padding: 20px; font-size: 22px; text-align: center; } </style> <script type="text/javascript" src="shataka.js"></script> </head> <body> ...

Count the number of leaf nodes

Qn: Write a function to count the number of leaf nodes in a binary search tree. Solution: count = leaf nodes in left subtree + leaf nodes in right subtree If a node is having left link as NULL and right link as NULL, then it is a leaf node. So if this condition is true, the call should return 1. If the node is NULL, the call should return 0. if node is NULL return 0 if node->left==NULL and node->right==NULL return 1 else return count(node->left)+count(node->right)

Count the number of nodes of a binary tree

Question: How do you count the nodes of a binary tree? Solution : Like almost all functions in a binary tree, this algorithm also needs a recursive function. The no. of nodes of a binary tree = 0 if the node is NULL = 1 + no. of nodes in left sub-tree+ no.of nodes in right sub-tree. Calculate recursively for all sub-trees. Here is C++ code for the same. int bintree::count() { return count_leaf_nodes(root); } int bintree::count_nodes(node * nd) { if(nd==NULL) return 0; if(nd->left ==NULL && nd->right==NULL) return 1; return 1+count_nodes(nd->left)+count_nodes(nd->right); }

Deleting a node from binary tree

Write a program to delete a node from binary search tree. Solution : The problem with binary tree operations is that it is nonlinear. When we delete a node from linked list, we link the previous node to the next node so that the list is not broken. But that is not simple in binary tree. Because the node has two next nodes - left child node and right child node. Which do we link to previous node - or parent node? If we link say left child node to the parent of node to be deleted, what do we do with other branch? When a node is to be deleted from a binary search tree, there are 3 possible cases. the node is leaf the node has only one child/subtree the node has both children/subtrees The following recursive algorithm takes care of all three cases nd = root find the node to be deleted if nd->val > delvalue recursively call delete on nd->left and set result to nd->left if nd->val < delvalue recursive, call delete on nd->right and set result to nd->right no...

Reverse a singly linked list

I think I have already blogged it some where. It is very common question - next only to inversing the binary tree. Write a function to reverse a singly linked list. Would you like to write a recursive function? No, OK, let us write a non-recursive function for this. Let us say you have first three nodes n1, n2 and n3. Now simply link n2 to n1. Next take next three nodes n2,n3 and n4 and link n3 to n2. Continue this process until you reach the end of the list. Take n1, n2 = n1->next and n3 = n2->next Set n1->next = NULL. Because this will be your last node. Now link n2 and n1. That is set n2->next = n1. Now assign n1 = n2, n2 = n3 and n3 = n3->next Repeat 2 steps above until n3 = NULL. You still have one un-assigned node. Set that. n2->next = n1 Now n2 is your new head node. That's it. And now it is the coding time. #include<iostream> using namespace std; struct node { int n; node *next; }; class...

Concatenation of two circular linked lists

Here is a trick question - a data structures question for you Write a function to concat two circular linked lists. Without traversing either of them. The lists are singly linked. hint : order is not important. Let us try to understand the situation. We have two single linked circular lists. We have to join them. One easy solution would be to traverse to the end of first list and link the last node to second list. But we are not allowed to do that. The second possible solution could be find the previous node of head of first list - which will be last node. And then link it to second list. Again, not possible as the list is not doubly linked. Ok. Here is the solution Let temp be the next node of head of list1 Link head of list1 to head->next of list2 Link head of list2 to temp Let us take an example. Let the two lists be 1-2-3-4-5 and 10-20-30 Now let temp=2 Assign 1->next =20. Now we have list1 as 1-20-30-10. and back to 20 Assign 10->n...

Program to add a node to rear of circular linked list

Let us write Write a program to add a node to the rear of a circular linked list. Now a circular linked list has no end. That is to say, the last node in the list points back to the head of the list. So finding the last node will be slightly tricky. let temp = head while temp->next !=head temp = temp->next Once we find the last node, we append the new node here. But we must not forget to point his new node back to head. lastnode->next = newnode; newnode->next = head; The complexity is O(n). Here is the complete program #include<iostream> using namespace std; struct node { int n; node *next; }; class linked_list { node *head; public: linked_list(int val = 0) { if(val==0) head = NULL; else{ head = new node; head->n = val; head->next = NULL; } } node* find_last_node() { if(head==NULL || head->next==head) ...