Sorting duplicate elements in single array

 
There are lot of sorting algorithms like bubble sort, quick sort, insertion sort, rad-ix sort etc., But all these sorting algorithm gives array of elements in an ascending or descending order. 
In point of interview if they ask to sort the array with all the duplicate elements should be placed at end of the array again with sorted sub arrays.
Sorting duplicate elements in single array


For example 

Input array : { 5, 6, 2, 4, 8, 3, 5, 1, 3, 4, 5, 2, 1, 5, 3 }

Output array : {1, 2, 3, 4, 5, 6, 8,    1, 2, 3, 4, 5,    3, 5,   5 }

If we see above output, input array has been sorted with sub arrays with all duplicate elements at last. So lets see simple java code with the help of Collection API to sort the given array as per above problem


import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class DuplicateArraySort {

 public static void main(String[] args) {

  int array[] = { 5, 6, 2, 4, 8, 3, 5, 1, 3, 4, 5, 2, 1, 5, 3 };

  System.out.print("Before array sorting : ");
  printArray(array);

  Map<Integer, Integer> myMap = generateMap(array);
  Set<Integer> set = (Set<Integer>) myMap.keySet();

  for (int i = 0; i < array.length;) {

   Iterator<Integer> itr = set.iterator();

   while (itr.hasNext()) {
    int key = itr.next();
    if ((myMap.get(key)) > 0) {
     myMap.put(key, (myMap.get(key) - 1));
     array[i] = key;
     i++;
    }
   }
  }

  System.out.print("\nAfter array sorting : ");
  printArray(array);
 }

 public static Map<Integer, Integer> generateMap(int[] array) {

  Map<Integer, Integer> myMap = new TreeMap<Integer, Integer>();
  for (int i : array) {
   if (myMap.containsKey(i)) {
    myMap.put(i, myMap.get(i) + 1);
   } else {
    myMap.put(i, 1);
   }
  }
  return myMap;
 }

 public static void printArray(int[] array) {
  for (int i : array) {
   System.out.printf("%d, ", i);
  }
 }
}


OUTPUT:


Before array sorting : 5, 6, 2, 4, 8, 3, 5, 1, 3, 4, 5, 2, 1, 5, 3, 
After array sorting : 1, 2, 3, 4, 5, 6, 8, 1, 2, 3, 4, 5, 3, 5, 5, 





Calculate String Length

 
This is one of the simple interview question that need to calculate String length without using length() function. There are lot of ways to find the find the length like converting String to Character array and by iterating it. Lets see simple java code to calculate string length.
Calculate String length




public class StringSize {

 public static void main(String[] args) {
  
                String str = "Java Discover";
  
                int length = getStringLength(str);
  
                System.out.printf("String - %s \nLength - %d ",str,length);
 }
 
 public static int getStringLength(String str){
  
                int length = 0;
  
                char[] array = str.toCharArray();
  for (char c : array) {
   length++;
  }
  
                return length;
 }
}


OUTPUT:


String - Java Discover 
Length - 13



Anagrams

Anagram is a type of word or phrase generating by rearranging the letters of a given word or phrase to produce a new word or phrase. Need to use all the original letters exactly once to frame new word or phrase. Some of the famous Anagram words are given below,
Anagrams


Mother in lawWoman Hitler
Debit cardBad credit
Eleven plus twoTwelve plus one
Payment receivedEvery cent paid me
AstronomerMoon starer
DormitoryDirty room
PunishmentNine Thumps
DesperationA rope ends it
Snooze alarmsAlas! No more Zs

and lot more are there...


Lets implement anagrams in java for only words to generate. 

public class Anagram {

 private HashSet<String> words = new HashSet<String>();
 
 public static void main(String[] args) throws Exception {
  
  String myWord = "art";

  Anagram obj = new Anagram();
  
  obj.getAnagramWords("", myWord);
  
  obj.printAnagramWords();
  
 }

 public void getAnagramWords(String prefix, String word) {
  if (word.length() <= 1) {
   words.add(prefix+word);
  } else {
   for (int i = 0; i < word.length(); i++) {
    String middle = word.substring(i, i + 1);
    String before = word.substring(0, i);
    String after = word.substring(i + 1);
    getAnagramWords(prefix + middle, before + after);
   }
  }  
 }
 
 public void printAnagramWords(){
  System.out.println("LIST OF ANAGRAM WORDS :::");
  for (String string : words) {
   System.out.println(string);   
  }
 }
}

OUTPUT:


LIST OF ANAGRAM WORDS :::
rta
atr
tra
art
tar
rat

Quicksort in Java

In our earlier tutorials we have seen about Bubble sort and Insertion sort. In this tutorial we will see about one of the best divide and conquer algorithm called Quicksort. In divide and conquer sorting algorithm the original elements will be separated into two parts (divided) and then individually sorted (conquered) and then combined. Need to remember that Quciksort can be implemented in same array and no need of additional array required.
quicksort example in java


  • If array contains only one element or zero element then the array is in sorted order already. 
  • If array contains more than 1 element then we need to select middle element as pivot element.
  • Next we need to place all smaller elements than pivot element on left side and all larger elements are placed at right side of the array. 
  • Sort both the arrays recursively by applying Quicksort algorithm.
  • Finally combine both the sorted arrays. 


Now lets see simple java code to sort integer array using Quicksort algorithm.


public class QuickSort {

 public static void main(String[] args) {
  
  int array[] = { 6, 3, 9, 2, 5, 7, 8, 1, 4 };
  
  System.out.print("Array before sorting : ");
  printArray(array);
  
  quickSort(array, 0, array.length - 1);
  
  System.out.print("Array after sorting : ");
  printArray(array);
 }

 public static void quickSort(int array[], int lower, int length) {

  if (lower >= length)
   return;
  int first = lower, last = length;
  int piv = array[(first + last) / 2]; // Picking pivot element

  while (first < last) {
   // Searching for smaller element than pivot element
   while (first < last && array[first] < piv)
    first++;

   // Searching for greater element than pivot element
   while (first < last && array[last] > piv)
    last--;
   if (first < last) {
    int tmp = array[first];
    array[first] = array[last];
    array[last] = tmp;
   }
  }
  if (last < first) {
   int tmp = first;
   first = last;
   last = tmp;
  }
  // Calling recursive
  quickSort(array, lower, first);
  quickSort(array, first == lower ? first + 1 : first, length);
 }

 public static void printArray(int[] array) {
  for (int i : array) {
   System.out.print(i + ", ");
  }
  System.out.println();
 }
}


OUTPUT:


Array before sorting : 6, 3, 9, 2, 5, 7, 8, 1, 4, 
Array after sorting : 1, 2, 3, 4, 5, 6, 7, 8, 9, 



Generics in Java


Generics are introduced in JDK 1.5 on-wards and one of the important and flexible feature in Java by enabling types (classes and interfaces) to be parameters when defining classes, interfaces and methods. Its same as like other formal parameters by providing way of reusing code for different input types. Only the difference in inputs to formal parameters are values where as for inputs to type parameters are types.  
Generics in java

For developers to pass type or method to operate on objects of various types. Also it provides compile time type safety by making fully statically typed language. There are lot of advantage on Generics compared to non-Generic codes like,

  • Use of Multiple Bounds
  • Stronger type checks at compile time.
  • Elimination of casts.
  • Use of wildcards with extends or super to increase API flexibility
  • Enabling programmers to implement generic algorithms.

Now lets see few examples on using Generics in Java.


public class GenericsTest {

 public static void main(String[] args) {
  
  // Without Genric
  List list = new ArrayList();
  list.add("Hello Java Discover");
  // Here we need casting while we use non-generic code
  String val = (String) list.get(0);
  
  
  // With Genric
  List<String> list1 = new ArrayList<String>();
  list1.add("Hello Java Discover");
  // No need of casting while we use Generic
  String val1 = list1.get(0);  
 }
}


If we see in above we declared 2 List object without Generic type and 2nd with "String" type setting. When we get values from 1st List specifically we need to cast those values to corresponding type. But while we get values from 2nd list no need to casting to "String" as like 1st List. 


Next we write single method which will take multiple type inputs like integer, float, String etc.,


public class GenericsTest {

 public static void main(String args[]) {
  
  Integer[] iArray = new Integer[] { 10, 30, 50, 20, 60, 70 };
  System.out.print("Integer Array : ");
  genericMethod(iArray);
  
  Float[] fArray = new Float[]{ 4.41f, 5.23f, 2.23f, 99.41f };
  System.out.print("Float Array   : ");
  genericMethod(fArray);
  
  String[] sArray = new String[]{ "Hello", "Java", "Discover", "2013"};
  System.out.print("String Array  : ");
  genericMethod(sArray);  
 }

 public static <E> void genericMethod(E[] array) {
  for (E element : array) {
   System.out.print(element+", ");
  }
  System.out.println();
 }
}

OUTPUT:


Integer Array : 10, 30, 50, 20, 60, 70, 
Float Array   : 4.41, 5.23, 2.23, 99.41, 
String Array  : Hello, Java, Discover, 2013, 

In above program we have used genericMethod() function to print all 3 different types like integer, float and string. 

Next we will see about creating Generic class using Types.


public class MyGenericClass<T> {

 private T t;

 public MyGenericClass(T t) {
  this.t = t;
 }

 public T getValue() {
  return t;
 }
}


public class GenericsTest {

 public static void main(String args[]) {

  MyGenericClass<Integer> iValue = new MyGenericClass<Integer>(100);
  MyGenericClass<String> sValue = new MyGenericClass<String>("Hello Java Discover");
  MyGenericClass<Double> dValue = new MyGenericClass<Double>(434.23);

  System.out.println("Integer Value : " + iValue.getValue());
  System.out.println("String Value  : " + sValue.getValue());
  System.out.println("Double Value  : " + dValue.getValue());
 }
}

OUTPUT:


Integer Value : 100
String Value  : Hello Java Discover
Double Value  : 434.23

In above example we have created Generic class called "MyGenericClass" which will take different type constructor parameters. 


Iterator Design Pattern in Java

Iterator Design Pattern in Java

Iterator pattern is a behavioral object design pattern. Iterator pattern allows for the traversal through the elements in a grouping of objects via a standardized interface defines the actions or methods that can be performed. These actions or methods able to traverse the objects, remove or add Object according to project needs. So keeping in mind about the pattern just we need to apply on top of our business logic's. 

If we look at Java widely used Iterator interface which used to iterate through elements in various Java collections. We can write our own iterator by implementing java.util.Iterator. This interface features the hasNext(), next(), and remove() methods. Lets take simple example of book stall which contains list of books with these few following information's like,

Book Name
Author
Price

Based on above example lets create Book class which holds the book details


public class Book {

 private String name;
 private String author;
 private int price;
 
 public Book(String name, String author, int price) {
  this.name = name;
  this.author = author;
  this.price = price;
 }
 public String getName() {
  return name;
 }
 public String getAuthor() {
  return author;
 }
 public int getPrice() {
  return price;
 }

 @Override
 public String toString() {
  return "----------\n\nBook Name : "+name+" \nAuthor    : "+author+"\nPrice     : Rs."+price; 
 } 
}




Next lets create Store class which contains list of various books and list actions like add books, removing, listing etc., can be performed. 


import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Store {
 
 List<Book> bookList = new ArrayList<Book>();
 
 public void addBook(Book item) {
  bookList.add(item);
 }

 public Iterator<Book> iterator() {
  return new BooksIterator();
 }

 class BooksIterator implements Iterator<Book> {
  int bookId = 0;

  @Override
  public boolean hasNext() {
   if (bookId >= bookList.size()) {
    return false;
   } else {
    return true;
   }
  }

  @Override
  public Book next() {
   return bookList.get(bookId++);
  }

  @Override
  public void remove() {
   bookList.remove(--bookId);
  }
 } 
}


Next lets implement the main class which feeds list of books into Store and iterates. For sample lets add 4 books and will test.


import java.util.Iterator;

public class BookStore {
 
 public static void main(String[] args) {
  Book b1 = new Book("Lightning", "Dean Koontz", 500);
  Book b2 = new Book("Roma: The Novel of Ancient Rome", "Steven Saylor", 452);
  Book b3 = new Book("Humility", "Andrew Murray", 334);
  Book b4 = new Book("Meditations", "Marcus Aurelius, Martin Hammond", 635);
  
  Store store = new Store();
  store.addBook(b1);
  store.addBook(b2);
  store.addBook(b3);
  store.addBook(b4);
  
  System.out.println("Display list of books in store");
  Iterator<Book> iterator = store.iterator();
  while (iterator.hasNext()) {
   Book item = iterator.next();
   System.out.println(item.toString());
   
   //Removing "Humility" from the book store list
   if(item.getName().equals("Humility")){
    iterator.remove();
   }
  }
  
  System.out.println("\n\n\nDisplay list of books in store after removing 'Humility' book");
  iterator = store.iterator();
  while (iterator.hasNext()) {
   Book item = iterator.next();
   System.out.println(item.toString());
  }
 }
}


OUTPUT:


Display list of books in store
----------

Book Name : Lightning 
Author    : Dean Koontz
Price     : Rs.500
----------

Book Name : Roma: The Novel of Ancient Rome 
Author    : Steven Saylor
Price     : Rs.452
----------

Book Name : Humility 
Author    : Andrew Murray
Price     : Rs.334
----------

Book Name : Meditations 
Author    : Marcus Aurelius, Martin Hammond
Price     : Rs.635



Display list of books in store after removing 'Humility' book
----------

Book Name : Lightning 
Author    : Dean Koontz
Price     : Rs.500
----------

Book Name : Roma: The Novel of Ancient Rome 
Author    : Steven Saylor
Price     : Rs.452
----------

Book Name : Meditations 
Author    : Marcus Aurelius, Martin Hammond
Price     : Rs.635

Java Scanner class

Scanner class in Java

Scanner class does same work as like String Tokenizer and Split() used to parse a string, pulling out data of different types. But its limit in usage and can't get array of strings delimited by a particular expression like in Split(). 

If we see about Scanner and BufferedReader classes used to read stream contents, Scanner class mainly used to parsing tokens from the contents of the stream. But BufferedReader just reads the stream and does not do any special parsing like Scanner. For parsing we can pass those BufferedReader objects to a scanner as the source of characters or string to parse. 

The other difference is BufferedReader is synchronized and Scanner is non-synchronized. Also from JDK 6 we have got 1 KB of character buffer for Scanner and 8 KB of character buffer for BufferedReader . 

Use Scanner if need to parse the file or use BufferedReader just to read the file. 

Next we will see simple example of parsing CSV file using Scanner class.

training.csv


1,Java Basics,4 weeks,INR 3000,
2,Oracle,5 weeks,INR 4500,
3,ASP.NET,6 weeks,INR 5000,
4,EJP,3 weeks,INR 4000,
5,Hibernate,4 weeks,INR 2000,
6,Spring,8 weeks,INR 6000,


TrainingBean.java


public class TrainingBean {

 private int id;
 private String course;
 private String duration;
 private String fees;
 
 public int getId() {
  return id;
 }
 public void setId(int id) {
  this.id = id;
 }
 public String getCourse() {
  return course;
 }
 public void setCourse(String course) {
  this.course = course;
 }
 public String getDuration() {
  return duration;
 }
 public void setDuration(String duration) {
  this.duration = duration;
 }
 public String getFees() {
  return fees;
 }
 public void setFees(String fees) {
  this.fees = fees;
 }
 
 @Override
 public String toString() {
  return "ID:"+id+"\t Course:"+course+"\t Duration:"+duration+"\t Fees:"+fees;
 }
}


ScannerTest.java


public class ScannerTest {

 public static void main(String[] args) throws FileNotFoundException {

  ArrayList<TrainingBean> trainingList = parseTrainingDetails("D://training.csv");

  displayTrainingDetails(trainingList);
 }

 public static ArrayList<TrainingBean> parseTrainingDetails(String file) {
  ArrayList<TrainingBean> list = new ArrayList<TrainingBean>();
  try {
   Scanner scan = new Scanner(new File(file));
   scan.useDelimiter(",");
   int i = 1;
   TrainingBean bean = new TrainingBean();
   while (scan.hasNext()) {
    String value = scan.next().trim();
    if (value.length() == 0)
     break;
    if (i == 1) {
     bean.setId(Integer.parseInt(value));
    } else if (i == 2) {
     bean.setCourse(value);
    } else if (i == 3) {
     bean.setDuration(value);
    } else if (i == 4) {
     bean.setFees(value);
     i = 0;
     list.add(bean);
     bean = new TrainingBean();
    }
    i++;
   }
  } catch (FileNotFoundException e) {
   e.printStackTrace();
  }
  return list;
 }

 public static void displayTrainingDetails(ArrayList<TrainingBean> list) {
  for (TrainingBean trainingBean : list) {
   System.out.println(trainingBean.toString());
  }
 }
}



OUTPUT:


ID:1  Course:Java Basics Duration:4 weeks  Fees:INR 3000
ID:2  Course:Oracle  Duration:5 weeks  Fees:INR 4500
ID:3  Course:ASP.NET  Duration:6 weeks  Fees:INR 5000
ID:4  Course:EJP  Duration:3 weeks  Fees:INR 4000
ID:5  Course:Hibernate Duration:4 weeks  Fees:INR 2000
ID:6  Course:Spring  Duration:8 weeks  Fees:INR 6000