Compare ArrayList and LinkedList

ArrayList
Pros
1. Find nth element in O(1)
2. Adding an element to end is O(1)
Cons
1. Deletion/Insertion at an arbitrary point in O(n)
2. Insertion to a sorted array is O(n)

Linked List
Pros
1. Insertion/Deletion is easy
2. For highly dynamic lists
Cons
1. Find nth element is O(n)

CAS – CompareAndSwap in Java 5.0

Most processor architectures, including IA32 and Sparc, have implemented a compare-and-swap (CAS) instruction.CAS(A,B) means “I think V should have the value A; if it does, put B there, otherwise don’t change it but tell me I was wrong.”. When multiple threads attempt to update the same variable simultaneously using CAS, one wins and updates the variable’s value, and the rest lose.

public class SimulatedCompareAndSwap {
    private int V;

    public synchronized int get() {
        return V;
    }

    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        int oldValue = V;
        if (oldValue == expectedValue)
            V = newValue;
        return oldValue;
    }

    public synchronized boolean compareAndSet(int expectedValue,
                                              int newValue) {
        return (expectedValue == compareAndSwap(expectedValue, newValue));
    }
}

A non-blocking counter can be implemented using CAS as below

public class NonBlockingCounter {
    private SimulatedCompareAndSwap value;

    public int getValue() {
        return value.get();
    }

    public int increment() {
        int v;
        do {
            v = value.get();
        } while (v != value.compareAndSwap(v, v + 1));
        return v + 1;
    }
}

CAS-based counters significantly outperform lock-based counters if there is even a small amount of contention, and often even if there is no contention.
This used by the atomic variable classes (AtomicXxx in java.util.concurrent. atomic) to provide an efficient CAS operation on numeric and reference types; these atomic variable classes are used, directly or indirectly, to implement most of the classes in java.util.concurrent.

Implementation in AtomicInteger for incrementAndGet is as follows

    public final int incrementAndGet() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return next;
        }
    }

Source: http://www.amazon.com/dp/0321349601

Find Minimum and Maximum in an array in 3N/2 Comparisons – Java Source Code

  public static void findMinMax(int[]a)
  {
     int min = 99999;
     int max = -99999;
     int comp =0;
     for (int i = 0; i < a.length; i+=2)
     {
         int lmax,lmin;
         if(i+1==a.length)
         {
            lmax = a[i];
            lmin=a[i];
         }else{

           if(a[i] > a[i+1])
           {
              lmax=a[i];
              lmin=a[i+1];
           }else
           {
              lmax=a[i+1];
              lmin=a[i];
           }
         }
         if(max < lmax)max=lmax;
         if(min > lmin)min=lmin;

     }
     System.out.println("Max="+max+" Min="+min);

  }

Quicksort – Java Source Snippet


public class QuickSort
{

  public static void swap(int[]a ,int i,int j)
  {
    int tmp = a[i];
    a[i]=a[j];
    a[j]=tmp;
  }

 // This logic will never give the location of the pivot element after the partition
  public static int partitionQuickSort(int[] a,int start,int end,int pivot)
  {
    int lo=start;
    int hi=end;
    int pivotVal = a[pivot];
    while(lo < = hi)
    {
      while(a[lo] < pivotVal)lo++;
      while(a[hi] > pivotVal)hi--;
      if(lo < = hi) {swap(a,lo,hi);
          lo++;
          hi--;
        }
    }
    return lo;
  }

  public static void quickSort(int[] inp,int start,int end)
  {
    if(start>=end)return;
    int mid = (start+end)/2;
    int loc = partitionQuickSort(inp,start,end,mid);
    if(loc-1 > start)    quickSort(inp,start,loc-1);
    if(end > loc)quickSort(inp,loc,end);
  }

    public static void printArray(int[] a)
  {
    for (int i = 0; i < a.length; i++)
    {
      System.out.print(a[i]+" ");
    }
    System.out.println();
  }

  /**
   *
   * @param args
   */
  public static void main(String[] args)
  {
    QuickSort quickSort = new QuickSort();
    int []inp = new int[]{9,8,5,6,2,2,2,2,3,4,7};
    quickSort(inp,0,inp.length-1);
    printArray(inp);
  }
}

Mirror a binary tree – Java Source Snippet

  public static void  mirror(Node root)
  {
     if(root==null)return;
     Node left = root.left;
     mirror(root.left);
     mirror(root.right);
     root.left = root.right;
     root.right = left;
  }

Nth Fibonacci Number using Iteration – Java Source Snippet


  public static int getNthFibonacci(int n)
  {
    if(n==1)return 0;
    if(n==2)return 1;
    int a=0;
    int b=1;
    for (int i = 0; i < n-2 ; i++)
    {
       b = a+b;
       a = b -a;
      // System.out.println(b);
    }
    return b;
  }

Activity Selection Algorithm – Java Source Snippet


class Activity implements Comparable
  {
    int start;
    int finish;

    public Activity(int x,int y)
    {
      start=x;
      finish=y;
    }

    public String toString()
    {
      return "[["+this.start+"-"+this.finish+"]]";
    }

    public int compareTo(Object obj)
    {
      Activity a = (Activity) obj;
      return this.finish - a.finish;
    }

  }

 public static ArrayList schedule(Activity [] list)
  {
    Arrays.sort(list);
    printActivityList(list);
    System.out.println();
    ArrayList ret = new ArrayList();
    ret.add(list[0]);
    int currentFinishTime = list[0].finish;
    for (int i = 1; i < list.length ; i++)
    {
       if(list[i].start > currentFinishTime)
       {
         //Add activity j to ret
         ret.add(list[i]);
         currentFinishTime = list[i].finish;
       }
    }
    return ret;
  }

Print a Square Matrix Spirally – Java Source Code

   public static void printSpirally(int[][] a) {
        int N = a[0].length;
        for (int i = N - 1, j = 0; i > 0; i--, j++) {
            for (int k = j; k < i; k++)System.out.println(a[j][k]);
            for (int k = j; k < i; k++)System.out.println(a[k][i]);
            for (int k = i; k > j; k--)System.out.println(a[i][k]);
            for (int k = i; k > j; k--)System.out.println(a[k][j]);
        }
        int middle = (N / 2);
        if ((N % 2) == 1) {
            System.out.println(a[middle][middle]);
        }
    }

Reverse Vowels in a String – Java Source Code

    public static boolean isVowel(char inp) {
        char c = Character.toUpperCase(inp);

        if ((c == 'A') || (c == 'E') || (c == 'I') || (c == 'O') || (c == 'U')) {
            return true;
        }

        return false;
    }

    public static void reverseVowels(char[] a) {
        int start = 0;
        int end = a.length - 1;

        while (start < end) {
            while ((start < a.length) && !isVowel(a[start])) {
                start++;
            }

            while ((end > 0) && !isVowel(a[end])) {
                end--;
            }

            if ((start > = end) || (start == a.length) || (end == -1)) {
                return;
            }

            //swap start and end;
            char t = a[start];
            a[start] = a[end];
            a[end] = t;
            start++;
            end--;
        }
    }

Print Binary Search Tree Level By Level – Java Source Code

Print all nodes level by level


   public static void printlevelByLevel(Node root)
   {
      Node current = root;
      Queue q = new Queue();
      q.add(root);
      while(!q.isEmpty())
      {
        Node c =(Node) q.remove();
        System.out.print(c.val+",");
        if(c.left!=null)q.add(c.left);
        if(c.right!=null)q.add(c.right);
      }
   }

Print all nodes level by level and priting also when each level finishes


      public static void printlevelByLevel2Queues(Node root)
   {
      Node current = root;
      Queue q[] = new Queue[]{new Queue(),new Queue()};
      int currentQ=0;
      q[currentQ].add(root);
      while(!q[currentQ].isEmpty() || !q[1-currentQ].isEmpty() )
      {
        if(q[currentQ].isEmpty())
        {
          System.out.println("One level Finished... Switching queue...");
          currentQ = 1- currentQ;
        }
        Node c =(Node) q[currentQ].remove();
        System.out.print(c.val+",");
        if(c.left!=null)q[1-currentQ].add(c.left);
        if(c.right!=null)q[1-currentQ].add(c.right);
      }
   }