Counting Sort using Java...

Here is the code .....

       
public class CountingSort {

 public static void main(String[] args) {

  // Array of items on which search will
  // be conducted.
  int arr[] = new int[] { 10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47 };
  int maxElemnt = findMaxElement(arr);
  arr = countSort(arr, maxElemnt);

  System.out.println("Below is the sorted array:");
  for (int s : arr)
   System.out.print(s + " ");
 }

 // Finding Max Element
 public static int findMaxElement(int[] arr) {

  int i = 0;
  int temp;
  while (i < arr.length - 1) {
   if (arr[i] > arr[i + 1]) {
    temp = arr[i + 1];
    arr[i + 1] = arr[i];
    arr[i] = temp;
   }
   i++;
  }

  return arr[arr.length - 1];
 }

 public static int[] countSort(int[] arr, int range) {

  int[] countArray = new int[range + 1];
  int[] outputArray = new int[arr.length];

  int i = 0;
  while (i < arr.length) {
   countArray[arr[i]] = ++countArray[arr[i]];
   i++;
  }
  i = 1;
  while (i < countArray.length) {
   countArray[i] = countArray[i] + countArray[i - 1];
   i++;
  }

  i = 0;
  while (i < outputArray.length) {
   outputArray[countArray[arr[i]] - 1] = arr[i];
   countArray[arr[i]] = --countArray[arr[i]];
   i++;
  }

  return outputArray;
 }
}

Exponential Search using Java....

Here is the code ....

public class ExponentialSearch {

 public static void main(String[] args) {

  // Array of items on which search will
  // be conducted.
  int arr[] = new int[] { 10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47 };
  int valueToSearch = 24;
  int i = 1;

  if (arr[0] == valueToSearch) {
   System.out.println("ELement found at location");
   return;
  }

  while (i < arr.length && arr[i] <= valueToSearch) {
   i = i * 2;

   int loc = binarySearrch(arr, valueToSearch, i / 2, min(i, arr.length - 1));
   if (loc != -1) {
    System.out.println("Element found at location : " + loc);
    break;
   }
  }
 }

 public static int binarySearrch(int[] arr, int valueToSearch, int startIndex, int lastIndex) {

  if (lastIndex == startIndex) {
   if (arr[lastIndex] == valueToSearch)
    return lastIndex;
   else
    return -1;
  } else {

   int mid = (startIndex + lastIndex) / 2;
   if (arr[mid] == valueToSearch)
    return mid;
   else if (arr[mid] > valueToSearch)
    return binarySearrch(arr, valueToSearch, startIndex, mid - 1);
   else
    return binarySearrch(arr, valueToSearch, mid + 1, lastIndex);
  }
 }

 public static int min(int i, int j) {
  if (i < j)
   return i;
  else
   return j;
 }
}


       
 

Interpolation Search using Java...

Here is the code ....

public class InterpolationSearch {

 public static void main(String[] args) {

  // Array of items on which search will
  // be conducted.
  int arr[] = new int[] { 10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47 };
  int valueToSearch = 33;
  int loc = searchElement(arr, valueToSearch, 0, arr.length - 1);

  if (loc != -1)
   System.out.print("Element appears at location : " + loc);
  else
   System.out.print("ELement not found");
 }

 // Recursive search : Interpolation search
 public static int searchElement(int[] arr, int valueTosearch, int low, int high) {

  if (high == low) {
   if (arr[high] == valueTosearch)
    return high;
   else
    return -1;
  } else {

   int pos = low + ((valueTosearch - arr[low]) * (high - low)) / (arr[high] - arr[low]);
   if (arr[pos] == valueTosearch)
    return pos;
   else if (arr[pos] > valueTosearch)
    return searchElement(arr, valueTosearch, low, pos - 1);
   else
    return searchElement(arr, valueTosearch, pos + 1, high);
  }
 }
}


       
 

Jump Search using Java....

Jump Search - Jump Search is a searching algorithm for sorted arrays. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements.

Input - A sorted array.

Here is the code .....

       
public class JumpSearch {

 public static void main(String[] args) {

  int[] arr = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 };
  int lastJumpedIndex = 0;

  // Evaluate optimal block size
  int t = (int) Math.floor(Math.sqrt(arr.length));
  int valueToSearch = 21;

  while (t < arr.length) {

   if (arr[t] > valueToSearch) {

    if (valueToSearch >= arr[lastJumpedIndex]) {

     // Doing a linear search for x in block
     int i = lastJumpedIndex;
     while (i < t) {
      if (arr[i] == valueToSearch) {
       System.out.print("Element found at index : " + i);
       return;
      }
      i++;
     }
    }
   }
   lastJumpedIndex = t;
   t = 2 * t;
  }

  // In case few of the elements in the last iteration of above loop have
  // left if array is not of an even length
  if (t > arr.length - 1) {
   int k = lastJumpedIndex;
   while (k <= arr.length - 1) {
    if (arr[k] == valueToSearch) {
     System.out.print("Element found at index : " + k);
     return;
    }
    k++;
   }
  }
  System.out.print("Element was not found");
 }

 public static int min(int i, int j) {
  if (i < j)
   return i;
  else
   return j;
 }
}


       
 

Find start of the loop in the linked list using Java...

Problem Statement:- Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
DEFINITION:-
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.

EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C

here is the code ...

       
public class Q5 {

 public static void main(String[] args) {

  Node head = new Node(1);    // head node of the linked list
  Node node1 = new Node(2);
  head.next = node1;
  Node node2 = new Node(3);
  node1.next = node2;
  Node node3 = new Node(4);
  node2.next = node3;
  Node node4 = new Node(5);
  node3.next = node4;
  Node node5 = new Node(6);
  node4.next = node5;
  Node node6 = new Node(7);
  node5.next = node6;
  node6.next = node3;        // here loop appears
  findNodeAtbeg(head);
 }

 public static void findNodeAtbeg(Node head) {
  Node slow = head;          //slow pointer
  Node fast = head;          //fast pointer

  while (fast != null) {
   slow = slow.next;
   fast = fast.next.next;
   if (slow == fast) {
    break;
   }
  }
  if (fast == null) {
   System.out.print("There is no loop exit");
  }
  slow = head;
  while (slow != fast) {
   slow = slow.next;
   fast = fast.next;
  }
  System.out.println("Node where loop begins contains data item as - "
    + fast.data);
 }
}

class Node {
 int data;
 Node next;

 Node(int d) {
  data = d;
  next = null;
 }
}

       
 

Producer Consumer multithreading problem using Java....

Here is the code .....

       

public class ProducerConsumerProblem {

 public static void main(String[] args) {
        
  DataClass c=new DataClass();
  Producer p1 = new Producer(c, 1);
  Consumer c1 = new Consumer(c, 1);
  p1.start();
  c1.start();

 }
}

class DataClass {
 int data;
 boolean dataAvailable = false;

 public synchronized int get() throws InterruptedException {

  while (dataAvailable == false) {
   wait();
  }
  dataAvailable = false;
  notifyAll();
  return data;
 }

 public synchronized void setData(int content) throws InterruptedException {

  while (dataAvailable == true) {
   wait();
  }
  data = content;
  dataAvailable = true;
  notifyAll();
 }
}

class Producer extends Thread {
 private DataClass dataObject;
 private int number;

 public Producer(DataClass dataClassReference, int num) {
  dataObject = dataClassReference;
  number = num;
 }

 public void run() {
  for (int i = 0; i < 10; i++) {
   try {
    dataObject.setData(i);
   } catch (InterruptedException e1) {
    // TODO Auto-generated catch block
    e1.printStackTrace();
   }
   System.out.println("Producer #" + this.number + " put: " + i);
   try {
    sleep((int) (Math.random() * 100));
   } catch (InterruptedException e) {
   }
  }
 }
}

class Consumer extends Thread {
 private DataClass dataObject;
 private int number;

 public Consumer(DataClass dataClassReference, int num) {
  dataObject = dataClassReference;
  number = num;
 }

 public void run() {
  int value = 0;
  for (int i = 0; i < 10; i++) {
   try {
    value = dataObject.get();
   } catch (InterruptedException e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   }
   System.out.println("Consumer #" + this.number + " got: " + value);
  }
 }
}

       
 

Check whether a string is a rotation of another string using Java .....

here is the code....

Problem - "ravgau" is a rotation of "gaurav".

       

public class Demo {

 public static void main(String[] args) {

  String s1 = "gaurav";
  String s2 = "avgaur";

  if (isSubString(s1 + s1, s2))
   System.out.print("String :" + s2 + " is a rotation of string :" + s1);
  else
   System.out.print("String :" + s2 + " is not a rotation of string :" + s1);

 }

 public static boolean isSubString(String s1, String s2) {
  int k = 0;
  int i = 0;
  int t;
  if (s1.length() < s2.length()) {
   return false;
  } else {
   while (i < (s1.length() - s2.length() + 1)) {
    if (s1.charAt(i) == s2.charAt(k)) {
     t = i;
     t++;
     k++;
     // Always make sure that conditions in loop should appear in
     // correct order otherwise it could give an exception
     while ((k < s2.length()) && (s1.charAt(t) == s2.charAt(k))) {
      t++;
      k++;
     }
     if (k == s2.length())
      return true;
     else
      k = 0;
    }
    i++;
   }
  }
  return false;
 }
}