DSA - Learning

[DevShivmohan]

class Solution{

    /**
     * sample below test cases below
     * <p>
     * {()[]} - true
     * {()[)} - false
     * {((()))[]} - true
     * {{} - false
     * [(()){}] - true
     *
     * @param parenthesis
     * @return
     */
    public static boolean isValidParenthesis(char[] parenthesis) {
        Stack<BracketCloseable> stack = new Stack<>();
        for (int i = 0; i < parenthesis.length; i++) {
            if (!isCloseableBracket(parenthesis[i]))
                stack.push(new BracketCloseable(parenthesis[i], null));
            else {
                var lastElementFromStack = stack.lastElement();
                if (lastElementFromStack.getClose() != null)
                    return false;
                else {
                    if (getCloseableBracket(lastElementFromStack.getOpen()) != parenthesis[i])
                        return false;
                    else {
                        lastElementFromStack.setClose(parenthesis[i]);
                        stack.remove(lastElementFromStack);
                    }
                }
            }
        }
        return true;
    }

    private static char getCloseableBracket(char ch) {
        if (ch == '(')
            return ')';
        else if (ch == '{')
            return '}';
        else if (ch == '[')
            return ']';
        return 0;
    }

    private static boolean isCloseableBracket(char ch) {
        if (ch == ')')
            return true;
        else if (ch == '}')
            return true;
        else if (ch == ']')
            return true;
        return false;
    }

    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    static class BracketCloseable {
        Character open;
        Character close;
    }

}

[DevShivmohan]

Stack implementation using generics in Java

public class StackImpl<T> {
    private int stackSize;
    private T[] stackArray;
    private int top;

    public StackImpl(int stackSize){
        this.stackSize=stackSize;
        stackArray=(T[]) new Object[stackSize];
        this.top=-1;
    }

    public void push(T data){
        if(top==stackSize-1){
            System.out.println("Stack has full");
            return;
        }
        stackArray[++top]=data;
    }

    public void pop(){
        if(top==-1){
            System.out.println("Stack has empty");
            return;
        }
        stackArray[top--]=null;
    }

    public void show(){
        for(int i=0;i<=top;i++){
            System.out.print(stackArray[i]+"\t");
        }
        System.out.println();
    }

    public void increaseStackSize(int newStackSize){
        this.stackSize=newStackSize;
        T[] tempArray=(T[]) new Object[stackSize];
        for(int i=0;i<stackArray.length;i++)
            tempArray[i]=stackArray[i];
        stackArray=tempArray;
    }

    public static void main(String[] args) {
        StackImpl<Integer> stack=new StackImpl(5);
        stack.pop();
        stack.push(12);
        stack.push(13);
        stack.push(14);
        stack.push(15);
        stack.increaseStackSize(10);
        stack.push(16);
        stack.push(17);
        stack.push(18);
        stack.push(19);
        stack.push(20);
        stack.push(21);
        stack.show();
        stack.pop();
        stack.show();
        stack.pop();
        stack.show();
    }
}

[DevShivmohan]

Simple Queue implementation using Generics in Java

public class QueueImpl<T> {
    private int rear;
    private int front;
    private int queueSize;
    private T[] queueArray;

    public QueueImpl(int queueSize){
        this.queueSize=queueSize;
        queueArray=(T[]) new Object[queueSize];
        rear=-1;
        front=-1;
    }

    public void enqueue(T data){
        if(front==0 && rear==queueSize-1){
            System.out.println("Queue has full");
            return;
        }
        if(front==-1)
            front=0;
        queueArray[++rear]=data;
    }

    public void dequeue(){
        if(front==-1){
            System.out.println("Queue has empty");
            return;
        }
        if(front>=rear){
            /*If both pointer has same index then we need to reset the queue*/
            front=-1;
            rear=-1;
        }else
            queueArray[front++]=null;
    }

    public void show(){
        if(front==-1){
            System.out.println("Queue has empty");
            return;
        }
        for(int i=front;i<=rear;i++)
            System.out.print(queueArray[i]+"\t");
        System.out.println();
    }

    public static void main(String[] args) {
        QueueImpl<Integer> queue= new QueueImpl<>(4);
        queue.enqueue(11);
        queue.enqueue(12);
        queue.enqueue(13);
        queue.enqueue(14);
        queue.show();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.show();
    }
}

[DevShivmohan]

Singly Linked list implementation using generics in Java

class Node<T>{
    Node next;
    T data;
    public Node(T data){
        this.data=data;
    }
}

public class LinkedListImpl<T> {
    private Node head;
    private int length;

    public LinkedListImpl(){
        head=null;
    }

    public void add(T data){
        Node node=new Node<>(data);
        if(head==null)
            head=node;
        else{
            Node tempNode=head;
            while(tempNode.next!=null)
                tempNode=tempNode.next;
            tempNode.next=node;
        }
        length++;
    }

    /**
     * Remove nodes according to LIFO
     */
    public void remove(){
        if(length==0){
            System.out.println("Linked list has empty");
            return;
        }
        else if(length==1)
            head=null;
        else{
            Node tempNode=head;
            Node prevNode=head;
            while (tempNode.next!=null){
                tempNode=tempNode.next;
                if(tempNode.next!=null)
                    prevNode=tempNode;
            }
            prevNode.next=null;
        }
        length--;
    }

    public void show(){
        StringBuilder stringBuilder=new StringBuilder("{");
        if(length==0){
            System.out.println("Linked list has empty");
            return;
        }else {
            Node tempNode=head;
            while (tempNode.next!=null){
                stringBuilder.append(tempNode.data).append(",");
                tempNode=tempNode.next;
            }
            stringBuilder.append(tempNode.data);
            stringBuilder.append("}");
        }
        System.out.println(stringBuilder);
    }

    public static void main(String[] args) {
        LinkedListImpl<Integer> linkedList=new LinkedListImpl<>();
        linkedList.add(11);
        linkedList.add(12);
        linkedList.add(13);
        linkedList.add(14);
        linkedList.add(15);
        linkedList.show();
        linkedList.remove();
        linkedList.show();
    }
}

Doubly linked list implementation using generics with sorting

class LinkNode<T extends Comparable<T>> implements Comparable<LinkNode<T>>{
    protected LinkNode prevNode;
    protected LinkNode nextNode;
    protected T data;

    public LinkNode(T data){
        this.data=data;
    }

    public T getT(){
        return data;
    }

    @Override
    public int compareTo(LinkNode<T> o) {
        return getT().compareTo(o.getT());
    }
}

public class DoublyLinkedList<T extends Comparable<T>> {
    /* root node */
    private LinkNode head;
    /* leaf node */
    private LinkNode tail;
    private int length;

    /**
     * add a new node
     * @param data
     */
    public void addNode(T data){
        LinkNode node=new LinkNode<T>(data);
        if(length==0){
            head=node;
        }
        else {
            tail.nextNode=node;
            node.prevNode=tail;
        }
        tail=node;
        length++;
    }

    /**
     * deletion from last node [LIFO]
     */
    public void remove(){
        if(length==1){
            head=null;
            tail=null;
        }
        else {
            tail=tail.prevNode;
            tail.nextNode=null;
        }
        length--;
    }

    public int length(){
        return length;
    }

    /**
     * back traversal
     */
    public void show(){
        StringBuilder stringBuilder=new StringBuilder("{");
        LinkNode tempNode=head;
        while (tempNode.nextNode!=null){
            stringBuilder.append(tempNode.data).append(",");
            tempNode=tempNode.nextNode;
        }
        stringBuilder.append(tempNode.data).append("}");
        System.out.println(stringBuilder.toString());
    }

public LinkNode<T> getTailNode(){
        return tail;
    }

    public LinkNode<T> getHeadNode(){
        return head;
    }

    /**
     * sorting element in ascending order
     */
    public void sort(){
        LinkNode current=head,index=null;
        Comparable temp;
        if(head==null)
            return;
        while (current!=null){
            index=current.nextNode;
            while (index!=null){
                if(current.data.compareTo(index.data)>0){
                    temp=current.data;
                    current.data=index.data;
                    index.data=temp;
                }
                index=index.nextNode;
            }
            current=current.nextNode;
        }
    }

    public static void main(String[] args) {
        DoublyLinkedList<Integer> doublyLinkedList=new DoublyLinkedList();
        doublyLinkedList.addNode(2);
        doublyLinkedList.addNode(5);
        doublyLinkedList.addNode(13);
        doublyLinkedList.addNode(14);
        doublyLinkedList.addNode(18);
        doublyLinkedList.addNode(11);
        doublyLinkedList.addNode(1);
        doublyLinkedList.addNode(8);
        doublyLinkedList.addNode(9);
        doublyLinkedList.show();
        doublyLinkedList.sort();
        doublyLinkedList.show();
    }
}

Add two linked list

/**
     * add two linked list without changing its order
     * @param doublyLinkedList1
     * @param doublyLinkedList2
     * @return
     */
    public static DoublyLinkedList<Integer> addTwoList(DoublyLinkedList<Integer> doublyLinkedList1, DoublyLinkedList<Integer> doublyLinkedList2){
        LinkNode<Integer> tempNode= doublyLinkedList2.getHeadNode();
        while (tempNode!=null){
            doublyLinkedList1.addNode(tempNode.data);
            tempNode=tempNode.nextNode;
        }
        return doublyLinkedList1;
    }

[DevShivmohan]

Tree data structure

• A tree is a non-linear and hierarchical data structure that consists of nodes connected by edges
• Terminology
  • Node - Node contain data item , left and right pointer.
  • Edge - It is link between any two nodes.
  • Root node - It is a top most node of a tree.
  • Height of a node - Its no. of edges from the node to deepest leaf node (Also called path of a node to the leaf node).
  • Depth of a node - The depth of a node are no. of edges from root to the node.
  • Height of a tree - The height of the root node or depth of the deepest node.
  • Degree of a node - No. of branches of the node .
  • Forest - A collection of disjoint of tree.
• Types of tree
  • Binary tree - A binary tree is a tree data structure that in which each parent node can have at most two child node. Each node of a binary tree consists of three part.
    • data item
    • left child address
    • right child address
  • Types of Binary tree
    • Full binary tree - A tree that each parent/internal node has either two or no children.
    • Perfact binary tree - A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.
    • Complete binary tree - Complete binary tree just like as full binary tree, only these differences
      • Every level must be completely filled.
      • All the leaf elements must lean towards the left.
      • The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree.
    • Degenerate or pathological tree - A degenerate or pathological tree is the tree having a single child either left or right.
    • Skewed binary tree - A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by the left nodes or the right nodes. Thus, there are two types of skewed binary tree: left-skewed binary tree and right-skewed binary tree.
    • Balanced binary tree - It is a type of binary tree in which the difference between the height of the left and the right subtree for each node is either 0 or 1.

Binary tree code representation -

• Insertion of node in Binary tree - Root node , Left node < Root node and Right node > Root node.
• Binary tree traversal
  • In-order traversal - visit left then root then right.
  • Pre-order traversal - visit root then left then right.
  • Post-order traversal - visit left then right then root.
  • Node deletion in BST -
    • If root node is null than don't do anything.
    • If key data greater than root data than move to right sub tree.
    • If key data less than root node data than move to left sub tree.
    • If key and node data matced-
    • If root node left pointer has null than pickup the right node of the root.
    • If root node right pointer has null than pickup the left node of the root.
    • If matched node has two child than swap the min value of the right sub tree in the root node.
    • And min value node has been delete.

class TreeNode<T extends Comparable<T>> implements Comparable<TreeNode<T>>{
    TreeNode<T> leftNode;
    TreeNode<T> rightNode;
    T data;

    public TreeNode(T data){
        this.data=data;
    }

    @Override
    public int compareTo(TreeNode<T> o) {
        return data.compareTo(o.data);
    }
}
public class BinaryTree<T extends Comparable<T>> {
    public void addNode(TreeNode rootNode,T data){
        if(rootNode.data.compareTo(data)>0){
            if(rootNode.leftNode==null){
                System.out.println(data+" inserted left at "+rootNode.data);
                rootNode.leftNode=new TreeNode<>(data);
            }
            else
                addNode(rootNode.leftNode,data);
        }else if(rootNode.data.compareTo(data)<0){
            if(rootNode.rightNode==null){
                System.out.println(data+" inserted right at "+rootNode.data);
                rootNode.rightNode=new TreeNode<>(data);
            }
            else
                addNode(rootNode.rightNode,data);
        }
    }

    /**
     * in-order traversal in binary tree
     * @param rootNode
     */
    public void inOrderTraversal(TreeNode rootNode){
        if(rootNode!=null){
            inOrderTraversal(rootNode.leftNode);
            System.out.print(rootNode.data+" ");
            inOrderTraversal(rootNode.rightNode);
        }
    }

    public void preOrderTraversal(TreeNode rootNode){
        if(rootNode!=null){
            System.out.print(rootNode.data+" ");
            preOrderTraversal(rootNode.leftNode);
            preOrderTraversal(rootNode.rightNode);
        }
    }

    public void postOrderTraversal(TreeNode rootNode){
        if(rootNode!=null){
            postOrderTraversal(rootNode.leftNode);
            postOrderTraversal(rootNode.rightNode);
            System.out.print(rootNode.data+" ");
        }
    }

    public TreeNode<T> deleteNode(TreeNode<T> rootNode,T key){
        if(rootNode==null){
            return rootNode;
        }
        /* If key data greater than tree data */
        if(key.compareTo(rootNode.data)>0)
            rootNode.rightNode=deleteNode(rootNode.rightNode,key);
            /* If key data less than tree data */
        else if(key.compareTo(rootNode.data)<0)
            rootNode.leftNode=deleteNode(rootNode.leftNode,key);
        else{ /* If key data equal to tree data */
            if(rootNode.leftNode==null)
                return rootNode.rightNode;
            else if(rootNode.rightNode==null)
                return rootNode.leftNode;
            /* If key data node have two child */
            rootNode.data=getMin(rootNode.rightNode);
            rootNode.rightNode=deleteNode(rootNode.rightNode, rootNode.data);
        }
        return rootNode;
    }

    private T getMin(TreeNode<T> rootNode){
        T data=rootNode.data;
        while (rootNode.leftNode!=null){
            data= rootNode.data;
            rootNode=rootNode.leftNode;
        }
        return data;
    }

    public static void main(String[] args) {
        TreeNode rootNode=new TreeNode<>(12);
        BinaryTree<Integer> binaryTree=new BinaryTree<>();
        binaryTree.addNode(rootNode,10);
        binaryTree.addNode(rootNode,11);
        binaryTree.addNode(rootNode,11);
        binaryTree.addNode(rootNode,13);
        binaryTree.addNode(rootNode,14);
        binaryTree.addNode(rootNode,5);
        binaryTree.addNode(rootNode,4);
        binaryTree.addNode(rootNode,3);
        binaryTree.addNode(rootNode,20);
        binaryTree.inOrderTraversal(rootNode);
        binaryTree.deleteNode(rootNode,20);
        System.out.println();
        binaryTree.inOrderTraversal(rootNode);
        System.out.println();
        binaryTree.preOrderTraversal(rootNode);
        System.out.println();
        binaryTree.postOrderTraversal(rootNode);
    }
}

[DevShivmohan]

Sorting

• Quick sort
  • 
  • Advanced level reference link - Link

    
    package com.algotest.sort;

import java.util.Arrays;

public class QuickSort { private static int[] arr={4,6,2,5,7,9,1,3,8};

public void quickSort(int[] array,int low,int high){
    if(low<high){
        int pivot=partition(array,low,high);
        quickSort(array,low,pivot-1);
        quickSort(array,pivot+1,high);
    }
}

public int partition(int[] array,int low,int high){
    int pivot=array[high];
    int i=low-1;
    for(int j=low;j<=high-1;j++)
        if(array[j]<pivot){
            i++;
            swap(array,i,j);
        }
    swap(array,i+1,high);
    return i+1;
}

public void swap(int[] array,int low,int high){
    int temp=array[low];
    array[low]=array[high];
    array[high]=temp;
}

public static void main(String[] args) {
    System.out.println(Arrays.toString(arr));
    new QuickSort().quickSort(arr,0,arr.length-1);
    System.out.println(Arrays.toString(arr));
}

}

[DevShivmohan]

Graph

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph

Types of graph

• Un-directed graph has bi-directional.
• Directed graph has single directional.
• Weighted Every edges has some value.
• Un-weighted weight of the all edges are same.

Graph representation

• Adjacency of matrix A graph represented by adjacency of matrix.

• using adjacency of matrix

• Adjacency of list A graph represented by list.

• using Adjacency of list

Graph implementation in Java using Adjacency of matrix

/**
     * 
     * @param arr array of the matrix 2D
     * @param source source vertex
     * @param destination destination vertex
     * @param isBiDirectional if is it bidirectional or not
     */
    public static void addEdge(int arr[][], int source,int destination,boolean isBiDirectional){
        arr[source][destination]=1;
        if(isBiDirectional)
            arr[destination][source]=1;
    }

Graph implementation in Java using Adjacency of list

class Graph<T>{
    protected Map<T, List<T>> map=new HashMap<>();

    public void addNewVertex(T s){
        map.put(s, new LinkedList<>());
    }

    public void addNewEdge(T source,T destination,boolean isBidirectional){
        if(!map.containsKey(source))
            addNewVertex(source);
        if(!map.containsKey(destination))
            addNewVertex(destination);
        map.get(source).add(destination);
        if(isBidirectional)
            map.get(destination).add(source);
    }
}

[DevShivmohan]

General sorting algorithm

Sorting algorithm All types of sorting algo

• Bubble sort
  • Check if adjacent element greater than next adjacent then swap with in each iteration .
  • then achieve ascending order sorted array.
  • In first iteration loop we have to consider as a first pass.
  • In second loop has iterate and check if arr[j]>arr[j+1] then we have to swap.
  • Second loop condition has specify that length-i last i ranges indexes has sorted so we do not need to sort again.

    /**
     * Bubble sorting algorithm
     * in each satisfied condition we have to swap
     * last i index rages has already sorted
     * @param arr
     */
    public static void sortByBubbleSort(int arr[]){
        for(int i=0;i<arr.length-1;i++)
            for(int j=0;j<arr.length-i-1;j++)
                if(arr[j]>arr[j+1])
                    swap(arr,j,j+1);
    }

    public static void swap(int []arr,int firstIndex,int secondIndex){
        int temp=arr[firstIndex];
        arr[firstIndex]=arr[secondIndex];
        arr[secondIndex]=temp;
    }

• Selection sort
  • Checking in adjacent elements.
  • find smallest element from the array and then swap with i index after ending second loop.
  • smallest = arr[i];
  • check if smallest > arr[j] then assign smallest = arr[j] and after second loop it will be swap with i index .

/**
     * selection sort
     * after finding the smallest element in the array
     * then swap with initial index, not swapping in each condition
     * @param arr
     */
    public static void sortBySelectionSort(int arr[]){
        for(int i=0;i<arr.length;i++){
            int smallest=i;
            for(int j=i;j<arr.length;j++)
                if(arr[smallest]>arr[j])
                    smallest=j;
            swap(arr,smallest,i);
        }
    }

public static void swap(int []arr,int firstIndex,int secondIndex){
        int temp=arr[firstIndex];
        arr[firstIndex]=arr[secondIndex];
        arr[secondIndex]=temp;
    }

• Insertion sort
  • In insertion sort there are two parts of the array sorted and unsorted part.
  • compare each element from unsorted to the sorted part.
  • If less than then placed at the hist expected location.

/**
     * there are two parts sorted and unsorted part
     * compare each unsorted element with sorted element
     * if
     * @param arr 7 8 3 1 2
     */
    public static void sortByInsertionSort(int arr[]){
        // consider 0th index as sorted part
        for(int i=1;i<arr.length;i++){
            int current=arr[i]; // current element of unsorted part
            int j=i-1; // last element of sorted part
            while(j>=0 && current<arr[j]){
                arr[j+1]=arr[j];
                j--;
            }
            // placed
            arr[j+1]=current;
        }
    }