Sort an array of 0s, 1s or 2-way Partitioning

/*
 * Sort an array of 0s, 1s
 * reference: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
 */
public class Partition2Way {
    int numArr[] = null;
   
    public Partition2Way(){
        numArr = null;
    }
   
    public Partition2Way(int n){
        numArr = new int[n];
    }
   
    public void sort2Way(int a[]){
        int low = 0;
        int mid = 0;
        int high = a.length-1;
        while(mid <= high){
            switch(a[mid]){
                case 0:
                    int t = a[low];
                    a[low] = a[mid];
                    a[mid] = t;
                    low++;
                    mid++;
                    break;
                case 1:
                    mid++;
                    break;
            }
        }
        this.numArr = a;
    }
   
    public void printArr(int a[]){
        System.out.print("Sorted List: ");
        for(int i=0; i<a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
   
    public static void main(String args[]){
        int a[] = {0,1,1,1,0,0,1,1,0,1};
        Partition2Way pw = new Partition2Way(a.length);
        pw.sort2Way(a);
        pw.printArr(pw.numArr);
    }
}

#output:

Sorted List: 0 0 0 0 1 1 1 1 1 1 

Convert a Binary Search Tree to a Doubly Link List

/*
 * Convert a Binary Search Tree to a Doubly Link List
 * Reference: http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/
 */
public class BST2DLL {
    TNode root = null;
 
    public BST2DLL(){
        root = null;
    }
 
    public BST2DLL(TNode t){
        root = t;
    }
 
    public TNode convertTree2DLL(TNode root){
        if(root == null)
            return root;
        if(root.left != null){
            TNode left = convertTree2DLL(root.left);
            for(;left.right != null; left = left.right);
            left.right = root;
            root.left = left;
        }
        if(root.right != null){
            TNode right = convertTree2DLL(root.right);
            for(;right.left != null; right=right.left);
            right.left = root;
            root.right = right;
        }
        return root;
    }
 
    public TNode BST2List(TNode root){
        if(root == null)
            return root;
        root = convertTree2DLL(root);
        while(root.left != null)
            root = root.left;
        return root;
    }
 
    public void printDLL(TNode root){
        System.out.print("\nList\t");
        for(;root!= null; root=root.right)
            System.out.print(root.data+" ");
        System.out.println();
    }
    public static void main(String args[]){
        //Create BST
        BinaryTree bt = new BinaryTree();
        bt.addNode(10);
        bt.addNode(8);
        bt.addNode(6);
        bt.addNode(9);
        bt.addNode(15);
        bt.addNode(12);
        bt.addNode(17);
        bt.inorder(bt.root);
     
        BST2DLL bd = new BST2DLL();
        TNode root = bd.BST2List(bt.root);
        bd.printDLL(root);
    }
}

#output

6 8 9 10 12 15 17 

List 6 8 9 10 12 15 17 

Dynamic Programming Question: maximize profit for wine sale

/**
 * you have a collection of N wines placed next to each other on a shelf. For
 * simplicity, let's number the wines from left to right as they are standing on
 * the shelf with integers from 1 to N, respectively. The price of the i-th wine
 * is pi (prices of different wines can be different).
 * Because the wines get better every year, supposing today is the year 1, on
 * year y the price of the i-th wine will be y*pi, i.e. y-times more than the
 * current year.
 * what is the maximum profit you can get, if you sell the wines in optimal order.
 * So for example, if the prices of the wines are (in the order as they are
 * placed on the shelf, from left to right): p1=1, p2=4, p3=2, p4=3.
 *
 */
public class DP1 {
    int p[] = null;
    int cache[][];
   
    public DP1(){
        p = new int[100];
        cache = new int[100][100];
        for(int i=0; i<100; i++)
            for(int j=0; j<100; j++)
                cache[i][j] = -1;
    }
   
    public DP1(int N){
        p = new int[N];
        cache = new int[N][N];
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                cache[i][j] = -1;
    }
   
    /**
     * Description: Backtracking function to find maximum profit.
     * @param year : starts from 1 to N-1
     * @param be : beginning of price array
     * @param en : end of price array
     * @return : maximized profit
     */
    public int maxProfit(int year, int be, int en){
        if(be>en)
            return 0;
        return Math.max((this.maxProfit(year+1, be+1, en)+year*this.p[be]),(this.maxProfit(year+1, be, en-1) + year*p[en]));
    }
   
    /*
     * Dynamic Programming Approach
     */
    public int maxDPProfit(int be, int en){
        if(be > en)
            return 0;
       
        if(cache[be][en] != -1)
            return cache[be][en];
       
        int year = this.p.length - (en-be+1) + 1;
        cache[be][en] = Math.max((this.maxDPProfit(be+1, en) + year*p[be]),(this.maxDPProfit(be, en-1)+year*p[en]));
        return cache[be][en];
    }
   
    public static void main(String args[]){
        DP1 dp = new DP1();
        int p[] = new int[]{1,4,2,3};
        dp.p = p;
        int profit = dp.maxProfit(1, 0, 3);
        System.out.println("Profit: " + profit);
        //DP
        int dpprofit = dp.maxDPProfit(0, 3);
        System.out.println("DP Profit: " + dpprofit);
    }
}

#output:

Profit: 29

DP Profit: 29

Given an array of integers(+ve,-ve,0 or duplicates). Find n print all triplets such that a+b+c=0

/**
   * Given an array of integers(+ve,-ve,0 or duplicates). Find n print all triplets such that a+b+c=0.
   * e.g. Let A = -1 0 9 5 -5 2 3
   * Answer = {0 5 -5} {-5 2 3}.
   * Expected : Time O(n2) Space O(1)
 */
public class Prob3Sum {

    public void find3Sum(int A[]){
        for(int i=0; i<A.length; i++){
            int l = i+1;
            int r = A.length - 1;
            while(l<r){
                if(A[i] + A[l] + A[r] == 0){
                    System.out.println("Sum: " + A[i] + " " + A[l] + " " + A[r]);
                }
                if(A[i] + A[l] + A[r] > 0)
                    r--;
                else
                    l++;
            }
        }
    }
   
    public static void main(String args[]){
        QuickSort sort = new QuickSort();
        sort.A = new int[]{-1, 0, 9, 5, -5, 2, 3};
        sort.quickSort(sort.A, 0, sort.A.length-1);
        sort.printArr();
       
        Prob3Sum ps = new Prob3Sum();
        ps.find3Sum(sort.A);
       
    }
}

#output

Sorted: -5, -1, 0, 2, 3, 5, 9, 

Sum: -5 0 5

Sum: -5 2 3

Level Order Traversal for Binary Tree

    public void levelTraversal(TNode root) {
        TNodeQueue queue = new TNodeQueue();
        if(root != null){
            queue.push(root);
            while(!queue.isEmpty()){
                //System.out.println("Queue: " + queue.isEmpty());
                TNode tmp = queue.pop();
                System.out.print(tmp.data + " ");
                if(tmp.left != null)
                    queue.push(tmp.left);
                if(tmp.right != null)
                    queue.push(tmp.right);
            }
        }
    }

# output

Inorder:

2 4 6 8 9 10 

Level Order Traversal: 

8 4 9 2 6 10 

Stack with TNode (Tree Node)

public class NodeStack {

    TNode stack[] = null;
    int top = 0;

    //int ssize = 0;
    NodeStack(int n) {
        stack = new TNode[n];
    }

    NodeStack() {
        stack = new TNode[100];
    }

    public boolean isEmpty() {
        if (top < 0) {
            return true;
        } else {
            return false;
        }
    }

    public void printPop() {
        System.out.println("Poppoed " + this.pop().data);
    }

    public void push(TNode p) {
        if (top < stack.length) {
            stack[top++] = p;
        }
        //System.out.println("Top: " + top);
    }

    public TNode top(){
        if(top>0)
            return stack[top-1];
        return null;
    }
    public TNode pop() {
        TNode p = null;
        if (top > 0) {
            p = stack[--top];
        }
        //System.out.println("Top: " + top);
        return p;
    }

    public void printStack() {
        System.out.print("Stack [LIFO order]: ");
        for (int i = this.top - 1; i >= 0; i--) {
            System.out.print(stack[i].data + " ");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        NodeStack s = new NodeStack();
        s.push(new TNode(10));
        s.push(new TNode(15));
        s.push(new TNode(20));
        s.push(new TNode(25));
        s.printStack();
        s.printPop();
        s.printPop();
        s.push(new TNode(19));
        s.push(new TNode(24));
        s.printStack();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printStack();
    }
}

# output:

Stack [LIFO order]: 25 20 15 10 

Poppoed 25

Poppoed 20

Stack [LIFO order]: 24 19 15 10 

Poppoed 24

Poppoed 19

Poppoed 15

Poppoed 10

Stack [LIFO order]: 

Iterative or non-recursive version of Binary Tree Inorder, Preorder & Postorder

 public void nonRecursiveInorder(TNode root) {
        NodeStack s = new NodeStack(this.totNode);
        while (true) {
            while (root != null) {
                s.push(root);
                //System.out.println()
                root = root.left;
            }
            if (s.isEmpty()) {
                break;
            }
            root = s.pop();
            if (root == null) {
                break;
            }
            System.out.print(root.data + " ");
            root = root.right;
        }
    }

    public void nonRecursivePreorder(TNode root) {
        NodeStack s = new NodeStack(this.totNode);
        while (true) {
            while (root != null) {
                System.out.print(root.data + " ");
                s.push(root);
                //System.out.println()
                root = root.left;
            }
            if (s.isEmpty()) {
                break;
            }
            root = s.pop();
            if (root == null) {
                break;
            }
            root = root.right;
        }
    }

    public void nonRecursivePostorder(TNode root) {
        NodeStack s = new NodeStack(this.totNode);
        while (true) {
            while(root != null){
                if(root.right != null)
                    s.push(root.right);
                s.push(root);
                root = root.left;
            }
            if(s.isEmpty())
                break;
            root = s.pop();
            if(root == null)
                break;
            if(root.right != null && s.top() == root.right){
                s.pop();
                s.push(root);
                root = root.right;
            }else{
                System.out.print(root.data + " ");
                root = null;
            }
        }
    }

[Reference: http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/]

For TNode definition, please check my previous post.

Largest Sum Contiguous Subarray..

Reference: http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

public class MaxSubArray {

    /*
    Notes: Algorithm doesn't work for all negative numbers. It simply returns 0
    if all numbers are negative. For handling this we can add an extra phase
    before actual implementation. The phase will look if all numbers are negative,
    if they are it will return maximum of them (or smallest in terms of absolute
    value). There may be other ways to handle it though.
    */
    public int findMaxSubArray(int a[]){
        int max_so_far = 0;
        int max_ending_here = 0;
        for(int i=0; i<a.length; i++){
            max_ending_here += a[i];
            if(max_ending_here < 0)
                max_ending_here = 0;
            if(max_so_far < max_ending_here)
                max_so_far = max_ending_here;
        }
        return max_so_far;
    }
 
    /*
     * Another implementation which takes care of all +ve as well as -ve value.
     */
    public int findMaxSubArray2(int a[]){
        int max_so_far = a[0];
        int current_max = a[0];
        for(int i=1; i<a.length; i++){
            current_max = Math.max(a[i], current_max+a[i]);
            max_so_far = Math.max(max_so_far, current_max);
        }
        return max_so_far;
    }
 
    public static void main(String args[]){
        MaxSubArray msa = new MaxSubArray();
        int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
        int res = msa.findMaxSubArray(a);
        System.out.println("MaxSum: " + res);
        int b[] = {-2, -3, -4, -1, -2, -1, -5, -3};
        res = msa.findMaxSubArray2(b);
        System.out.println("MaxSum2: " + res);
    }
}

# Output

MaxSum: 7

MaxSum2: -1

To divide an array such that the sum of left half and right half is minimum.

/*
Prob: To divide an array such that the sum of left half and right half is minimum or partition an array in equal halves with minimum sum difference.
A = 1,2,3,4,5,6,7,8,9,10 #Array is not sorted
left=1,4,5,8,9,1 (sum=27) right=2,3,6,7,10(sum=28)
Complexity: O(n^2) Type: GREEDY
*/

public class DivideArray {

    int A[];
    boolean used[];
    int partition[];
    int left = 0;
    int right = 0;

    DivideArray() {
        A = null;
        used = null;
        partition = null;
        left = -1;
        right = -1;
    }

    DivideArray(int N) {
        A = new int[N];
        used = new boolean[N];
        partition = new int[N];
        left = 0;
        right = N - 1;
    }

    public int findNearest(int A[], boolean used[], int idx) {
        int min = 99999999;
        int minIndex = -1;
        for (int i = 0; i < A.length; i++) {
            if (i == idx) {
                continue;
            }
            if (used[i]) {
                continue;
            }
            int diff = Math.abs(A[idx] - A[i]);
            if (diff < min) {
                min = diff;
                minIndex = i;
            }
        }
        return minIndex;
    }

    public void partitionArr(int A[], boolean used[], int partition[]) {
        for (int i = 0; i < A.length; i++) {
            if (used[i]) {
                continue;
            }
            int j = findNearest(A, used, i);
            used[i] = true;
            if (j >= 0) {
                used[j] = true;
                if (sumLeft(partition, left) <= sumRight(partition, right)) {
                    partition[left++] = Math.max(A[i], A[j]);
                    partition[right--] = Math.min(A[i], A[j]);
                } else {
                    partition[left++] = Math.min(A[i], A[j]);
                    partition[right--] = Math.max(A[i], A[j]);
                }
            } else {
                // if size of array is odd
                if (sumLeft(partition, left) <= sumRight(partition, right)) {
                    partition[left++] = A[i];
                } else {
                    partition[right--] = A[i];
                }

            }
        }
        this.partition = partition;
    }

    public int sumLeft(int par[], int left) {
        int sum = 0;
        for (int i = 0; i <= left; i++) {
            sum += par[i];
        }
        return sum;
    }

    public int sumRight(int par[], int right) {
        int sum = 0;
        for (int i = right; i < par.length; i++) {
            sum += par[i];
        }
        return sum;
    }

    public static void main(String args[]) {

        Scanner sin = new Scanner(System.in);
        int N = sin.nextInt();
        DivideArray da = new DivideArray(N);

        for (int i = 0; i < N; i++) {
            da.A[i] = sin.nextInt();
        }
        // call partition function
        da.partitionArr(da.A, da.used, da.partition);
        System.out.print("LeftArray: ");
        for (int i = 0; i < da.left; i++) {
            System.out.print(da.partition[i] + " ");
        }
        System.out.print("\t(sum=" + da.sumLeft(da.partition, da.left - 1) + ")\nRightArray: ");
        for (int i = da.right + 1; i < N; i++) {
            System.out.print(da.partition[i] + " ");
        }
        System.out.println("\t(sum=" + da.sumRight(da.partition, da.right + 1) + ")");

    }
}


## Output
10
1 2 3 4 5 6 7 8 9  10
LeftArray: 2 3 6 7 10     (sum=28)
RightArray: 9 8 5 4 1     (sum=27)

9
9
1 2 3 4 5 6 7 8 9
LeftArray: 2 3 6 7 9     (sum=27)
RightArray: 8 5 4 1     (sum=18)

Quick Sort (in java)

public class QuickSort {

    public int A[] = null;

    public int partition(int A[], int low, int high) {
        int left, right, pivot_item = A[low];
        left = low;
        right = high;

        while (left < right) {
       
            while (left < right && A[left] <= pivot_item) {
                left++;
            }
            while (A[right] > pivot_item) {
                right--;
            }

            if (left < right) {
                int temp = A[right];
                A[right] = A[left];
                A[left] = temp;
            }
        }
     
        A[low] = A[right];
        A[right] = pivot_item;
        return right;
    }

    public void printArr() {
        System.out.print("Sorted: ");
        for (int i = 0; i < this.A.length; i++) {
            System.out.print(this.A[i] + ", ");
        }
        System.out.println();
    }

    public void quickSort(int A[], int low, int high) {
        int pivot;
        if (high > low) {
            pivot = partition(A, low, high);
           // System.out.println("Pivot: " + pivot);
            quickSort(A, low, pivot - 1);
            quickSort(A, pivot + 1, high);
        }
       // this.printArr();
    }

    public static void main(String args[]) {
        QuickSort sort = new QuickSort();
        sort.A = new int[]{2, 4, 5, 7, 1, 2, 3, 6};
        sort.quickSort(sort.A, 0, 7);
        // print sorted Array
        sort.printArr();
    }
}

Merge Sort in Java

public class MergeSort {

    public int A[], temp[]; //, size=0;

    MergeSort(int n) {
        A = new int[n];
        temp = new int[n];
        //size = n;
    }

    MergeSort() {
        A = null;
        temp = null;
        //size = 0;
    }

    public void mergeSort(int A[], int left, int right) {
        int mid;
        //System.out.println("A-len: " + this.A.length + " Temp-len: " + this.temp.length);
        if (left < right) {
            mid = (right + left) / 2;
            mergeSort(A, left, mid);
            mergeSort(A, mid + 1, right);
            merge(A, left, mid, right);
        }
    }

    public void merge(int A[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int L1[] = new int[n1];
        int L2[] = new int[n2];
     
        for (int i = 0; i < n1; i++) {
            L1[i] = A[left + i];
        }

        for (int i = 0; i < n2; i++) {
            L2[i] = A[mid + i + 1];
        }

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L1[i] <= L2[j]) {
                A[k] = L1[i];
                i++;
            } else {
                A[k] = L2[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            A[k] = L1[i];
            i++;
            k++;
        }

        while (j < n2) {
            A[k] = L2[j];
            j++;
            k++;
        }

    }

    public void printArr() {
        System.out.print("Sorted: ");
        for (int i = 0; i < this.A.length; i++) {
            System.out.print(this.A[i] + ", ");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        MergeSort sort = new MergeSort();
        sort.A = new int[]{2, 4, 5, 7, 1, 2, 3, 6};
        sort.temp = new int[8];
        sort.mergeSort(sort.A, 0, 7);
        // print sorted Array
        sort.printArr();
    }
}

Find if a substring is exist in a given string !!

public class MatchString {
 
    public int matchStr(String str, String sub){
     
        if(str.length() < sub.length())
            return -1;
     
        for(int i=0; i<str.length() && (str.length()-i >= sub.length()); i++){
            String temp = str.substring(i, i+sub.length());
            //System.out.println("temp: " + temp);
            if(temp.equalsIgnoreCase(sub))
                return 1;
        }
     
        return -1;
    }
 
    public static void main(String args[]){
     
        MatchString ms = new MatchString();
        int res = ms.matchStr("abcdefgh", "cdfe");
        if(res < 0)
            System.out.println("Not Found!");
        else
            System.out.println("Match!");
    }
}

Find a number from sorted list where start and end of list is not known

Prob: find a number from a sorted list where start and end of list is not known. The moving pointer will rotate over from max to min and vice versa.

public class FindANumber {

    public int bTreeRotated(int A[], int start, int finish, int data) {
        int mid = start + (finish - start) / 2;
        if (start > finish) {
            return -1;
        }
        if (A[mid] == data) {
            return mid;
        } else if (A[start] <= A[mid]) {
            if (data >= A[start] && data <= A[mid]) {
                return bTreeRotated(A, start, mid - 1, data);
            } else {
                return bTreeRotated(A, mid + 1, finish, data);
            }
        } else //if(A[mid] <= A[finish]){
        if (data >= A[mid] && data <= A[finish]) {
            return bTreeRotated(A, mid + 1, finish, data);
        } else {
            return bTreeRotated(A, start, mid - 1, data);
        }
    }
 
    public static void main(String args[]){
        FindANumber fan = new FindANumber();
        int A[] = new int[]{15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14};
        int res = fan.bTreeRotated(A, 0, 11, 5);
        if(res < 0)
            System.out.println("Not Found!!");
        else
            System.out.println("Fund at " + res);
     
    }
}

Find the min number of coin to get sum S

public class FindMinCoin {

    public void findMinCoin() {
        int valueCoins[] = new int[]{1, 3, 5};
        int sum = 11;
        int min[] = new int[sum + 1];
       
        // assign sum to infinity
        for(int i=1; i<min.length; i++)
            min[i] = 999999;
       
        // initialize min sum = 0
        min[0] = 0;
       
        for(int i=1; i<= sum; i++)
            for(int j=0; j<valueCoins.length; j++){
                if(valueCoins[j] == i){
                    min[i] = 1;
                }else if((valueCoins[j] < i) && (((min[i-valueCoins[j]]) + 1) < min[i])){
                    min[i] = (min[i-valueCoins[j]]) + 1;
                }
            }
       
        for(int k=1; k<min.length; k++){
            System.out.println(k + " " + min[k] + " ");
        }      
    }

    public void printArr(int coins[][], int min[]){
        System.out.println("Min:-----------");
        for(int i=0; i<min.length; i++)
            System.out.println("min[" + i + "] = " + min[i]);
       
        System.out.println("Coins:--------");
        for(int i=0; i<coins.length; i++)
            System.out.println("conins[" + i + "][0] = " + coins[i][0] + "\tcoins[" + i + "][1]=" + coins[i][1]);
    }
   
    public static void main(String args[]) {
        FindMinCoin fmc = new FindMinCoin();
        fmc.findMinCoin();
    }
}

Circular Linked List

public class CLinkedList {

    private Node head = null; //new Node();

    public int listLength() {
        int cnt = 0;
        Node t = this.head;
       
        do{
           cnt++;
           t=t.next;
        }while(t != this.head);
       
        return cnt;
    }

    public void insertNode(int dat, int pos){
        Node t = this.head;
        Node prev = null;
        int i = 0;
        do{
            prev = t;
            t = t.next;
            i++;
        }while(i<pos-1 && t != this.head);
       
        Node p = new Node(dat);
        p.next = prev.next;
        prev.next = p;
    }
   
    public void printList() {
        Node t = this.head; //t.next != this.head; t = t.next)
        do {
            System.out.print(t.data + " ");
            t = t.next;
        }while(t != this.head);
        System.out.println();
    }

    public void reverseList() {
        Node nxt = this.head;
        Node prev = null;
        Node htemp = this.head;

        do{
            Node tmp = nxt.next;
            nxt.next = prev;
            prev = nxt;
            nxt = tmp;
        }while (nxt != this.head);
        htemp.next = prev;
        this.head = prev;
    }

    public void addNode(int dat) {
        Node p = new Node(dat);
        Node t = this.head;
        if (this.head == null) {
            this.head = p;
            this.head.next = this.head;
        } else {
            while (t.next != this.head) {
                t = t.next;
            }
            p.next = t.next;
            t.next = p;
        }
    }

    public void deleteNode(int dat) {
        Node t = this.head;
        Node prev = t;

        while (t.next != this.head) {
            if (t.data == dat) {
                prev.next = t.next;
                //break;
            }
            prev = t;
            t = t.next;
        }
    }

    public void sortList() {
        Node t = this.head;
        //for (; t.next != this.head; t = t.next) {
            //for (Node r = t.next; r.next != this.head; r = r.next) {
        do{
            Node r = t;
            do{
                r = r.next;
                if (t.data > r.data) {
                    int temp = t.data;
                    t.data = r.data;
                    r.data = temp;
                }
                //r = r.next;
            }while(r.next != this.head);
            t = t.next;
        }while(t.next != this.head);
    }

    public static void main(String args[]) {
        CLinkedList ll = new CLinkedList();
        ll.addNode(10);
        ll.addNode(15);
        ll.addNode(18);
        ll.addNode(1);
        ll.addNode(20);
        ll.addNode(3);
        ll.addNode(7);
        ll.printList();
        System.out.println("Length: " + ll.listLength());
        ll.reverseList();
        ll.printList();
        ll.sortList();
        ll.printList();
        ll.deleteNode(18);
        ll.deleteNode(3);
        ll.printList();
        ll.insertNode(3, 3);
        ll.insertNode(21, 5);
        ll.insertNode(18, 7);
        ll.printList();
        ll.sortList();
        ll.printList();
        System.out.println("Length: " + ll.listLength());
    }
}

Stack using Array

public class Stack {
    int stack[] = new int[100];
    int top = 0;
    //int ssize = 0;
   
     public void printPop(){
         System.out.println("Poppoed " + this.pop());
     }
   
    public static void main(String args[]){
        Stack s = new Stack();
        s.push(10);
        s.push(15);
        s.push(20);
        s.push(25);
        s.printStack();
        s.printPop();
        s.printPop();
        s.push(19);
        s.push(24);
        s.printStack();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printStack();
    }
   
    public void push(int p){
        if(top < stack.length){
            stack[top++] = p;
        }
        //System.out.println("Top: " + top);
    }
   
    public int pop(){
        int p = -99999;
        if(top > 0)
            p = stack[--top];
        //System.out.println("Top: " + top);
        return p;
    }
   
    public void printStack(){
        System.out.print("Stack [LIFO order]: ");
        for(int i=this.top-1; i>=0; i--){
            System.out.print(stack[i] + " ");
        }
        System.out.println();
    }
}

Node & TNode Class declaration for Linked List & Tree

public class Node{
    int data;
    Node next;
    Node prev;
 
    Node(){
        data = 0;
        next = null;
        prev = null;
    }
 
    Node(int p){
        data = p;
        next = null;
        prev = null;
    }
}

public class TNode {

    int data;
    TNode left;
    TNode right;
    TNode parent;

    TNode() {
        data = -999999;
        left = null;
        right = null;
        parent = null;
    }

    TNode(int p) {
        data = p;
        left = null;
        right = null;
        parent = null;
    }
}

Reading input from Terminal in Java

public class ReadIO {

    public int readInt(Scanner sin) {
        return sin.nextInt();
    }
   
    public double readDouble(Scanner sin){
        return sin.nextDouble();
    }
   
    public String readString(Scanner sin){
        if(sin.nextLine() != "")
            return sin.nextLine();
        return sin.nextLine();
    }
   
    public char readChar(Scanner sin){
        return sin.next().charAt(0);
    }
   
    public float readFloat(Scanner sin){
        return sin.nextFloat();
    }
   
    public static void main(String args[]){
        ReadIO io = new ReadIO();
        Scanner sin = new Scanner(System.in);
        System.out.println("ReadInteger: " + io.readInt(sin));
        System.out.println("ReadDouble: " + io.readDouble(sin));
        System.out.println("ReadString: " + io.readString(sin));
        System.out.println("ReadChar: " + io.readChar(sin));
        System.out.println("ReadFloat: " + io.readFloat(sin));
    }
}

Stack Using Linked List

public class ListStack {
    Node stack = null;
   // int top = 0;
 
     public void printPop(){
         System.out.println("Poppoed " + this.pop());
     }
   
    public static void main(String args[]){
        ListStack s = new ListStack();
        s.push(10);
        s.push(15);
        s.push(20);
        s.push(25);
        s.printStack();
        s.printPop();
        s.printPop();
        s.push(19);
        s.push(24);
        s.printStack();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printStack();
    }
 
    public void push(int p){
        Node tmp = new Node(p);
        if(stack == null){
            stack = tmp;
        }else{
            tmp.next = stack;
            stack = tmp;
        }      
    }
 
    public int pop(){      
        Node tmp = null;
        if(stack != null){
            tmp = stack;
            stack = stack.next;
            return tmp.data;
        }
        return -99999;
    }
 
    public void printStack(){
        System.out.print("Stack [LIFO order]: ");
        for(Node t=stack; t != null; t=t.next){
            System.out.print(t.data + " ");
        }
        System.out.println();
    }
}

Single Linked List

public class LinkedList {

    private Node head = null; //new Node();

    public int listLength() {
        int cnt = 0;
        for (Node t = this.head; t != null; t = t.next) {
            cnt++;
        }
        return cnt;
    }

    public void insertNode(int dat, int pos){
        Node t = this.head;
        Node prev = null;
     
        for(int i=0; i<pos && t != null; i++, t=t.next)
            prev = t;
     
        Node p = new Node(dat);
        p.next = prev.next;
        prev.next = p;
    }
 
    public void printList() {
        for (Node t = this.head; t != null; t = t.next) {
            System.out.print(t.data + " ");
        }
        System.out.println();
    }

    public void reverseList() {
        Node nxt = this.head;
        Node prev = null;

        while (nxt != null) {
            Node tmp = nxt.next;
            nxt.next = prev;
            prev = nxt;
            nxt = tmp;
        }
        this.head = prev;
    }

    public void addNode(int dat) {
        Node p = new Node(dat);
        Node t = this.head;
        if (this.head == null) {
            this.head = p;
        } else {
            while (t.next != null) {
                t = t.next;
            }
            t.next = p;
        }
    }

    public void deleteNode(int dat) {
        Node t = this.head;
        Node prev = t;

        while (t != null) {
            if (t.data == dat) {
                prev.next = t.next;
            }
            prev = t;
            t = t.next;
        }
    }

    public void sortList() {
        Node t = this.head;
        for (; t != null; t = t.next) {
            for (Node r = t.next; r != null; r = r.next) {
                if (t.data > r.data) {
                    int temp = t.data;
                    t.data = r.data;
                    r.data = temp;
                }
            }
        }
    }

    public static void main(String args[]) {
        LinkedList ll = new LinkedList();
        ll.addNode(10);
        ll.addNode(15);
        ll.addNode(18);
        ll.addNode(1);
        ll.addNode(20);
        ll.addNode(3);
        ll.addNode(7);
        ll.printList();
        System.out.println("Length: " + ll.listLength());
        ll.reverseList();
        ll.printList();
        ll.sortList();
        ll.printList();
        ll.deleteNode(18);
        ll.deleteNode(3);
        ll.printList();
        ll.insertNode(3, 3);
        ll.insertNode(21, 5);
        ll.insertNode(18, 7);
        ll.printList();
    }
}

Hiiiiiii........

Hi Guys,

I have created this blog for learning purpose. I will be sharing my java code for algorithms & data structure. This may includes algorithm questions from different company's interview. So stay tuned and please do give your feedback on my code.

thanks!