LowestCommonAncesstor

public class LowestCommonAncesstor {
   
    public static void main(String[] args) {
        int[] arr = {3,6,5,9,2,8};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
       
         Node node = getLCA(root, 5, 8);//output 6
         System.out.println(node.value);
    }
   
    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
            } else {
                root.right = insertNode(root.right, value);
            }
            return root;
        }

    }
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
   
    static Node getLCA(Node currentNode,int A,int B) {
        if(currentNode==null) {
            return null;
        }
        if(currentNode.value==A || currentNode.value==B) {
            return currentNode;
        }
        Node left = getLCA(currentNode.left, A, B);
        Node right = getLCA(currentNode.right, A, B);
        if(null!=left && null!=right) {
            return currentNode;
        }
        if(null==left) {
            return right;
        }else {
            return left;
        }
    }
   
}

Find Noble Integer Program

Question: Given an integer array, find if an integer p exists in the array such that the number of integers greater than p in the array equals to p
If such an integer is found return 1 else return -1.

Solution:
static int checkNobleInteger(int[] arr) {
        for(int i=0;i<arr.length;i++) {
           
            int count = 0;
            for(int j=0;j<arr.length;j++) {
               
                if(arr.length-j+count<arr[i]) {
                    break;
                }
               
                if(arr[j]>arr[i]) {
                    count++;
                }
            }
            if(arr[i]==count) {
                return 1;
            }
        }
        return -1;
    }

input: {4, 3, 5, 6, 7, 8}
output: 1


input: {6, 3, 5, 6, 7, 8}
output: -1

Ref: https://www.interviewbit.com

MergeSort Program

Merge Sort:

public class MergeSort2 {

    public static void main(String args[]) {
        int[] arr = {1,12,3,8,2,1,7,9};
        mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
   
    public static void mergeSort(int[] arr, int start, int end) {
        if(start<end) {                               //check start < mid then find mid and divide arr in parts 
            int mid = (start + end)/2 ;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid+1, end);
            merge(arr, start, mid, end); //merge
        }
    }
   
    public static void merge(int[] arr, int start, int mid, int end) {
        int p = start ;
        int q = mid+1;
       
        int[] localArr = new int[end-start+1];
        int k = 0;
        for(int i=start;i<=end;i++) {
            if(p>mid) {
                localArr[k] = arr[q];
                k++;
                q++;
            }else if(q>end) {
                localArr[k] = arr[p];
                k++;
                p++;
            }else if(arr[p]<arr[q]) {
                localArr[k] = arr[p];
                p++;
                k++;
            }else {
                localArr[k]  =arr[q];
                q++;
                k++;
            }
        }
       
        for(int i=0;i<localArr.length;i++) {
            arr[start]  = localArr[i];
            start++;
        }
       
       
    }
   
}

How merge method work:
take an example below
[1,12 ,3,8 ||||||| ,2,1,7,9] start = 0,mid = 1,end = 3
we want to merge 0 to 3

p = 0
q=  mid+1 = 2;
take localarr of size end-start+1 = 4
k=0
loop---> start to < = end
if p reaches to mid then only right part need to insert localarr
if(p>mid) {
                localArr[k] = arr[q];
                k++;
                q++;
            }
if q reaches to end then only left part need to insert into localarr
else if(q>end) {
                localArr[k] = arr[p];
                k++;
                p++;
            }

if arr[p] <arr[q] it means need to insert p position element to localarr and increemt p

else if(arr[p]<arr[q]) {
                localArr[k] = arr[p];
                p++;
                k++;
            }

if arr[p]>arr[q] it means need to insert q position element to localarr and increment q
 else {
                localArr[k]  =arr[q];
                q++;
                k++;
            }

loop exit

now need to insert localarr to original array
  for(int i=0;i<localArr.length;i++) {
            arr[start]  = localArr[i];
            start++;
        }

QuickSort Program

QuickSort:

[5,9,3,15,13,7,1,8,18,14,4]

Steps:

we will choose first element as pivot
move all less than pivot on one side and other on one side

so we need to find the pivot element position
then partition in 2 parts first is before pivot and other is after pivot

public class QuickSort {
   
    public static void main(String args[]) {
        int arr[] = {10,3,16,8,9,1,15,6,18};
        quick_sort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
   
    static void quick_sort ( int A[ ] ,int start , int end ) {
           if( start < end ) {
                //stores the position of pivot element
                 int piv_pos = partition (A,start , end ) ;    
                 quick_sort (A,start , piv_pos -1);    //sorts the left side of pivot.
                 quick_sort ( A,piv_pos +1 , end) ; //sorts the right side of pivot.
           }
        }
   
    static int partition ( int A[],int start ,int end) {
        int i = start + 1;
        int piv = A[start] ;            //make the first element as pivot element.
        for(int j =start + 1; j <= end ; j++ )  {
        /*rearrange the array by putting elements which are less than pivot
           on one side and which are greater that on other. */

              if ( A[ j ] < piv) {
                     swap (A ,i , j );
                i += 1;
            }
       }
       swap ( A,start ,i-1  ) ;  //put the pivot element in its proper place.
       return i-1;                      //return the position of the pivot
    }
   
    public static void swap(int[] A,int first, int second) {
        int temp = A[first];
        A[first] = A[second];
        A[second] = temp;
    }
   
}


How partition work in above:
start = 0 , end = 10
[5,9,3,15,13,7,1,8,18,14,4]
piv = A[start] = 5
i = start+1 = 1;
loop--> j=start+1 to <=end and j++

first round of loop:  a[j]>piv so nothing change
                                  i= 1, j=2
second round of loop: a[j]<piv so swap i with j and increase i by1
  [5,3,9,15,13,7,1,8,18,14,4]
       i = 2, j=3
third round of loop:  a[j]>piv so nothing change
i=2,j=4 
fourth round of loop:  a[j]>piv so nothing change
i=2,j=5
fifth round of loop:  a[j]>piv so nothing change
i=2,j=6
seventh round of loop: a[j]<piv so swap i with j and increase i by1
  [5,3,1,15,13,7,9,8,18,14,4]
       i = 3, j=7
next few round no change till i=3, j=9
in last round i=3,j=10
a[j]<piv so swap i with j and increase i by1
  [5,3,1,4,13,7,9,8,18,14,15]
       i = 4


now loop break move pivot element to actual position
swap i-1 with start(pivot)

now pivot moved to actual postion

then we will sort the leftside of pivot and right side

Implement Least Recently Used (LRU) cache

 If item is present in cache, it is moved to front of the list and location is returned.

 If it is not present , a new page mapping is done. If cache is not full, a new entry is added to front otherwise least recently used entry is removed and then a new entry to front is added.

import java.util.HashMap;
import java.util.Map;

public class LRUCacheSample1 {
    DoubleLinkList start = null;
    DoubleLinkList end = null;
    int capacity = 5;
    int count = 0;
    Map<Integer, DoubleLinkList> map = new HashMap<>();
    class DoubleLinkList{
        DoubleLinkList next;
        DoubleLinkList prev;
        int key;
        int val;
      
        public DoubleLinkList(int key,int val) {
            this.key = key;
            this.val = val;
        }
    }
  
    void get(int key) {
        if(map.containsKey(key)) {
            DoubleLinkList existNode = map.get(key);
            moveNodeToFront(existNode);
        }
    }
  
    void add(int key,int val) {
        if(map.containsKey(key)) {
            DoubleLinkList existNode = map.get(key);
            existNode.val = val;
            moveNodeToFront(existNode);
        }else {
            DoubleLinkList node = new DoubleLinkList(key, val);
            if(count<capacity) {
                count = count+1;
                addNodeAtFront(node);
            }else {
                DoubleLinkList lastNode = map.remove(end.key);
                removeNode(lastNode);
                addNodeAtFront(node);
            }
      
        }
    }
  
    void removeNode(DoubleLinkList node) {
         end = end.prev;
         if(null!=end) {
             end.next = null;
         }
        node = null;
    }
  
    void addNodeAtFront(DoubleLinkList node) {
        node.next = start;
        if(null!=start) {
            start.prev = node;
        }
            start = node;
         if(end==null) {
             end = node;
         }
         map.put(node.key, node);
        
    }
  
    void moveNodeToFront(DoubleLinkList node) {
        DoubleLinkList pr = node.prev;
        DoubleLinkList nex = node.next;
        if(null!=pr) {
            pr.next = nex;
        }else {
            start = node;
        }
        if(null!=nex) {
            nex.prev = pr;
        }else {
            end = pr;
        }
      
         addNodeAtFront(node);
    }
  
    void print() {
        DoubleLinkList node = start;
        while(null!=node) {
            System.out.println("key is"+node.key+"val is"+node.val);
            node = node.next;
        }
    }
  
  
    public static void main(String args[]) {
        LRUCacheSample1 obj = new LRUCacheSample1();
        obj.add(5, 10);
        obj.add(2, 4);
        obj.add(3, 6);
        obj.add(6, 12);
        obj.add(8, 16);
        
        obj.print();
        obj.get(3);
        System.out.println("*****************");
        System.out.println("after get 3");
        obj.print();
      
        obj.add(9, 18);
        System.out.println("*****************");
        System.out.println("after add 9");
        obj.print();
      
        obj.add(2, 13);
        System.out.println("*****************");
        System.out.println("after update 2");
        obj.print();
      
      
    }
  
}
output::
key is8val is16
key is6val is12
key is3val is6
key is2val is4
key is5val is10
*****************
after get 3
key is3val is6
key is8val is16
key is6val is12
key is2val is4
key is5val is10
*****************
after add 9
key is9val is18
key is3val is6
key is8val is16
key is6val is12
key is2val is4
*****************
after update 2
key is2val is13
key is9val is18
key is3val is6
key is8val is16
key is6val is12

Ref: http://androidsrc.net/lru-cache-java-implementation/