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 .