Threaded Binary Tree

Threaded binary tree saves stack recursion space used for traversing a tree , by making traversal iterative istead of recursive.
    The right most null node is made to be ponted to its inorder successor while tree formation .
    So space complexity becomes O(1) from O(N)



#include<cstdio.h>
#include<iostream>


//structure of a node in a threded binary tree
struct treeNode{
    int data;
    struct treeNode* right;
    struct treeNode* left;
    bool isRightHanded;
       
};

struct treeNode* leftMost(struct  treeNode* curr)
{
    if (curr == NULL)
        return NULL;
    while (curr->left != NULL)
        curr = curr->left;
    return curr;

}



void traverseThrededTree(struct treeNode* root)
{
    if (root == NULL)
    {
        printf("Empty tree");
        return ;
    }

    struct treeNode* cur = leftMost(root);

    while (cur != NULL)
    {
        printf("%d", cur->data);

        //if node is right handed , go to next node
        if (cur->isRightHanded)
        {
            cur = cur->right;
        }
        else // else go to next leftmost node of the right node , if it exist
        {
            cur = leftMost(cur->right);
        }
    }




}

Find size of a binary tree

#include<stdio.h>
#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

int sizeOfTree(struct treeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }

    return sizeOfTree(root->left) + 1 + sizeOfTree(root->right);
}

int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Size of the tree is %d", sizeOfTree(root));
    getchar();
    return 0;
}

Print all paths from root to leaf node in a binary tree

Maintain an array path[] having node's data on each level , and the length of path[] , on every  new level oush the node's data to path[] and increment path len.
If we are at the leaf node ,  print the path[] , or try recursing to left and right child 

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

void printPathsRecur(struct treeNode* node, int pat[], int pathlen);

void printArray(int ints[], int len)
{
    int i;
    for (i = 0; i<len; i++) {
        printf("%d ", ints[i]);
    }
    printf("\n");
}
void mirror(struct treeNode* node)
{
    if (node == NULL)
        return;
    //go to left node
    mirror(node->left);
    mirror(node->right);

    //swap left and right node child pointers
    struct treeNode* temp = node->left;
    node->left = node->right;
    node -> right = temp;


}

void printPaths(struct node* node)
{
    int path[1000];
    printPathsRecur(node, path, 0);
}

void printPathsRecur(struct treeNode* node, int pat[], int pathlen)
{
    if (node == NULL)
    {
        return;
    }
   
    //add the node to path at this level
    pat[pathlen] = node -> data;
    //increment path len
    ++pathlen;

    //if its a leaf node , print the path
    if (node->right == NULL && node->left == NULL)
    {
        printArray(pat, pathlen);
    }
    else
    {
        //try bith subtree
        printPathsRecur(node->left, pat, pathlen);
        printPathsRecur(node->right, pat, pathlen);
    }
}
int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    /* Print all root-to-leaf paths of the input tree */
    printPaths(root);

    getchar();
    return 0;
   
}

Mirror a Binary tree

Mirror a binary tree works by recursing in post order , and then swapping left and right pointers of the node

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

void mirror(struct treeNode* node)
{
    if (node == NULL)
        return;
    //go to left node
    mirror(node->left);
    mirror(node->right);

    //swap left and right node child pointers
    struct treeNode* temp = node->left;
    node->left = node->right;
    node -> right = temp;


}

void inOrder(struct treeNode* node)
{
    if (node == NULL)
        return;

    inOrder(node->left);
    printf("%d ", node->data);

    inOrder(node->right);
}
int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    /* Print inorder traversal of the input tree */
    printf("\n Inorder traversal of the constructed tree is \n");
    inOrder(root);

    /* Convert tree to its mirror */
    mirror(root);

    /* Print inorder traversal of the mirror tree */
    printf("\n Inorder traversal of the mirror tree is \n");
    inOrder(root);

    getchar();
    return 0;
   
}

Find Height of a Tree

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

int maxDepth(struct treeNode* root)
{
    if (root == NULL)
        return 0;
    else
           
    {   

        return ( max(maxDepth( root->left) , maxDepth(root->right) ) + 1 );
    }
}

int main()
{
    struct treeNode *root = newNode(1);

    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Hight of tree is %d", maxDepth(root));

    getchar();
    return 0;
   
}

Diameter of Binary Tree

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}


void printArray(int ints[], int len)
{
    int i;
    for (i = 0; i<len; i++) {
        printf("%d ", ints[i]);
    }
    printf("\n");
}

int maximum(int a, int b)
{
    return a>=b?a : b;
}

int height(struct treeNode* root)
{
    if (root == 0)
    {
        return 0;
    }

    int h = 1 + maximum(height(root->left) , height(root->right));
    return h;
}

/*
/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1
*/

int diameter(struct treeNode* root)
{
    if (root == 0)
        return 0;
    int rHeight = height(root->right);
    int lHeight = height(root->left);

    int lDiameter = diameter(root->left);
    int rDiameter = diameter(root->right);

    return maximum(1 + rHeight + lHeight, maximum(lDiameter, rDiameter));

}




int main()
{
    /* Constructed binary tree is
    1
    /   \
    2      3
    /  \
    4     5
    */
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Diameter of the given binary tree is %d\n", diameter(root));

    getchar();
    return 0;
}

Delete a Binary Tree

Using postorder traversal , delete tree , as we should delete child nodes first instead of parent node for straight tree deletion
#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};   


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

void deleteTree(struct treeNode* node)
{
    if (node == NULL)
    {
        return;
    }

    deleteTree(node->left);
    deleteTree(node->right);
    free(node);

}
int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    deleteTree(root);
    root = NULL;

    printf("\n Tree deleted ");

    getchar();
    return 0;
   
}

Check If Both Binary Trees Are Identical

Complexity O(m) where m is size of tree with nodes m <=n , where n is size of other tree

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

int isIdentical(struct treeNode* A, struct treeNode* B)
{
    //if both are empty , return 1
    if (A == NULL  && B == NULL)
    {
        return 1;
           
    }

    if(A != NULL && B != NULL)
    {
        //check if the data at root or root of subtree (while recursion) , and left and right subtree are equal
        //by recursing to left and right subtree
        return A->data == B->data && isIdentical(A->left, B->left) && isIdentical(A->right, B->right);
    }
    //else both trees are not identical ,one empty and other is not ,  return 0
    else return 0;
}

int main()
{
    struct treeNode *root1 = newNode(1);
    struct treeNode *root2 = newNode(1);
    root1->left = newNode(2);
    root1->right = newNode(3);
    root1->left->left = newNode(4);
    root1->left->right = newNode(5);

    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);

    if (isIdentical(root1, root2))
        printf("Both tree are identical.");
    else
        printf("Trees are not identical.");

    getchar();
    return 0;
}

Swap nibbles of a given number

#define swapNibble(num)   (( num & 0xF ) << 4 )  |  ( ( num 7 0xF0 ) >> 4 )

( num & 0xF ) << 4 ) : This grabs first nibble of nummber  and left shifts the nibble  to 4 places

( num 7 0xF0 ) >> 4 ) : And this grabs the next nibble of the number and right shifts the nibble  to 4 places

Finally we use bitwise OR  swap is completed

Stack using arrays

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<limits.h>

struct Stack {
    int top;
    unsigned int capacity;
    int* array;

};

//function to create a stack  , initialising with capacity as zero

struct Stack* createStack(unsigned int cap)
{
    struct Stack* newStack = (struct Stack*) malloc(sizeof(struct Stack));

    newStack->top = -1;
    newStack->capacity = cap;
    newStack->array = (int*)malloc(sizeof(int)* newStack->capacity);
    return  newStack;
}


int isFullStack(struct Stack* stack)
{
    return stack->top == stack->capacity - 1;
}

int isEmptyStack(struct Stack* stack)
{
    return stack->top ==  - 1;
}

void push(struct Stack* stack , int item )
{
    if (isFullStack(stack) == 1)
    {
        printf("Stackoverflow");
        return;
    }

    stack->array[++stack->top] = item;
    printf("Pushed on stack %d \n ", item);

}

int pop(struct Stack* stack)
{
    if (isEmptyStack(stack) == 1)
    {
        printf("Stack Underflow");
        return INT_MIN;
    }

    printf("Popped %d\n", stack->array[stack->top]);
    return stack->array[stack->top--] ;

}

void peek(struct Stack* stack)
{
    if (isEmptyStack(stack))
    {
        printf("Empty stack \n");
        return;
    }
    printf("%d\n" , stack->array[stack->top]);
    ;
}

int main()
{
    struct Stack* stack = createStack(100);
    push(stack , 1 );
    push(stack, 2);
    push(stack, 3);

    pop(stack);
    peek(stack);

    pop(stack);
    pop(stack);
    peek(stack);
    push(stack, 1);
    peek(stack);

    getchar();
    return 0;

       




}

Stack with Linked List

//STACK WITH linked list

#include<stdlib.h>
#include<limits.h>
#include<conio.h>
#include<stdio.h>

struct StackNode {
    int data;
    struct StackNode* next;
};

struct StackNode* newNode(int data)
{
    struct StackNode* node = (struct StackNode*) malloc(sizeof(struct StackNode));
    node->data = data;
    return node;

}

int isEmpty(struct StackNode* root)
{
    return !root;
}

void push(struct StackNode** root, int item)
{
    struct StackNode* node = newNode(item);
    node->next = *root;

    *root = node;
    printf("pushed %d \n", item);

}

void pop(struct StackNode** root)
{
    if (isEmpty(*root))
    {
        printf("Underflow \n");
        return;
    }
    int poped = (*root)->data;
    struct StackNode* temp = *root;
    *root = (*root)->next;
    free(temp);

    printf("popped %d\n", poped);

}

void peek(struct StackNode* root)
{
    if (isEmpty(root))
    {
        printf("empty stack \n");
        return;
    }
    printf("peeked %d \n" , root->data);

}


int main()
{
    struct StackNode* stackRoot = NULL;
    push(&stackRoot, 4);
    push(&stackRoot, 6);

    pop(&stackRoot);

    peek(stackRoot);

    pop(&stackRoot);
    peek(stackRoot);
    push(&stackRoot, 6);
    peek(stackRoot);

    getchar();
    return 0;


}

Tid Bits - Stack :

Stack can be FILO - First in last out or LIFO - First in last out .
Underflow condition - When a pop operation  is performed on an empty stack
Peek Operation   : get the topmost item
Stack can be implemented using an array or a Linked List
Basic ADT : Using arrays :
            struct Stack {
                int top  ;
                unsigned int capacity ;
                int* array ;
              }
             
              Disadvantages using array :
             
              No dynamic size
              Doesnt grow or shrink using depending on needs at runtime
             
              Using Linked List :
              struct StackNode {
                int data ;
                struct StackNode* next ;
              }
             
 Balancing of symbols:
Infix to Postfix/Prefix conversion
Redo-undo features at many places like editors, photoshop.
Forward and backward feature in web browsers
Used in many algorithms like Tower of Hanoi, tree traversals.
Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver.



We need postfix notations because compiler scans the expressions from left to right or from right to left
Consider the below expression: a op1 b op2 c op3 d
If op1 = +, op2 = *, op3 = +

The compiler first scans the expression to evaluate the expression b * c, then again scan the expression to add a to it. The result is then added to d after another scan.


The expressions written in postfix form are evaluated faster compared to infix notation as parenthesis are not required in postfix.

Efficiency of Short Hand Notation

Why x += 1 ; is more efficient than x = x+1 ?

It is related to how assembler references the memory location accesss .
The ALU uses registers for referencing values and accumulator for storing partial results .
 So , for case 1 : 
  x =  x + 1 ;
 
  MOV A , (x) ;  // Move the value at memory location x in accumultor A  . The value of x is stored in register
  ADD A , 1  ; // ADD 1 IN ACCUMULATor
  MOV (X) ,  A ; // Move the value in accumulator at memory location referenced by x
 
  for case 2 :
  x += 1
  ADD (x) , 1 ; // Add 1 at memory location referenced by x
 
  So , so coz of efficient dereferncing and no partial result generation  , short hand artihmatic noations are efficient even though at an abstract view all operations produce same results

Java tid bits :

1 : A class that implpementing an interface becomes an abstract class if it dont implements all the functions declared inside Interface and hence cant be used for instantiating objects

2 : Interfaces having only variables can be used for making set of Global Constants which can be used by other classes , just like constants declared in C header files


3 : Packages help in resuing classes across programmes
4 : Only at runtime, interpreter loads the class used from other package , during compilation , compiler only  checks whther the .class file is present in package imported

5: A java source file can only have one class declared as public because filename should be same as the public class with .java extension . But many non public classes can be defined

6:
Exception class is a subclass of Throwable , hence so do all user defined exceptions

7 : in switch case statements only constant values or literals are allowed
 final String a = "" , b = "fa";
     switch("dgh")
     {
     case "sdg":
         break;
     case a+b :
         break;
     }
    
8:  Runtime : polymorphism (overriding) and Compiletime - Inheritance of methods and attributes by subclasses

9 :  Java's interpreter do thread switching for multi threading
10 : States of a Thread :
New Born State : When an object of a class extending java.lang.Thread is made
Runnable state : on calling start()
Running state : Java runtime schedules thread calling run()

Next Greater Element

/// PRINT NEXT GREATER ELEMENT IN THE STACK FOR AN ARRAY O(N)
void printNextGreater( int arr[] ,int n )
{
    // the array item under consideration
    int next  ;
    int element ; //the current popped element
    struct stack s;
   
    //push the first element to the stack
    s.push(&s , arr[0]) ;
   
    for(int  i = 1 ; i < n ; ++i)
    {
        next = i ;
   
            while( isEmpty(s) == false )
            {
                //pop the element from the stack
                element = s.pop();
               
                //print the pairs until popped element are smaller than next
                // these are the next greater element pairs for each element in stack pushed earlier
                while ( element < next)
                {
                    printf("%d -> %d \n" , element , next );
                    if(isEmpty(s)) break;
                    element = pop(&s);
                }
               
                //if the popped element is greater than next , push it back to stack
                if(element > next )
                    push(&s , element);
               
            }
           
            //push the next to find its next greater element
            push (&s , next);
   
    }
   
    //for all remaining element in the stack , print -1 as these elements dont have next greater element
    while(isEmpty(s) == false)
    {
        printf("%d -> -1" , pop(&s));
    }
   
}

Find even or odd parity of a given unsigned number

// parity here means total number of set bits in  a number

typedef int bool ;


int parity ( unsigned int num )
{
    bool parity  = 0 ; // 0 means even parity and 1 meand odd parity
   
    while ( num )
    {
        parity  = !parity ;
        num &= n-1 ;
     }
   
    return parity;
}

i haave seen a million faces
but still my heart embraces

Evaluate Postfix

Algorithm to follow :
    Scan the characters in the expression , and
    for each character
        If the character is an operand , push it to stack
        If the character is an operator , pop the operands , evaluate result and push result back to stack
    After the loops ends scanning and evaluating , pop the value from stack and return it as the final value of the postfix expression
   

int evaluatePostfix(char* exp)
{
    //create a stack equal to expression size
    struct Stack* stack = createStack(strlen(exp));
   
    //check if stack was created successfully
    if (!stack) return -1;

    //scan all characaters in the expression one by one
    for (int i = 0; exp[i]; ++i)
    {
        //if the scanned character is a number ,push it on the stack
        if (isdigit(exp[i]) ) push(stack , ( exp[i] - '0' ) );

        //else pop the operands from stack and push back the result after evaluation
        else
        {
            int value1 = pop(stack);
            int value2 = pop(stack);
            switch (exp[i])
            {
            case '+':
                push(stack , value2 + value1 ); // value2 is the first operand because it was pushed before value1
                break;
            case '-':
                push(stack, value2 - value1); // value2 is the first operand because it was pushed before value1
                break;
            case '/':
                push(stack, value2 / value1); // value2 is the first operand because it was pushed before value1
                break;
            case '*':
                push(stack, value2 * value1); // value2 is the first operand because it was pushed before value1
                break;
            }
        }

    }

    //the last value in the stack is ours final result
    return pop(stack);


}

Post Fix to Infix

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Stack type
struct Stack
{
    int top;
    unsigned capacity;
    int* array;
};

// Stack Operations
struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));

    if (!stack)
        return NULL;

    stack->top = -1;
    stack->capacity = capacity;

    stack->array = (int*)malloc(stack->capacity * sizeof(int));

    if (!stack->array)
        return NULL;
    return stack;
}
int isEmpty(struct Stack* stack)
{
    return stack->top == -1;
}
char peek(struct Stack* stack)
{
    return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
    if (!isEmpty(stack))
        return stack->array[stack->top--];
    return '$';
}
void push(struct Stack* stack, char op)
{
    stack->array[++stack->top] = op;
}


int isOperand(char ch)
{
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

int prec(char ch)
{
    switch (ch)
    {
    case '+':
    case '-' :
        return 1;
    case '*':
    case '/':
        return 2;

    case '^':
        return 3;
    }
    return -1;
}

int infixToPostfix(char* exp)
{

    int k , i ;
    struct Stack* stack = createStack(strlen(exp));
    if (!stack)
        return -1;
    for ( i = 0, k = -1; exp[i]; ++i)
    {
        //if scanned character is an operand , add to the output
        if (isOperand(exp[i]))
            exp[++k] = exp[i];
        // If the scanned character is an ‘(‘, push it to the stack.
        else if (exp[i] == '(')
            push(stack, exp[i]);
        //  If the scanned character is an ‘)’, pop and output from the stack
        // until an ‘(‘ is encountered.
        else if (exp[i] == ')')
        {
            while (!isEmpty(stack) && peek(stack) != '(')
                exp[++k] = pop(stack);
            if (!isEmpty(stack) && peek(stack) != '(')
                return -1; //invalid expression
            else
                pop(stack); // pop starting braces (
        }

        else //an operator is encountered
        {
            while (!isEmpty(stack) && prec(exp[i]) <= prec(peek(stack)))
                exp[++k] = pop(stack);
            push(stack, exp[i]);
        }

    }
    // pop all the operators from the stack
    while (!isEmpty(stack))
        exp[++k] = pop(stack);

    exp[++k] = '\0';
    printf("%s\n", exp);
}
// Driver program to test above functions
int main()
{
    char exp[] = "a+b*(c^d-e)^(f+g*h)-i";
    infixToPostfix(exp);
    getchar();
    return 0;
}

Check For Balanced Expression in an expression

Given an expression string exp, write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”  

// a function to check if two given characters are a matching pair
bool isMatchingPair( char chr1 , char chr2   )
{
    if( chr1 == '(' && chr2 == ')')
        return 1 ;
    else if( chr1 == '{' && chr2 == '}')
        return 1 ;
    else if( chr1 == '[' && chr2 == ']')
        return 1 ;
     else
        return 0 ;
       
       
}

bool arePraenthesisBalanced (char exp[])
{
    int i = 0 ;
   
    // an empty character stack  to be made up of linked list
    struct sNode* stack = NULL;
   
    //while we dont approach the null character of the string
        while( exp[i])
        {
            // if exp[i] is a starting charcter push it
            if(exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
                push(&stack, exp[i]);
          
           //if the exp[i] is an ending parenthesis , pop from stack and check whether it matches as the type of starting parenthesis exp[i]
            if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
            {
                //if the stack is NULL , return false  as  this is an extra invalid parentheis
                if(stack == NULL)
                {
                    return 0 ;
                }
                 // pop the character and check if it is  not of the type of exp[i] , return false
                 else if(!(isMatchingPair(pop(&stack) , exp[i])))
                    return 0 ;
               
            }
            ++i;
          
        }
       
        //if there is something left in stack , means we found an unmatched single parenthesis type
        // return false
        if(stack  == NULL )
            return true ; //balanced
          else
            return false; //unbalanced
         
}

Transpose A Matrix

public class mMatrix {

    public static void main(String args[]) {
        int[][] twodarray = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
       
        for( int i = 0 ; i < twodarray.length ; ++i)
        {
            for( int j = 0 ; j < twodarray[0].length ; ++j)
            {
                System.out.print(twodarray[i][j] + " ");
            }
            System.out.println();
           
        }
       
        int transpose [][]  = new int [ twodarray.length ][ twodarray[0].length ];       
        for( int i = 0 ; i < twodarray.length ; ++i)
        {
            for( int j = 0 ; j < twodarray[0].length ; ++j)
            {
               
                transpose[j][i] = twodarray[i][j];
               
            }
            System.out.println();
           
        }
       
        for( int i = 0 ; i < twodarray.length ; ++i)
        {
            for( int j = 0 ; j < twodarray[0].length ; ++j)
            {
                System.out.print(transpose[i][j] + " ");
            }
            System.out.println();
           
        }
       
       
    }

}

LCM

import java.io.InputStreamReader;
import java.io.BufferedReader;

public class hLCM {
    public static void main(String args[]) {
        InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(in);

        int first = 0;
        int second = 0;
        // get a number
        System.out.println("Enter  numbers to find LCM : ");
        try {
            first = Integer.parseInt(reader.readLine());
            second = Integer.parseInt(reader.readLine());
        } catch (Exception e) {
            e.printStackTrace();
           
        }

        int lcm = first * ( second / gcd(first , second ) );
               
       
        System.out.println("LCM is "  + lcm );

    }

    private static int gcd(int first, int second) {
        while (second > 0) {
            int temp = second;
            second = first % second;
             first = temp ;

        }
        return first ;
    }
}

GCD

import java.io.InputStreamReader;

import java.io.BufferedReader;

public class gGCD {
    public static void main(String args[]) {
        InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(in);

        int first = 0;
        int second = 0;
        // get a number
        System.out.println("Enter  numbers to find GCD : ");
        try {
            first = Integer.parseInt(reader.readLine());
            second = Integer.parseInt(reader.readLine());
        } catch (Exception e) {
            e.printStackTrace();
           
        }

        first = gcd(first , second);
       
        System.out.println("GCD is "  + first);

    }

    private static int gcd(int first, int second) {
        if(second > 0)
            first =  gcd(second , first % second) ;
        return
                first ;
   
       
    }
}

Floyd's Triangle

import java.io.InputStreamReader;
import java.io.BufferedReader;

public class eFloydsTraingle {
    public static void main(String args[]) {
        InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(in);

        int length = 0;
        // get a number
        System.out.println("Enter height of triangle : ");
        try {
            length = Integer.parseInt(reader.readLine());
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("Out of memory");
            return;
        }
       
        int fIndex = 1 ;
        // print the triangle
        for(int i=0 ; i < length ; ++i)
        {
            for(int j= 0 ; j <= i ; ++j){
                System.out.print(fIndex++  + " ");
            }
            System.out.println();
        }

    }
}

Is a given Number Palindrome

import java.io.InputStreamReader;
import java.io.BufferedReader;

public class dNumberIsPalindrome {
    public static void main(String args[]) {
        InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(in);

        String num;
        // get a number
        System.out.println("Enter a number : ");
        try {
            num = reader.readLine();
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("Out of memory");
            return;
        }

        boolean isPalindrome = false;

        char array[] = num.toCharArray();
        int endIndex = array.length - 1;
        for (int startIndex = 0; startIndex <= endIndex; ++startIndex, --endIndex) {

            if (array[startIndex] != array[endIndex]) {
                isPalindrome = false;
                break;
            }
            isPalindrome = true;
        }

        System.out.println("Palindorme check for " + num + " is "
                + isPalindrome);

    }
}

Sum of digits

import java.io.InputStreamReader;
import java.io.BufferedReader;

public class cCountSumOfDigits {
    public static void main(String args[]) {
        InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(in);

        int num = 0;
        // get a number
        System.out.println("Enter a number : ");
        try {
            num = Integer.parseInt(reader.readLine());
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("Out of memory");
            return;
        }
        int temp = num;
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }

        System.out.println("Sum of digits in " + temp + " is " + sum);

    }
}

Count total digits

import java.io.InputStreamReader;
import java.io.BufferedReader;

public class bCountDigits {
    public static void main(String args[]) {
        InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(in);

        int num = 0;
        // get a number
        System.out.println("Enter a number : ");
        try {
            num = Integer.parseInt(reader.readLine());
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("Out of memory");
            return;
        }
        int temp = num;
        int ttlDigits = 0;
        while (num > 0) {
            ++ttlDigits;
            num /= 10;
        }

        ttlDigits = (ttlDigits == 0) ? 1 : ttlDigits;

        System.out.println("Total digits in " + temp + " is " + ttlDigits);

    }
}

Reverse a number

import java.io.InputStreamReader;
import java.io.BufferedReader;

public class aReverseNumber {
    public static void main(String args[]) {
        InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(in);

        int num = 0;
        // get a number
        System.out.println("Enter a number : ");
        try {
             num = Integer.parseInt(reader.readLine());
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("Out of memory");
            return ;
        }
        int temp = num ;
        int revNum = 0 ;
        while (num > 0 )
        {
            revNum = revNum *10 +  num % 10 ;
            num/= 10 ;
        }
       
        System.out.println("Reverse of " + temp + " is " +revNum );
       
       
       
    }
}

Check if two linked lists are identical

int isIdentical(struct node* a , struct node* b )
{
    if(a == NULL && b == NULL)
    {
        return 1 ;
    }
    if(a == NULL && b != NULL)
    {
        return 0 ;
    }
    if(a != NULL && b == NULL)
    {
        return 0 ;
    }
    if(a->data !=  b-> data)
    {
        return 0 ;
    }
   
    return isIdentical(a->next ,  b->next );
   

}

Merge two sorted linked list in a sorted order

//merge two sorted linked list in sorted order

void MoveNode(struct node **dest , struct node **src)
{
    struct node* newNode = *src;
   
    assert(newNode != NULL) ;
   
    //advance src
    *src = newNode->next;
   
    //link new node with destination old reference
    newNode->next = *dest;
   
    //point dest to new node
    *dest = newNode;
   

}


struct  node*  merge(struct node** a , struct node** b )
{
    struct node dummy;
   
   
    //pointer to tail for easy appendinng at end of list in MoveNode()
    struct node* tail = &dummy;
   
    dummy->next = NULL;
   
    while(1)
    {
        if( a == NULL)
        {
            tail->next = b ;
            break;
        }
        else if( b == NULL)
        {
            tail->next = a ;
            break;
        }
        else if (a->data <= b->data)
        {
            MoveNode(&(tail->next) , &a);
        }
        else
        {
            MoveNode(&(tail->next) , &a);
        }
        tail = tail->next;
    }
   
    return ( dummy -> next);
}

Reverse a linkes list

struct node {
    int data ;
    struct node* next ;
}

// use pointer to node because we gotta change head reference value in function

void reverseList(node** head)
{
    struct node* current = *head;
    struct node* prev = NULL;
    struct node* next ;
   
   
    while( current != NULL)
    {
        //save next node
        next = current->next;
       
        //shift previous node , reversing two nodes at a time (current and previous)
        current->next = prev ;
        //update prev
        prev = current ;
       
        //update current pointing rest of the list
        current = next ;
       
    }
   
    //update head
    *head = prev ;
}


Simple Visualisation  inside loop

Sample linked list

1 -> 2 -> 3
Iterations :
1 :     1-> NULL (*prev == 1 )  , 2->3 (*current == 2)
2 :     2->1->NULL (*prev == 2) , 3-> NULL
3:     3->2->1-> (*prev == 3)  , NULL

Loop over  ,  update  *head = prev
       

Remove duplicates in a sorted linked list

 Complexity O(n)

struct Node {
    int data ;
    struct Node * next ;
};

 

typedef struct Node * Node ;



void removeDuplicate (Node * head){
    if( head == NULL)
        return ;
    Node next_next = head->next ;
   
    while ( head -> next != NULL)
    {
        if( head->data == head->next->data)
        {
            //remove the next  duplicate node
            head->next = next_next->next;
            free(next_next);
            next_next = head->next ;
           
        }
        //advance only if no deletion occurs , because on deleting a node , we have no info about equality of the current and next (next_next) node
        else {
            head = head->next ;
        }
    }
}

Given 3 linked list , find a triplet such that there's sum equals a given number

    A function to check if there exist a triplet in three given linked list such that the tripplet's sum is equal to a given number
    Let there be 3 linked list a , b , c .
   
    1 Sort list b in ascendinng and c and descending order respectively

    2 For each node in  list a ,check if there exist a triplet traversing list b and c as shown in function below.

    The technique is called Quadratic algorithm for 3 sum problem

    Function assumes list b and c already satisfies 1st step and all list are of same length

#include<iostream>
using namespace std;
struct node {
    int data;
    struct node * next;


};

bool isTripletPresent(struct node* aHead, struct node* bHead,  struct node* cHead, int num)
{
    struct node* a = aHead;
    while (a != NULL)
    {
        struct node* b = bHead;
        struct node* c = cHead;

        while (b != NULL  && c != NULL)
        {
            int sum = a->data + b->data + c->data;
            if (sum == num)
            {
                cout << "Found";
                return true;
            }
            else if (sum < num)
            {
                //look for greater value in b
                b = b->next;
            }
            else {
                //look for smaller value in c
                c = c->next;
            }


                       
        }

        a = a->next;



    }
    cout << "No such triplet ";
    return false;
}

C programme to check if a linked list is circular

// c program to check if a linked list is circular

struct Node {
    int data ;
    struct Node* next ;

};

typedef Node* Node ;

int isCircularLinkedList(Node head)
{
     Node slowPtr = fastPtr = head ;
    
     while (slowPtr && fastPtr )
     {
        slowPtr = slowPtr->next ;
        fastPtr = fastPtr -> next;
       
        if( ! fastPtr )
        {
            return 0 ;
        }
        else {
            fastPtr = fastPtr - > next ;
        }
       
        if( slowPtr = fastPtr )
            return 1 ;
       
     }
    
     return 0 ;
}

C : find middle element using two pointer technique

// c code to find middle element using two pointer technique

struct Node {
    int data ;
    struct Node* next ;

};

typedef Node* Node ;

Node middleNodeOfLinkedList(Node head)
{
    Node slowPtr = fastPtr = head ;
   
    if(head->next != NULL )
    {
        fastPtr = fastPtr->next->next;
    }
   
    while (fastPtr != NULL )
    {
        // check for more nodes  at the node pointed by  fastPtr
        if(fastPtr -> next != NULL)
        {
            //advance fastPtr
            fastPtr = fastPtr->next->next ;
        }
        else {
            return slowPtr;
        }
       
        //advance slow ptr
        slowPtr = slowPtr->next ;
       
   }
  
   return slowPtr;
  
  
}

C Reverse a linked List

// C programme to reverse a linked list

strcut  Node {
    int data ;
    struct Node* next ;
} ;

typedef struct Node* Node ;


//function to reverse a linked list

Node reverseLinkedList (Node head)
{
    Node ptr = NULL ;
    Node newHead  = NULL ;
   
    while ( head != NULL )
    {
        //save head
        ptr = head;
       
        //advance head
        head = head->next;
       
        //advance the value at newHead
        newHead->next = newHead ;
       
        //add the saved node at newHead of list
        newhead = ptr ;
    }
}

Tid Bits Data Structures

 1 :
    Total number of nodes pointing to null in a binary tree with N nodes are N-1
 2:
    Total non leaf nodes in a binary tree with N leaf nodes are N-1
 3 :
    Maximum possible height of a binary tree with N nodes is N , when the binary tree is right or left skewed
 4 :
    Height of a complete binary tree with N nodes log(N)
 5 :
    A simple graph have  one edge connecting two edges  while a multi graph can have more than one edge connecting two vertices
 6 :
    Self loops are allowe in directed graphs but not in undirected graphs
 7:
    Two comman ways of representing graphs are Adjaceny matrix and adjaceny list
 8  :
    In a priority queue , a priority is associated with each element such that insertion and removal is based on priority , but not on arrival time or order
 9:
    A tree is a connected graph with no circuits . Removing an edge in a tree disconnectes one or more nodes , hence a tree is a minimally connected graph .
    Finally all trees are graph , but not vice versa .

Paint Fill

//paint fill function : given a point , a 2d array , and a new color , fill the image (2d-array here) using new color

public enum Color
{  
    Black , White , Red , Yellow , Green
}

public static void boolean PaintFill(Color[][] screen , int x , int  y  ,  Color nColor)
{
    /*
    *   Here x is column index and y is the row index , as happens in screen orientations
    */
   
    if(screen[y][x] == nColor) return false ;
    return PaintFill(screen , int x , int y , screen[y][x] , nColor);
}


public static boolean PaintFill (Color[][] screen , int x  , int y , Color oColor , Color nColor)
{
    //check if the index is out of bounds of the screen
    if ( y < 0  || y > screen.length   || x < 0 || x > screen[0].length)
        return false ;
   
    //if the present point pixel is of old color , recurse coloring the neighbors
    if (screen[y][x] == oColor)
    {
        PaintFill(screen , x-1 , y, oColor , nColor ) ; //left
        PaintFill(screen , x+1 , y, oColor , nColor ) ; //right
        PaintFill(screen , x , y-1, oColor , nColor ) ; //top
        PaintFill(screen , x , y+1, oColor , nColor ) ; //bottom
    }
   
    return true ;
}

Operators C tid bits

1 :
    precedence of comparison operators (<=, >= and ==) is higher than assignment operator =. The result of a comparison operator is either 0 or 1 based on the comparison result

    2 :
     int i = 1, 2, 3;
     printf("%d", i);
     Compile time error : Comma acts as a separator here. The compiler creates an integer variable and initializes it with 1. The compiler fails to create integer variable 2 because 2 is not a valid identifier.
   
     3:
     int i = (1, 2, 3);
     printf("%d", i);
     Output : 3
     The bracket operator has higher precedence than assignment operator. The expression within bracket operator is evaluated from left to right but it is always the result of the last expression which gets assigned.
   
     4:
      int i;
    i = 1, 2, 3;
    printf("%d", i);  Output : 1
    Comma acts as an operator. The assignment operator has higher precedence than comma operator. So, the expression is considered as (i = 1), 2, 3 and 1 gets assigned to variable i.
  
    5 The control in the logical OR goes to the second expression only if the first expression results in FALSE
    6: . An expression doesn't get evaluated inside sizeof operator.
  
    7 :
        This is an another way to convert an alphabet to upper case by resetting its bit positioned at value 32 i.e. 5th bit from the LSB(assuming LSB bit at position 0).
      
        eg : a &= ~32 ; Outputs A  ;
    8:
        We can swap two variables without any extra variable using bitwise XOR operator '^'. Let X and Y be two variables to be swapped. Following steps swap X and Y.

          X = X ^ Y;
          Y = X ^ Y;
          X = X ^ Y ;
           
   

Linked List in C++

#include <iostream>
#include<conio.h>

using namespace std;

class Node {
private :
    int data;
    Node *next;
public :
    void setData( int data ){
        this->data = data;
   }
    void setNext(Node *node) {
        this->next = node;
    }
        Node* getNext(){
        return next;
    }
    int getData() { return data; }

};



class LinkedList
{
 private:
     Node *head;
     static int length ;

public :
   
    LinkedList(){ head = NULL; }
    void insertAtHead(int  );
    void deleteFromHead( );
    void displayList();
    int getLength(){ return length ; }
    bool isEmpty(){ return  (length == 0);  }

   
};
int LinkedList::length;

void LinkedList::insertAtHead(int data){
    Node *node = new Node();
    node->setData(data);

    Node *temp = head;
    head = node;
    node->setNext(temp);
    ++length;

}

void LinkedList::deleteFromHead(){
    if (isEmpty() )
    {
        cout << "List is empty  \n";
    }
    else
    {
        Node *temp = head;
        head = head->getNext();
        delete temp;
        --length;
    }

}

void LinkedList::displayList(){
    Node *temp = head;
   
    if ( isEmpty() ){
        cout << "Empty list";
    }
    else {
        while (temp != NULL)
        {

            int data = temp->getData();
            cout << data << " \n";
            temp = temp->getNext();
        }
    }

}


int main()
{
    LinkedList list;

    list.insertAtHead(1);
    list.insertAtHead(2);
    list.insertAtHead(3);
    list.insertAtHead(4);
    list.insertAtHead(5);

    list.displayList();

    list.deleteFromHead();
    list.deleteFromHead();
    list.deleteFromHead();
    list.deleteFromHead();
    list.deleteFromHead();

    list.displayList();

    getchar();
    return 0;

   



}

Tid-Bits C I/O

1 :
     char array[100];
    printf("%d" , scanf("%s" , arr));
    //input  : Jimmmy
    prints 1  as scan returns number of inputs successfully read
 2: 
    printf(" \"JIMMY %% N  %% JOLLY\"");
   
    output : "JIMMY % N % JOLLY"
   
    (\\\) backslash are used for escaping double quotes
   
 3: prototype of printf() in C :
              int printf(const char *format, ...);
 4:

    The stdout stream is buffered, so will only display what’s in the buffer after it reaches a newline (or when it’s told to)
    eg :
    printf(“\%\n”); prints : %
   
   
  5 :
    Use of backspace \b  and return  \r escape characters is terminal dependent :
        http://stackoverflow.com/questions/17236242/usage-of-b-and-r-in-c
       
   6:
        int main()
            {
               printf(1 + "Jjim");
               return 0;
            }
           
            prints : jim
          
           printf()  prototype as int printf( const char *format , ... ) ; The compiler adds 1 to base address of "Jjim" and sends "jim" as an arguemnts to
           printf() function defined in stdio.h header file .
    7:
            int main()
                {
                    printf("%c ", 5["jimmyjolly"]);
                    return 0;
                }
               
              prints : 'j'
       
          Compiler assumes   5["jimmyjolly"] as *(5 + "jimmyjolly") Adding 5 to base address of the string increments the pointer to point 'j'
                             Applying value-of opertaor gives 'j' as final result
            Same logic for  "jimmyjolly"[5] where  output is j
     
     
      8 :
             gets() can read a string with spaces but a normal scanf() with %s can not.
             gets() doesn't do any array bound testing and should not be used
             use fgets() instead :
                char *fgets(char *s, int n, FILE *stream);
                fgets read at most n-1 characters into the array s, stopping if a newline is encountered, the newline is included in the array, which is terminated by ‘\0'.
                fgets returns s, or NULL if end of file or error occurs.
     9 :
            #include <stdio.h>

            int main()
            {
                char str[50] = {0};
                scanf("%4s", str);
                printf(str);
                getchar();
                return 0;
            }
           
            input :  jimmy
            ouput : jimmy
           statment  scanf("%4s" , str ) ;  Read maximum 4 characters from console where str is a char array variable eg. char str[50];
          
          
        10 :
           
            printf(“%.*s”, n, s); in this statement value of pointer will move till nth character of s , printing n characters

            .* means The precision is not specified in the format string, but as an additional integer value argument preceding the argument that has to be formatted.
        11 :
             printf function returns the number of characters successfully printed on the screen.
         12 :
            The return type of getchar() is int to accommodate EOF which indicates failure
          13 :
             for a CPU with memory mapped I/O ,  I/O protection is ensured by operating system routine (s)

Constrcutor VS static functions to create instances

 Source Effective Java

/*Item 1: Consider static factory methods instead of constructors
 ## Use static method to make instance controlled classes

 *        The normal way for a class to allow a client to obtain an instance of itself is to provide
 *    a public constructor. There is another technique that should be a part of every
 *    programmer’s toolkit. A class can provide a public static factory method, which is
 *  simply a static method that returns an instance of the class. Here’s a simple example
 *  from Boolean (the boxed primitive class for the primitive type boolean). This
  * method translates a boolean primitive value into a Boolean object reference:
*/

        public static Boolean valueOf( boolean b) {
            return b ? Boolean.TRUE : Boolean.FALSE ;
        }
/*page - 27
            One advantage of static factory methods is that, unlike constructors, they
            have names. If the parameters to a constructor do not, in and of themselves,
            describe the object being returned, a static factory with a well-chosen name is easier
            to use and the resulting client code easier to read
           
            page - 29
            A second advantage of static factory methods is that, unlike constructors,
they are not required to create a new object each time they’re invoked This
allows immutable classes (Item 15) to use preconstructed instances, or to cache
instances as they’re constructed, and dispense them repeatedly to avoid creating
unnecessary duplicate objects



           
           
*/