Find a pair of elements from an array whose sum equals a given number

 
 /*  
  * 1.Given a sorted array a and a sum k print 
  * all pairs of indexes i and  j such that 
  * a[i]+a[j]=k.  
  */  

 void printPairsWithSum(int *array, int k, int len) {
      int startIndex = 0, endIndex = len - 1, sum;
      while (startIndex < endIndex) {  
           sum = array[startIndex] + array[endIndex];
           if (sum == k) {  
                printf("%d %d \n", startIndex, endIndex);
                startIndex++;  
           } else if (sum > k)  
                endIndex--;  
           else  
                startIndex++;  
      }  
 }  
 int main() {  
      int *array = malloc(sizeof(int) * 100);  
      int len, i;  
      scanf("%d", &len);  
      for (i = 0; i < len; i++) {  
           scanf("%d ", &array[i]);  
      }  
      printPairsWithSum(array, 12, len);  
      return 0;  
 }  

Sorting a linked list

 

 /**Algorithm best suited to sort a linked list. 
  * 
  * Write a C program to implement that algorithm. 
  * Modified quick sort should work. 
  * 
  * ex: 4 8 2 9 5 3 
  *   4 2 8 9 5 3 
  *   4 2 3 9 5 8 
  */ 

 #include "Common.h" 

 typedef struct _node { 
      struct _node *next; 
      int value; 
 } Node; 

 void swap(Node* node1, Node* node2) { 
      int temp = node1->value; 
      node1->value = node2->value; 
      node2->value = temp; 
 } 

 void sortLinkedList(Node *head, Node *lastNode) { 
      if (head == NULL ) 
           return; 

      // if last two nodes and already sorted return 
      if (head == lastNode || head->next == lastNode) 
           return; 

      Node* nextNode = head->next; 
      if (nextNode->next == lastNode) 
      { 
           if (head->value < head->next->value) 
                     return; 
           else 
           { 
                swap(head, head->next); 
                return; 
           } 
      } 

      Node *pivot = head; 
      Node *startNode = head->next, *endNode = head->next, 
           *currSwapNode = startNode;

      while (1) { 
           while (startNode != lastNode) { 
                if (startNode->value < pivot->value) { 
                     currSwapNode = startNode; 
                     startNode = startNode->next; 
                } else { 
                     break; 
                } 
           } 

           if (startNode == lastNode) 
                break; 
           endNode = startNode == lastNode ? startNode : startNode->next; 

           while (endNode != lastNode && endNode->value >= pivot->value) { 
                endNode = endNode->next; 
           } 

           if (endNode != lastNode && startNode != lastNode) 
           { 
                swap(startNode, endNode); 
                currSwapNode = startNode; 
           } 
           else 
                break; 

           startNode = startNode->next; 
      } 

      if (currSwapNode != NULL && pivot->value > currSwapNode->value) { 
           swap(pivot, currSwapNode); 
           sortLinkedList(head, currSwapNode); 
           sortLinkedList(currSwapNode->next, lastNode); 
      } 
      else 
           sortLinkedList(currSwapNode, lastNode); 
 } 

 int main() { 
      int numNumbers, number, i; 
      Node *head = NULL, *current = NULL; 
      printf("Enter the numbers : "); 
      scanf("%d", &numNumbers); 

      for (i = 0; i < numNumbers; i++) { 
           scanf("%d", &number); 
           Node *node = malloc(sizeof(Node)); 
           node->value = number; 
           node->next = NULL; 
           if (current != NULL ) { 
                current->next = node; 
           } 

           if (head == NULL ) { 
                head = node; 
           } 
           current = node; 
      } 

      current = head; 
      while (current != NULL ) { 
           printf("%d ", current->value); 
           current = current->next; 
      } 

      printf("\n"); 
      sortLinkedList(head, NULL ); 

      current = head; 
      while (current != NULL ) { 
           printf("%d ", current->value); 
           current = current->next; 
      } 
      return 0; 
 } 

Find common elements in given two Binary Search Trees

 /*  
  * Two BST are given find common elements in both  
  * Algo works like this:  
  * Iteratively traverse both the tree in inorder fashion  
  * If the first tree node is less than the second tree move the  
  * first tree forward else if the second tree node is less than the  
  * first tree move second tree forward. If equal move both tree forward  
  * Do this operation till either one of the tree is complete.  
  *  
  */  
   
 void CommonElementsInBST(TreeNode* root1, TreeNode* root2) {  
      Stack *stack1 = createStack();  
      Stack *stack2 = createStack();  
      int commonElementCount = 0;  
   
      do {  
           while (root1 != NULL ) {  
                push(stack1, root1);  
                root1 = root1->left;  
           }  
           while (root2 != NULL ) {  
                push(stack2, root2);  
                root2 = root2->left;  
           }  
   
           if (isEmpty(stack1) != 0 && isEmpty(stack2)) {  
                root1 = (TreeNode*)top(stack1);  
                root2 = (TreeNode*)top(stack2);  
                if (*((int*)root1->object) < *((int*)root2->object)) {  
                     pop(stack1);  
                     root1 = root1->right;  
                } else if (*((int*)root1->object) > *((int*)root2->object)) {  
                     pop(stack2);  
                     root2 = root2->right;  
                } else {  
                     pop(stack1);  
                     pop(stack2);  
                     printf("%d ", *((int*) root1->object));  
                     root1 = root1->right;  
                     root2 = root2->right;  
                     commonElementCount++;  
                }  
           }  
      } while (((isEmpty(stack1) != 0) || root1 != NULL) && ((isEmpty(stack2) != 0) || root1 != NULL));  
      printf("Number of common elements are : %d", commonElementCount);  
 }  
   

Stack Operations

Stack create, push, pop, empty operations

 typedef struct _stack {
 int top;
 void* array[20];
} Stack;

Stack* createStack()  
 {  
   Stack *stack = malloc(sizeof(Stack));  
   memset(stack, 0, sizeof(Stack));  
   return stack;  
 }  
   
 void push(Stack* stack, void* elem)  
 {  
   stack->array[stack->top] = elem;  
   stack->top += 1;  
 }  
   
 void* pop(Stack* stack)  
 {  
   void* elem = stack->array[stack->top-1];  
   stack->top -= 1;  
   return elem;  
 }  

 void* top(Stack* stack)
 {
   if (stack->top == 0)
     return NULL;

   return stack->array[stack->top-1];
 }
   
 int isEmpty(Stack* stack)  
 {  
   return stack->top;  
 }  

Inorder Traversal of binary tree

Inorder traversal of binary tree - Recursive

  
typedef struct _binaryTreeNode
{
  struct _binaryTreeNode *left;
  struct _binaryTreeNode *right;
  void* object;
} TreeNode;

void inOrderTraversalRecursive(TreeNode* root) {  
   if (root == NULL )  
     return;  
   inOrderTraversalRecursive(root->left);  
   printf("%d ", *(int *) root->object);  
   inOrderTraversalRecursive(root->right);  
 }  

Inorder traversal of binary tree - Iterative

 void inOrderTraversalIterative(TreeNode* root) {  
   if (root == NULL )  
     return;     
   Stack *tempStack = createStack();   
   do {  
     while (root != NULL ) {  
       push(tempStack, root);  
       root = root->left;  
     }  
   
     if (isEmpty(tempStack) != 0) {  
       root = pop(tempStack);  
       printf("%d ", *((int*) root->object));  
       root = root->right;  
     }  
   } while ((isEmpty(tempStack) != 0) || root != NULL );  
 }  

PS: Stack related functions are here.

Mirror a Binary Tree

Following algorithm would create a mirror of a Tree

 void mirror(TreeNode* root) { 
   if (root == NULL ) 
     return; 
  
   TreeNode* temp = root->left; 
   root->left = root->right; 
   root->right = temp; 
   mirror(root->left); 
   mirror(root->right); 
 } 

Removing consecutive Zeros

 
/*Remove all two consecutive zeros in the given string.

 Example: a3409jd00dk000d

 Output: a3409jddk000d

 Note: If there are less/more than two consecutive zeros, they should not be replaced.

 */



void remove2zeros(char *input) {
 char *temp = input;

 while (*temp != '\0') {
  if (*temp == '0' && *(temp - 1) != '0' && *(temp + 1) == '0'
    && *(temp + 2) != '0') {
   temp = temp + 2;
  } else {
   if (input != temp) {
    *input++ = *temp++;
   } else {
    temp++;
    input++;
   }
  }
 }
 *input = '\0';
}