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;
 }
}

       
 

Remove duplicates from a string without using any additional data structure using Java....

here is the code .....

       

public class Demo {

 public static void main(String[] args) {
  String name = "GAURAV KUMAR YADAV1111";
  dupliactesRemoved(name);
 }

 //This method assumes that string is made up of only small letter characters i. "a....z"
 public static void dupliactesRemoved(String temp) {

  int vector = 0;
  int val;
  System.out.println("Given string after removing duplicates characters is below :");
  for (int i = 0; i < temp.length(); i++) {
   val = temp.charAt(i) - 'a';
   if ((vector & (1 << val)) == 0) {
    System.out.print(temp.charAt(i));
    vector = vector | (1 << val);
   }
  }
 }
}

       
 

Determine if a string has all unique characters without using any additional data structure using Java....

Here is the the code ....

       
public class Demo {

 public static void main(String[] args) {

  String name = "gaurv1";
  if (isUniqueCharString(name))
   System.out.print("String is made up of unique chars");
  else
   System.out.print("String is not made up of unique chars");

 }

 //here we are using an integer as a bit vector....
 public static boolean isUniqueCharString(String temp) {
  int vector = 0;
  int val;
  for (int i = 0; i < temp.length(); i++) {
   val = temp.charAt(i) - 'a';
   if ((vector & (1 << val)) > 0)
    return false;
   vector = vector | (1 << val);
  }
  return true;
 }

 // Alternate solution - we can sort the characters of string and then
 // compare the neighbors
}

       
 

Find k closest elements in a sorted array using Java ......

here is the code .....


/*Given a sorted array arr[] and a value X, find the k closest elements to X in arr[].
 Examples:

 Input: K = 4, X = 35
 arr[] = {12, 16, 22, 30, 35, 39, 42,
 45, 48, 50, 53, 55, 56}
 Output: 30 39 42 45
 Note that if the element is present in array, then it should not be in output, only the other closest elements are required.
 */

       

public class FindKClosestElements {

 public static void main(String args[]) {

  int[] arr = {
   12,
   16,
   22,
   30,
   35,
   39,
   42,
   45,
   48,
   50,
   53,
   55,
   56
  };
  int element = 100;
  int k = 5;
  int m;
  int n;
  int distance1;
  int distance2;

  // case if element is is larger than even the last element in the array
  if (arr[arr.length - 1] < element) {
   n = arr.length - 1;
   while (k != 0) {
    System.out.print(arr[n]);
    System.out.print(" ");
    k--;
    n--;
   }
   return;
  }

  for (int i = 0; i < arr.length; i++) {
   if (arr[i] >= element) {
    m = i - 1;
    if (arr[i] == element)
     n = i + 1;
    else
     n = i;
    while (m >= 0 && n < arr.length && k != 0) {

     distance1 = arr[n] - element;
     distance2 = element - arr[m];

     if (distance1 <= distance2) {
      System.out.print(arr[n]);
      System.out.print(" ");
      k--;
      n++;
     } else {
      System.out.print(arr[m]);
      System.out.print(" ");
      k--;
      m--;
     }
    }
    if (k != 0) {
     if (m > 0)
      while (k != 0) {
       System.out.print(arr[m]);
       System.out.print(" ");
       m--;
       k--;
      } else
      while (k != 0) {
       System.out.print(arr[n]);
       System.out.print(" ");
       k--;
       n++;
      }
    }
    if (k == 0)
     return;
    else
     continue;
   }
  }
 }


}