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


}

       
 

Merging two sorted arrays using Java ....

here is the code .....

       
public class MergingSortedLists {

 public static void main(String args[]) {

  int[] arr1 = {
   1,
   4,
   5,
   43,
   56,
   59
  };
  int[] arr2 = {
   2,
   3,
   6,
   34,
   36,
   42,
   67
  };
  int[] sortedList = new int[arr1.length + arr2.length];
  mergeLists(arr1, arr2, sortedList);
 }

 public static void mergeLists(int[] arr1, int[] arr2, int[] sortedList) {
  int k = 0;
  int j = 0;
  int t = 0;
  while (k < arr1.length && j < arr2.length) {
   if (arr1[k] <= arr2[j]) {
    sortedList[t] = arr1[k];
    t++;
    k++;
   } else {
    sortedList[t] = arr2[j];
    t++;
    j++;
   }
  }
  if (k != arr1.length) { //case where arr1 is left with elements not added to sorted list
   while (k < arr1.length) {
    sortedList[t] = arr1[k];
    t++;
    k++;
   }
  }
  if (j != arr2.length) { //case where arr2 is left with elements not added to sorted list
   while (j < arr2.length) {
    sortedList[t] = arr2[j];
    t++;
    j++;
   }
  }
  for (int s: sortedList) {
   System.out.print(s);
   System.out.print(" ");

  }
 }
}