Finding Shortest Prefixes for Strings in an Array [Java]

Question:

 Use the shortest unique prefix to represent each word in the array

 input:    ["zebra", "dog", "duck", "dot"]
 output: {zebra: z, dog: do, duck: du, dot: d}

 input:   [zebra, dog, duck, dove]
 output: {zebra: z, dog: do, duck: du, dove: d}

 input:   [bearcat, bear]
 output: {bearcat: be, bear: b}

Do check your program's output for this input:

input: [bbbb, bbb, bb, b]

and this one

input: [b, bb, bbb, bbbb]

Algorithm I came up with:

[We are using two arrays, the one given and the one we'll be using for the prefixes]

1. Make another array for prefixes. Store first characters of original strings in this array.
2. For all the prefixes to the left of it (in the prefix array), check whether this prefix has been used somewhere.
3. If it has been used, check whether you can add on character to the previous duplicate prefix, if not, add one character to the one that is being checked for duplicates.
4. Follow the same procedure for this new updated prefix (whether it was at some previous location in the array or the current one that was being checked, which is now updated)[Recursion]

Source:

import java.util.Arrays; 

public class UniquePrefix { 
 
    public static void checkPrefix(String[] strings, String[] pre, String s, int index){
        
        //System.out.println(Arrays.toString(pre));
        for(int i=index-1;i>=0;--i){
            if(s.matches(pre[i])){ 

                if(s.length()==strings[i].length()){
                    //System.out.println("Can't update the previous one, need to update this one");
                    pre[index] = strings[index].substring(0, s.length()+1);
                    checkPrefix(strings, pre, pre[index], index);
                    return;
                }
                else if(s.length() < strings[i].length()){ 
                    //System.out.println("Can update the previous one");
                    pre[i] = strings[i].substring(0, s.length()+1);
                    checkPrefix(strings, pre, pre[i], i);
                    return;
                } 
            }
        }
    }
    
    public static void findPrefixes(String[] strings){
        System.out.println();
        String[] pre = new String[strings.length];
         
        for(int i=0;i<pre.length;++i){
            if(i>0){
                if(strings[i].matches(strings[i-1])){
                    System.out.println("Duplicate string - Error!"); continue; 
                }
            }
            pre[i]=Character.toString(strings[i].charAt(0)); 
            checkPrefix(strings, pre, pre[i], i);
        } 
        System.out.println(Arrays.toString(strings));
        System.out.println(Arrays.toString(pre));
    }
    
    public static void main(String[] args) {

        //Tests
        String[] strings = {"zebra", "dog", "duck", "dove"};
        findPrefixes(strings);

        strings = new String[]{"zebra", "dog", "duck", "dot"};
        findPrefixes(strings);
        
        strings = new String[]{"zebra", "dog", "duck", "dove", "dorm"};
        findPrefixes(strings);

        strings = new String[]{"bearcat", "bear"};
        findPrefixes(strings);

        strings = new String[]{"bearcat", "bearcat"}; 
        findPrefixes(strings);
        strings = new String[]{"bearcat", "bear", "be", "b"}; 
        findPrefixes(strings);

        strings = new String[]{"bear", "dog", "bea", "bearcat"}; 
        findPrefixes(strings);
        
        strings = new String[]{"b", "bb"};
        findPrefixes(strings);
        
        //Killer tests
        strings = new String[]{"b", "bb", "bbb", "bbbb"}; 
        findPrefixes(strings);
        strings = new String[]{"bbbb", "bbb", "bb", "b"};
        findPrefixes(strings);  
    }
}

Output:

[zebra, dog, duck, dove]
[z, do, du, d]

[zebra, dog, duck, dot]
[z, do, du, d]

[zebra, dog, duck, dove, dorm]
[z, dog, du, do, d]

[bearcat, bear]
[be, b]

Duplicate string - Error!
[bearcat, bearcat]
[b, null]

[bearcat, bear, be, b]
[bear, bea, be, b]

[bear, dog, bea, bearcat]
[bea, d, be, b]

[b, bb]
[b, bb]

[b, bb, bbb, bbbb]
[b, bb, bbb, bbbb]

[bbbb, bbb, bb, b]
[bbbb, bbb, bb, b]

Detecting an Infinte Loop in a Linked List - Java

Question: If you have a linked list in which you can traverse only in one direction, and if that linked list has a loop in it, how you will detect it?

Algorithm (Floyd's cycle-finding algorithm):

1. Initialize two pointers p1 (to head) and p2 (to head.next.next). 

2. Both traverse the list but p2 is say 2 steps ahead of p1.

3. If the list has a cycle, p1 and p2 will be equal at some time.

4. If the list doesn't have a cycle, p2 will be pointing to null.

Source:

class Node { 
    int value;
    Node next;
}

public class InfiniteLoop {

    private static Node makeCyclicList() {  
        
        Node head = new Node(); 
        head.next = new Node();
        head.next.next = new Node();
        head.next.next.next = new Node();
        head.next.next.next.next = new Node();
        head.next.next.next = head.next;
        
        return head;
    }

    private static Node makeNonCyclicList(){ 
        
        Node head = new Node(); 
        head.next = new Node();
        head.next.next = new Node();
        head.next.next.next = new Node();
        head.next.next.next.next = new Node(); 
        
        return head;
    }

    public static boolean isInfinite(Node head){
        if(head==null) return false;
        
        Node p1 = head, p2 = head;
        
        if(p2.next==null)return false;
        p2 = p2.next.next;
        
        while(true){
            if(p1==p2) return true; 
            if(p2==null || p2.next == null) return false;
            p1 = p1.next;
            p2 = p2.next.next;
        } 
    }
    
    public static void main(String[] args) {
        System.out.println("List is "+(isInfinite(makeCyclicList())?"cyclic":"acyclic"));
        System.out.println("List is "+(isInfinite(makeNonCyclicList())?"cyclic":"acyclic"));
    }
}

Output:

List is cyclic

List is acyclic

Using java.awt.Robot class

The java.awt.Robot class is used to generate native system input events for the purposes of test automation, self-running demos, and other applications where control of the mouse and keyboard is needed. The primary purpose of Robot is to facilitate automated testing of Java platform implementations.

This tester program tests the important methods of this class.

Source:

import java.awt.AWTException; 
import java.awt.Robot; 
import java.awt.event.InputEvent;

public class JRobot {
    Robot robot;
    public JRobot() throws AWTException{ 
        robot = new Robot();
        System.out.println(robot);
    } 
    
    public void type(String s){ 
        byte[] bytes = s.getBytes();

        for(byte b:bytes){
            if(b>96 && b<123) b-=32;
            robot.keyPress(b);
            robot.delay(200);
            robot.keyRelease(b);
        }
    }
    
    //Performing a right click
    public void rightClick(int x, int y){
        robot.mouseMove(x, y);
        robot.mousePress(InputEvent.BUTTON1_DOWN_MASK);
        robot.mouseRelease(InputEvent.BUTTON1_DOWN_MASK);
    }
  
    //Random cursor movement
    public void testMouseMovement(){
        for(int i=0;i<200;++i){
            robot.mouseMove(i, 200); 
            robot.delay(5);
        }
    }
    
    //Scrolling down
    public void scrollDown(int amount){
        for(int i=0;i<amount;++i){
            robot.mouseWheel(i);
            robot.delay(500);
        }
    }
    
    //Getting pixel colors
    public void printColors(int x, int y){
        for(int i=0;i<200;++i,++x,++y){
            robot.mouseMove(x, y);
            System.out.print("\nPixel at "+x+", "+y+" has color ");
            System.out.print(robot.getPixelColor(x, y));
        }
    }
    
    public static void main(String[] args) throws AWTException{
        JRobot r = new JRobot();
        /*
          Delay before performing every action
          Can be added manually too (using robot.delay(int ms))
        */
        r.robot.setAutoDelay(5); 
        r.testMouseMovement();
        r.rightClick(200, 500);
        r.type("And the secret is... yet to be revealed");
        r.rightClick(590, 500);
        r.scrollDown(5); 
        r.printColors(0, 0);
    }
}

Ordered Symbol Table : Fixed Capacity Implementation [Java]

The symbol table supports the following functions:

void put(Key key, Value val)                      put key-value pair into the table
                                                                     (remove key from table if value is null)

Value get(Key key)                                    value paired with key
                                                                     (null if key is absent)

void delete(Key key)                                  remove key (and its value) from table

boolean contains(Key key)                          is there a value paired with key?

boolean isEmpty()                                      is the table empty?

int size()                                                     number of key-value pairs

Key min()                                                   smallest key

Key max()                                                  largest key

Key floor(Key key)                                    largest key less than or equal to key

Key ceiling(Key key)                                 smallest key greater than or equal to key

int rank(Key key)                                      number of keys less than key

Key select(int k)                                       key of rank k

void deleteMin()                                      delete smallest key

void deleteMax()                                     delete largest key

int size(Key lo, Key hi)                              number of keys in [lo..hi]

Iterable<Key> keys(Key lo, Key hi)          keys in [lo..hi], in sorted order

Iterable<Key> keys()                               all keys in the table, in sorted order

Source:

import java.util.Arrays;

public class SymbolTable<Key extends Comparable<Key>, Value> {

    final private Key[] keys;
    final private Value[] values;
    private int size;

    public SymbolTable(int size) {
        this.keys = (Key[]) new Comparable[size];
        this.values = (Value[]) new Object[size];
    }

    private void swap(Object[] a, int b, int c) {
        Object temp = a[b];
        a[b] = a[c];
        a[c] = temp;
    }

    public void put(Key key, Value val) {
        int pos = 0;
        while (pos < size && keys[pos] != null){
            if(key.compareTo(keys[pos]) > 0) pos++; 
            else if(key.compareTo(keys[pos])==0){
                values[pos] = val; 
                return;
            }else break;
        }
        
        if (pos >= keys.length) return;
        
        if(size==keys.length)size--;
        for (int i = size; i > 0 && i > pos; --i) { 
            keys[i] = keys[i - 1];
            values[i] = values[i - 1]; 
        }
        
        keys[pos] = key;
        values[pos] = val; 
        
        size++; 
    }

    private int findIndex(Key key) {
        int lo = 0, hi = size-1;
        int mid = hi / 2;

        while (lo <= hi) {
            if (key.compareTo(keys[mid]) == 0) {
                return mid;
            } else if (key.compareTo(keys[mid]) < 0) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
            mid = (hi + lo) / 2;
        }
        return mid;
    }

    public Value get(Key key) {
        int index = findIndex(key);
        if(key.compareTo(keys[index])==0)return values[index];
        else return null;
    }

    public void delete(Key key) {
        int index = findIndex(key);
        if(key.compareTo(keys[index])!=0){
            System.out.println("Unable to delete - Key not present");
            return;
        } 
       
        for (int i = index; i+1 < size; ++i) { 
            keys[i] = keys[i+1];
            values[i] = values[i+1]; 
        } 
        keys[size-1] = null;
        values[size-1] = null;
        size--;
    }

    public Key min(){ 
        if(size>=1) return keys[0]; 
        return null;
    }
    
    public Key max(){
        if(size>=1) return keys[size-1];
        return null;
    }
    
    public boolean contains(Key key) {
        return get(key) != null;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public Iterable<Key> keys() {
        return Arrays.asList(keys);
    }
    
    void deleteMin(){
        if(size>=1) delete(keys[0]);
    }
    
    void deleteMax(){
        if(size>=1) delete(keys[size-1]);
    }
    
    public void printTable(String s){
        System.out.print("\n\n"+s+"\n"+Arrays.asList(keys));
        System.out.print("\n"+Arrays.asList(values));
    }
    
    //Find a key less than or equal to the key supplied
    public Key floor(Key key){
        int index = findIndex(key); 
        if(index>0) {
            if(key.compareTo(keys[index])<0) return keys[index-1];
            else return keys[index];
        }
        else if(index==0)return keys[0];
        else return null;
    }
    
    //Find a key greater than or equal to the key supplied
    public Key ceiling(Key key){
        int index = findIndex(key);
        if(index<size-1) {
            if(key.compareTo(keys[index])>0) return keys[index+1];
            else return keys[index];
        }
        else if(index==0) return keys[0];
        else return null;
    }
    
    /*
        The location where the key should have been - Key
        may or may not be present
    */
    public int rank(Key key){
        
        int index = findIndex(key); 
        if(keys[index].compareTo(key)==0)
            return index;
        return -1; //Not present
    }
    
    public Key select(int k){
        if(k<0 || k>=size) return null;   
        return keys[k-1]; 
    } 
    
    //If key isn't present, take floor for lo, ceiling for hi
    int size(Key lo, Key hi){
        //hi>lo doesn't make sense
        if(lo.compareTo(hi)>0){System.out.println("lo must be less than hi");return -1;}
        
        int loIndex = findIndex(lo); 
        if(loIndex>0) 
            if(lo.compareTo(keys[loIndex])<0) loIndex--; 
        
        int hiIndex = findIndex(hi);
        if(hiIndex<size-1) 
            if(hi.compareTo(keys[hiIndex])>0) hiIndex++; 
          
        return hiIndex-loIndex+1;
    }
    
    Iterable<Key> keys(Key lo, Key hi){
        //hi>lo doesn't make sense
        if(lo.compareTo(hi)>0){System.out.println("lo must be less than hi");return null;}
       
        int loIndex = findIndex(lo); 
        if(loIndex>0) 
            if(lo.compareTo(keys[loIndex])<0) loIndex--; 
        
        int hiIndex = findIndex(hi);
        if(hiIndex<size-1) 
            if(hi.compareTo(keys[hiIndex])>0) hiIndex++; 
        
        Key[] subKeys = Arrays.copyOfRange(keys, loIndex, hiIndex+1);
        return Arrays.asList(subKeys);
    }
      
    public static void main(String[] args) {
        
        //Test code
        SymbolTable<Integer, String> table = new SymbolTable<>(3);

        System.out.println("isEmpty()? = "+table.isEmpty());
        table.put(3, "Hi"); 
        System.out.println("isEmpty()? = "+table.isEmpty());
        table.put(1, "There");
        table.put(2, "Hello");
        table.printTable("Full list");
        table.put(0, "Hey");
        table.printTable("Inserting index 0");
        table.delete(0);
        table.printTable("After deleting zeroth");
        table.put(0, "Hi there");
        table.printTable("Inserting new zero");
         
        System.out.println("\n\nTesting the get operation");
        for(int i=0;i<3;++i)System.out.println(table.get(i)+" ");
        System.out.println(table.get(4));
        
        System.out.println(table.size());
        
        System.out.println(table.keys());
        
        System.out.println(table.contains(0));
        System.out.println(table.contains(5));
        
        System.out.println("Min key = "+table.min());
        System.out.println("Max key = "+table.max());
        
        table.deleteMin();
        table.printTable("After deleting min key");
        table.deleteMax();
        table.printTable("After deleting max key");
        
        System.out.println("Min key = "+table.min());
        System.out.println("Max key = "+table.max());
        
        System.out.println("Min key = "+table.min());
        System.out.println("Max key = "+table.max());
         
        System.out.println("Floor of 2 "+table.floor(2));
        System.out.println("Ceiling of 0 "+table.ceiling(0));
        
        table.put(1, "There");
        table.put(2, "Someone"); 
        table.printTable("Considering floor and ceiling ops on this table");
        System.out.println("Floor of 2 "+table.floor(2));
        System.out.println("Ceiling of 0 "+table.ceiling(0));
        
        System.out.println("Rank of 2 = "+table.rank(2));
        System.out.println("Rank of 5 = "+table.rank(5));
        
        table.put(5, "Points");
        table.printTable("Testing the table for size function");
        System.out.println("size(0, 1) = "+table.size(1, 1));
        
        System.out.println("key range "+table.keys(1, 1));
        System.out.println("key range "+table.keys(1, 5)); 
        
        System.out.println("key range "+table.keys(5, 1)); 
    }
}

Output:

isEmpty()? = true
isEmpty()? = false


Full list
[1, 2, 3]
[There, Hello, Hi]

Inserting index 0
[0, 1, 2]
[Hey, There, Hello]

After deleting zeroth
[1, 2, null]
[There, Hello, null]

Inserting new zero
[0, 1, 2]
[Hi there, There, Hello]

Testing the get operation
Hi there
There
Hello
null
3
[0, 1, 2]
true
false
Min key = 0
Max key = 2


After deleting min key
[1, 2, null]
[There, Hello, null]

After deleting max key
[1, null, null]
[There, null, null]Min key = 1
Max key = 1
Min key = 1
Max key = 1
Floor of 2 1
Ceiling of 0 1


Considering floor and ceiling ops on this table
[1, 2, null]
[There, Someone, null]Floor of 2 2
Ceiling of 0 1
Rank of 2 = 1
Rank of 5 = -1


Testing the table for size function
[1, 2, 5]
[There, Someone, Points]size(0, 1) = 1
key range [1]
key range [1, 2, 5]
lo must be less than hi
key range null 

Displaying the contents of an arbitrarily complex nested list - Coding Interview Question

Question:

Write a function (in pseudo-code) called dumpList that takes as its parameters a string and a reference to an arbitrarily complex nested list and prints the value of each list element on a separate line. The value of each line should be preceded by the string and numbers indicating the depth and index of the element in the list. Assume that the list contains only strings and other nested lists.

Let’s take a look at an example of what we want exactly in the dumpList function. Suppose that you are given the following nested list. A nested list is just a list that contains other lists as well – so in the list below you see that it also contains the lists ['a','b','c'] and ['eggs'] :

List = ['a string', ['a','b','c'], 'spam', ['eggs']] 

And, suppose that the string passed in to the dumpList function is called ‘Foo’, then the output of dumpList(‘Foo’, List) would look like this:

Foo.0:  a string
Foo.1.0: a
Foo.1.1 : b
Foo.1.2: c
Foo.2: spam
Foo.3.0: eggs

The dumpList function should be less than 20 lines of pseudo-code. 

Code (Java):

import java.util.Random; 

class Node{
    String value;
    Node next;
    Node subList;
    
    Node(String value){
        this.value = value;  
    }
}

public class dumpList {
    
    /*
        Just constructing a random list
    */
    public static Node buildList(){
        Node node[] = new Node[10];
        Random rand = new Random();
        
        node[0] = new Node("first");  
        
        //Setting random string values
        for(int i=1;i<node.length;++i){
            node[i] = new Node(Character.toString((char)(97+rand.nextInt(26))));
            node[i-1].next = node[i];
        } 
        
        Node newNode = new Node("This");
        node[3].subList = newNode;
        newNode.next = new Node("is");
        newNode.next.subList = new Node("a");
        newNode.next.subList.next = new Node("line");
        newNode.next.subList.next.subList = new Node("!!");
        return node[0];
    }
    
    //The actual function
    public static void dumpList(String string, Node node){
        int i = 0;
        string+="."; 
        
        while(node!=null){ 
            System.out.println(string+i+": "+node.value);
            Node subList = node.subList;
                if(subList != null)
                    dumpList(string+i, subList);
            node = node.next; 
            i++;
        }
    }
    
    public static void main(String[] args){
        dumpList("Foo", buildList());
    }
}

Output:

Foo.0: first
Foo.1: o
Foo.2: g
Foo.3: o
Foo.3.0: This
Foo.3.1: is
Foo.3.1.0: a
Foo.3.1.1: line
Foo.3.1.1.0: !!
Foo.4: w
Foo.5: v
Foo.6: p
Foo.7: i
Foo.8: z
Foo.9: x

Division without using the Division Operator [Java]

This program divides two numbers without using the division operator (/).

Source:

public class DivisionWithout {

    public static void main(String[] args) {
        double running = 0, dividend = 4.25, divisor = 2.1;
        /*
        Another test case
        
        double running = 0, dividend = 6.06, divisor = 3;
        */
        int decimalDigits = 10;
        int count = 0;
        boolean flag = true; 
        
        for (int i = 0; i < decimalDigits+1; ++i) {
            while ((running + divisor) <= dividend){
                count++;
                running += divisor;
            } 
            System.out.print(count);

            if (running == dividend) break;

            if (flag) {
                System.out.print(".");
                flag = false;
            } 
            dividend = (dividend - running) * 10; 
            
            count = 0;
            running = 0; 
        }        
    }
}

Output (for the test case above):

2.0238095238

3-Way-Quicksort with Improvements [Tukey's Ninther]

Improvements:

1. If the number of elements is less than 10, use insertion sort.

2. If the number of elements is more, swap the first element with mid element.

3. If the number of elements is even more, swap the first element of the subarray with the median of the three elements (lo, mid, hi).

4. If the number of elements is even more, swap the first element with (Tukey's Ninther).

Source:

package ThreeWayQuickSort;

import java.util.Arrays;

public class ThreeWayQuicksort { 
    
    public static void qSort(int[] a){
        qSorter(a, 0, a.length-1);
    }
    
    private static void qSorter(int[] a, int lo, int hi){
        
        if(lo>=hi) return;
        
        /*
          If the sub array is of size 10 or less
          it is better to use insertion sort instead
        */
        if (hi - lo <= 10) { 
            InsertionSort.insertionSort(a, lo, hi);
            return;
        }

        if(hi - lo <= 25) {
            /*
              If the sub array is small, we can just use the middle
              element as the element to compare with
            */
            swap(a, lo, (lo+hi)/2); 
        }else if(hi - lo <= 50){ 
            /*
              If the sub array is medium in size, we can use the median
              of three elements lo, (mid), and hi and set it as the
              element to compare with.
            */
            int m = median(a, lo, (lo + hi) / 2, hi); 
            swap(a, m, lo); 
        }else{  
            
            //Tukey's ninther 
            int a1[] = new int[3];
            int a2[] = new int[3];
            int a3[] = new int[3]; 
            
            int gap = (hi-lo+1)/9;  
            if(((hi-lo+1)+gap)%9<gap)gap++; //Tricky logic!
            
            //System.out.println("Gap = "+gap);
            
            //Indexes
            int a1I = 0, a2I = 0, a3I = 0, arrayNo = 0;
            for(int i=lo;arrayNo<9;i+=gap){ 
               if(arrayNo < 3)      a1[a1I++] = i; 
               else if(arrayNo < 6) a2[a2I++] = i;
               else                 a3[a3I++] = i;
               
               arrayNo++;
            }
            
            /* Debug code
            System.out.println("Median of "+Arrays.toString(a1));
            System.out.println("Median of "+Arrays.toString(a2));
            System.out.println("Median of "+Arrays.toString(a3));
            */
            
            int median = median(a, median(a, a1[0], a1[1], a1[2]),
                                   median(a, a2[0], a2[1], a2[2]),
                                   median(a, a3[0], a3[1], a3[2]));
            swap(a, median, lo);
            //System.out.println("Ninther = "+a[lo]);
        }
        
        int lt = lo, gt = hi, i = lo;
        int v = a[lo];
        
        while(i<=gt){
            if(a[i]<v){ swap(a, i++, lt++);}
            else if(a[i]>v){swap(a, i, gt--);}
            else i++;
            //System.out.println(Arrays.toString(a));
        }
        
        qSorter(a, lo, lt-1); 
        qSorter(a, gt+1, hi);
    }
    
    public static int median(int[] x, int a, int b, int c) {
        if (x[a] > x[b] && x[a] > x[c]) { if (x[b] > x[c]) return b; else return c; }
        else if (x[b] > x[a] && x[b] > x[c]) { if (x[a] > x[c]) return a; else return c; } 
        else if (x[c] > x[a] && x[c] > x[b]) { if (x[a] > x[b]) return a; }
        return b;
    }
    
    private static void swap(int[] array, int a, int b){ 
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
    
    public static void main(String[] args){
        //Two arrays to test
        //int array[] = {2,3,5,7,8,3,5,6,8,4,3,2,5,6,7,8};
        int array[] = {2,3,4,1,5,6,7,8,9,10,11,2,3,4,5,2,3,14,19,20,23,22,1,4,3,2,5};
        qSort(array);
        System.out.println(Arrays.toString(array));
    }
}

class InsertionSort {

    public static void insertionSort(int[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; ++i) {
            int j = i;
            while (a[j] < a[j - 1]) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
                if (--j == 0) {
                    break;
                }
            }
        }
    }
}

Output for test input data:

[1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 7, 8, 9, 10, 11, 14, 19, 20, 22, 23]

Quick Sort With Minor Improvements

Improvements:

1. Setting the element with index hi (the pivot element) equal to the median of the three elements lo, hi and (lo+hi) / 2 so that the probability that it lies in between the values is more.

2. Using the faster Insertion sort if the number of elements in the sub array is less than some predefined value (the value 5 is used here).

Source:

package QuickSort;

import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int array[]) {
        quickSorter(array, 0, array.length - 1);
    }

    public static void quickSorter(int array[], int lo, int hi) {
        if (lo > hi) {
            return;
        }

        //If array size is less than 5, we will use Insertion Sort
        if (hi - lo <= 5) { 
            InsertionSort.insertionSort(array, lo, hi);
            return;
        }

        int m = median(array, lo, (lo + hi) / 2, hi); 
        swap(array, m, hi);

        int partition = partition(array, lo, hi);
        quickSorter(array, lo, partition - 1);
        quickSorter(array, partition + 1, hi);
    }

    private static int partition(int array[], int lo, int hi) {
        int partitionIndex = lo;

        for (int i = lo; i < hi; ++i) {
            if (array[i] < array[hi]) {
                swap(array, partitionIndex, i);
                partitionIndex++;
            }
        }
        swap(array, partitionIndex, hi);
        return partitionIndex;
    }

    public static int median(int[] x, int a, int b, int c) {
        if (x[a] > x[b] && x[a] > x[c]) { if (x[b] > x[c]) return b; else return c; }
        else if (x[b] > x[a] && x[b] > x[c]) { if (x[a] > x[c]) return a; else return c; } 
        else if (x[c] > x[a] && x[c] > x[b]) { if (x[a] > x[b]) return a; }
        return b;
    }

    public static void swap(int array[], int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 4, 3, 2, 1, 3, 44, 21, 3, 2, 33, 12, 123};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

class InsertionSort {

    public static void insertionSort(int[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; ++i) {
            int j = i;
            while (a[j] < a[j - 1]) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
                if (--j == 0) {
                    break;
                }
            }
        }
    }
}

Output:

[1, 2, 2, 3, 3, 3, 3, 4, 12, 21, 33, 44, 123]

Calculating the value of PI accurately to 5 decimal places

This program uses the Gregory-Leibniz series for calculating the value of PI. Note that this series is slow and there exist other faster algorithms for calculating the value of PI. 

A simple infinite series for π is the Gregory–Leibniz series:

As individual terms of this infinite series are added to the sum, the total gradually gets closer to π, and – with a sufficient number of terms – can get as close to π as desired. It converges quite slowly, though – after 500,000 terms, it produces only five correct decimal digits of π.

Source:

public class PI { 

    static float calculate() {
        float denom = 1, sum = 0, numerator = -4.0f;   
    
        for(int i=0;i<500000;++i){
            float nextTerm = (numerator=-numerator) / (denom);  
            sum += nextTerm;  
            denom+=2;
        }
        return sum;
    }
    
    public static void main(String[] args) { 
        System.out.println(calculate()); 
    }
}

Output:

3.141594

java.util.Comparator Usage Example

java.util.Comparator interface is used to manually define the criteria on which to compare objects. For example, same type of two objects can be compared based on their IDs or Names (for student objects) or color, price (for fruit objects).

The comparator interface has a method compareTo(Object1, Object2) which returns an int value based on the result of comparision

-1 if obj1 is less than obj2
0 if equal
+1 if obj1 is greater than obj2.

Here is an example:

import java.util.Arrays;
import java.util.Comparator;

//This is the class on which we'll be testing our comparators
class Student {

    private final String name;
    private final int id;
    
    //We've made static comparator Objects to make them Readily accessible
    public static Comparator<Student> NAME_COMPARE = new NameComparatorImplementation();
    public static Comparator<Student> ID_COMPARE = new IDComparatorImplementation();
    
    //This and the next inner class are the implementations of our comparators
    private static class NameComparatorImplementation implements Comparator<Student> {

        @Override
        public int compare(Student s1, Student s2) {
            return s1.name.compareTo(s2.name);
        }
    }

    private static class IDComparatorImplementation implements Comparator<Student> {

        @Override
        public int compare(Student s1, Student s2) {
            return s1.id < s2.id ? -1 : s1.id > s2.id ? 1 : 0;
        } 
    }
     
    public Student(String name, int id){
        this.name = name;
        this.id = id;
    }
    
    @Override
    public String toString(){
        return "Name: "+name+" ID: "+id;
    }
}

//This class manually tests the comparators (uses their comparator.compare() method to sort)
class ComparatorManualTester{
    
    //Insertion Sort used
    public static <T> void sort(T[] array, Comparator<T> comparator){
        for(int i=0;i<array.length-1;++i){
            for(int j=i+1;j>0;--j){
                if(comparator.compare(array[j], array[j-1])<0){
                    swap(array, j, j-1);
                }else break;
            }
        }
    }
    
    private static void swap(Object[] array, int index1, int index2){
        Object temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
}

public class TestComparator {
    public static void main(String[] args){
        Student[] arrayOfStudents = new Student[]{new Student("C", 10), 
                                                  new Student("B", 1),
                                                  new Student("D", 155), 
                                                  new Student("A", 2),
                                                  new Student("F", 12)};
        
        //Arrays.sort(ArrayToSort, Comparator) - is predefined in java.util.Arrays
        //Sort by name using Arrays.sort(array, NameComparator) 
        Arrays.sort(arrayOfStudents, Student.NAME_COMPARE);
        System.out.println(Arrays.toString(arrayOfStudents));
        
        //Sort by ID using Arrays.sort(array, IDComparator)
        Arrays.sort(arrayOfStudents, Student.ID_COMPARE);
        System.out.println(Arrays.toString(arrayOfStudents));
        
        //Testing it by manually using the comparator in the static
        //sort method defined in ComparatorManualTester class.
        ComparatorManualTester.sort(arrayOfStudents, Student.NAME_COMPARE);
        System.out.println(Arrays.toString(arrayOfStudents));
        
        ComparatorManualTester.sort(arrayOfStudents, Student.ID_COMPARE);
        System.out.println(Arrays.toString(arrayOfStudents));
    } 
}

Output:
[Name: A ID: 2, Name: B ID: 1, Name: C ID: 10, Name: D ID: 155, Name: F ID: 12]
[Name: B ID: 1, Name: A ID: 2, Name: C ID: 10, Name: F ID: 12, Name: D ID: 155]
[Name: A ID: 2, Name: B ID: 1, Name: C ID: 10, Name: D ID: 155, Name: F ID: 12]
[Name: B ID: 1, Name: A ID: 2, Name: C ID: 10, Name: F ID: 12, Name: D ID: 155]

Bottom Up Merge Sort Java Implementation

Bottom up merge sort sorts the array without using recursion. It is 10% slower than the top down (recursive) mergesort. The idea is to start sorting the array elements from the start in groups of 2, 4, 8, 16, and so on (powers of two). So that the effect is the same as the recursive algorithm.
Here is a trace for sorting numbers 13,12, ..., 1

 

Source:

import java.util.Arrays;

public class BottomUpMergeSort {

    public static void merge(int[] orig, int[] aux, int start, int mid, int end) {
        int i, j, z = start; 
        
        if(orig[mid] <= orig[mid+1])return; 
        
        for(i=start, j = mid+1; i!=mid+1 || j!=end+1;){
            if(i==mid+1)               while(j!=end+1){ aux[z++] = orig[j++]; }
            else if(j==end+1)          while(i!=mid+1){ aux[z++] = orig[i++]; }
            else if(orig[i]<=orig[j])  aux[z++] = orig[i++];
            else                       aux[z++] = orig[j++];
        }    
        System.out.println(Arrays.toString(orig));
        System.out.println("start = "+start+" mid = "+mid+" end = "+end);
        System.out.println(Arrays.toString(aux)+"\n");
        System.arraycopy(aux, start, orig, start, end-start+1);
    }

    public static void sort(int[] orig, int[] aux, int start, int end) {
        int N = orig.length;
        for (int sz = 1; sz < N; sz *= 2) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(orig, aux, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N-1));
            }
        }
    }

    public static void main(String[] args) {
        int array[] = {11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        int aux[] = new int[array.length];
        sort(array, aux, 0, array.length - 1);
    }
}

lo < N - sz 
takes care to see that the mid value falls before end. 

lo < N - sz
lo + sz < N
lo + sz - 1 < N - 1
mid < N - 1

Math.min() takes care to see that end does not extend beyond the last index.

Output:

[11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
start = 0 mid = 0 end = 1
[10, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1]
start = 2 mid = 2 end = 3
[10, 11, 8, 9, 0, 0, 0, 0, 0, 0, 0]
[10, 11, 8, 9, 7, 6, 5, 4, 3, 2, 1]
start = 4 mid = 4 end = 5
[10, 11, 8, 9, 6, 7, 0, 0, 0, 0, 0]
[10, 11, 8, 9, 6, 7, 5, 4, 3, 2, 1]
start = 6 mid = 6 end = 7
[10, 11, 8, 9, 6, 7, 4, 5, 0, 0, 0]
[10, 11, 8, 9, 6, 7, 4, 5, 3, 2, 1]
start = 8 mid = 8 end = 9
[10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0]
[10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 1]
start = 0 mid = 1 end = 3
[8, 9, 10, 11, 6, 7, 4, 5, 2, 3, 0]
[8, 9, 10, 11, 6, 7, 4, 5, 2, 3, 1]
start = 4 mid = 5 end = 7
[8, 9, 10, 11, 4, 5, 6, 7, 2, 3, 0]
[8, 9, 10, 11, 4, 5, 6, 7, 2, 3, 1]
start = 8 mid = 9 end = 10
[8, 9, 10, 11, 4, 5, 6, 7, 1, 2, 3]
[8, 9, 10, 11, 4, 5, 6, 7, 1, 2, 3]
start = 0 mid = 3 end = 7
[4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3]
[4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3]
start = 0 mid = 7 end = 10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]