dsp:getvalueof

It creates a variable in a given scope or in page scope if none specified.

With  you can create a constant, param or a constant value.

Defining constant value:

The equivalent in JSP:
String age = “25″;

Defining a parameter in request scope:

The equivalent in JSP:
String age = request.getParameter(“customerAge”);

Defining a bean:

The equivalent in JSP:
Employee employee = new Employee();

Motivation ;)

The BUG bit me :)))

Adam Huber !! I owe the first 10 minutes of my office time to your creation..  Don't believe me ? Checkout the pic below..

For anyone who doesn't know who "BUG" is, please head over to this site (www.bugcomic.com) or click on the below pic of the lovable cute guy ;))

I guarantee you, you will be hooked !!

Sorting Shown Visually

I found this site that provides a visual depiction of different sorting algorithms under different conditions.
Please take a look :)

http://www.sorting-algorithms.com/

Pill Problem Solution

For those of you who did not get it ;)

Keep aside the 3 pills for later. Take a set of pills from the bottles again (Hopefully be a little less clumsy from now on .. Dude, your life hangs in the balance !! ) .. Continue taking the pills everyday until the day before the end of the prescription month. Now you will be left with one pill in one bottle and none in the other. Mix the one with the 3 pills kept aside.. Now you have 4 pills (2 of one kind and 2 of the other).

Tricky part ;)) .. Divide the 4 pills into halves, eating one half of each as you make them .. Voila ! You just saved your life !! Eat the rest of the halves the next day on your way to the pharmacy ;))

Pill Problem

You have a two identical bottles of pills, containing pills that look identical except for their internal chemical composition. Looking/tasting/smelling them ,ie, the physical attributes will not let you know the difference.

The Rules
You HAVE to eat exactly one pill each from each bottle everyday.
If you eat more than one pill of each, you die.
If you eat less than one pill of each, you die.
If you do not eat both pills for a day, you die.
The bottle cannot be refilled until the end of prescription month, which basically means if there are 30 pills in a bottle, then that bottle can be refilled only after 30 days.. NOT before.

The Problem
You start eating the pills religiously following the rules for a couple of days. On the third day, lethargy sets in. when you tip the bottles over to get the pills, out of one bottle, two pills fall out instead of one.
Oboy !! Now you are left with three identical pills on one hand without any way of telling them apart ..

Objective
How do you live to get to the end of the prescription month ?


-- Google Interview

Yet Another Code Snippet for Merge Sort (Java)

Conceptually, merge sort works as follows:

1. Divide the unsorted list into two sublists of about half the size
2. Sort each of the two sublists
3. Merge the two sorted sublists back into one sorted list.

The algorithm was invented by John von Neumann in 1945.

The following code shows how to implement merge sort in Java.

/**      * Mergesort algorithm.      * @param a an array of Comparable items.      */     public static void mergeSort( Comparable [ ] a ) {         Comparable [ ] tmpArray = new Comparable[ a.length ];         mergeSort( a, tmpArray, 0, a.length - 1 );     }          /**      * Internal method that makes recursive calls.      * @param a an array of Comparable items.      * @param tmpArray an array to place the merged result.      * @param left the left-most index of the subarray.      * @param right the right-most index of the subarray.      */     private static void mergeSort( Comparable [ ] a, Comparable [ ] tmpArray,             int left, int right ) {         if( left < right ) {             int center = ( left + right ) / 2;             mergeSort( a, tmpArray, left, center );             mergeSort( a, tmpArray, center + 1, right );             merge( a, tmpArray, left, center + 1, right );         }     }          /**      * Internal method that merges two sorted halves of a subarray.      * @param a an array of Comparable items.      * @param tmpArray an array to place the merged result.      * @param leftPos the left-most index of the subarray.      * @param rightPos the index of the start of the second half.      * @param rightEnd the right-most index of the subarray.      */     private static void merge( Comparable [ ] a, Comparable [ ] tmpArray,             int leftPos, int rightPos, int rightEnd ) {         int leftEnd = rightPos - 1;         int tmpPos = leftPos;         int numElements = rightEnd - leftPos + 1;                  // Main loop         while( leftPos <= leftEnd && rightPos <= rightEnd )             if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )                 tmpArray[ tmpPos++ ] = a[ leftPos++ ];             else                 tmpArray[ tmpPos++ ] = a[ rightPos++ ];                  while( leftPos <= leftEnd )    // Copy rest of first half             tmpArray[ tmpPos++ ] = a[ leftPos++ ];                  while( rightPos <= rightEnd )  // Copy rest of right half             tmpArray[ tmpPos++ ] = a[ rightPos++ ];                  // Copy tmpArray back         for( int i = 0; i < numElements; i++, rightEnd-- )             a[ rightEnd ] = tmpArray[ rightEnd ];     }

Merge Sort (Java)

The universally used sorting algorithm ..

Merge sort is a sorting algorithm that uses O(n log n) (Big O Notation) comparisons to sort a list of n elements. 


Merge sort uses the divide and conquer strategy, dividing the list of elements into two sub-lists, sorts them and merges them back together to a sorted list. 


The strength of merge sort is that you always merge two lists that you know are already sorted, therefore the merging on each level will only take O(n) operations.


No easy way to understand it .. hope this helps ;))

If you really want to tax your brain with mathematics :P, then http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/mergeSort.htm is the place for you !


This link also has a very good explanation for Merge Sort : http://www.mycstutorials.com/articles/sorting/mergesort

Java Code

public class Mergesort {
 private int[] numbers;
 private int[] helper;

 private int number;

 public void sort(int[] values) {
  this.numbers = values;
  number = values.length;
  this.helper = new int[number];
  mergesort(0, number - 1);
 }

 private void mergesort(int low, int high) {
  // Check if low is smaller then high, if not then the array is sorted
  if (low < high) {
   // Get the index of the element which is in the middle
   int middle = (low + high) / 2;
   // Sort the left side of the array
   mergesort(low, middle);
   // Sort the right side of the array
   mergesort(middle + 1, high);
   // Combine them both
   merge(low, middle, high);
  }
 }

 private void merge(int low, int middle, int high) {

  // Copy both parts into the helper array
  for (int i = low; i <= high; i++) {
   helper[i] = numbers[i];
  }

  int i = low;
  int j = middle + 1;
  int k = low;
  // Copy the smallest values from either the left or the right side back
  // to the original array
  while (i <= middle && j <= high) {
   if (helper[i] <= helper[j]) {
    numbers[k] = helper[i];
    i++;
   } else {
    numbers[k] = helper[j];
    j++;
   }
   k++;
  }
  // Copy the rest of the left side of the array into the target array
  while (i <= middle) {
   numbers[k] = helper[i];
   k++;
   i++;
  }

 }
}

Insertion Sort (Java)

Click to view operation.

Integer Array

  public static int[] insertionsort(int[] input){

       for(int i=1; i= 0 && input[j] > value){

               input[j+1] = input[j];

               j--;

           }

           input[j+1] = value;

       }

       return input;

   }

Object Array

   public static > T[] insertionsort(T[] input){

       for(int i=1; i= 0 && input[j].compareTo(value)>0){

               input[j+1] = input[j];

               j--;

           }

           input[j+1] = value;

       }

       return input;

   }

Detection of Looping in Linked Lists

A Linked List is basically data stored in a linear form, like a list or an array.
It can be considered as the following structure

 [illustration only]

The  address(this) is the memory location of the initialized [but not yet assigned] linked list object. When there are no values added yet in a linked list, then address(next) value will be null. This will always be null for the last object structure in the list ( hint:: That's how you know you have reached the last element :) )

Alrighty then, you can do the standard functions to traverse the list and get the values.

Now for the mind bender..
say there is some sort of data corruption or a wrong input, and the list has a loop in it !

It becomes an inadvertent loop. How do you find a loop in your linked system?

There are ways to find out, and then there are ways to find out ;)
For an explanation for all of the ways you can do it, please refer  http://ostermiller.org/find_loop_singly_linked_list.html

The best method to do it is the "Hare and Tortoise" Algorithm (Floyd's Cycle Finding Algorithm).

The method basically uses 2 incrementers, one of them incrementing by one and the other incrementing by two. Consider the Red Spot as the 1st incrementer and the Blue Spot as the 2nd.

At the 0th iteration,

When iterator step = 1

When iterator step = 2

When iterator step = 3

And Voila !!! If we check the object values of the objects pointed by the two iterators, and we determine them to be equal, we have the position where the loop occurs ! This happens because the second iterator goes twice as fast around the loop and catches up to the first one if there is indeed a loop.

And since it takes only one iteration of the main list to actually determine the loop presence, the algorithm is said to be of O(n) Time Complexity. Also it takes only a fixed number of variables (two iterators) to determine the loop presence.


Pseudo Code Snippet


Iterator i = list.Iterator(); 1-step
Iterator j = list.Iterator(); 2-step


while{
        // increment iterator by two (one step at a time)

        if(j has next element){
            j= j.next();
        }else{
          // reached end of list via iterator j .. return, no loop present
        }

        if(j has next element){
            j= j.next();
        }else{
            // reached end of list via iterator j .. return, no loop present
        }


        // actually the conditional check code is not required since 
        // whatever the iterator i is going through, j has already gone through
        // but its still left in for illustration purpose


        // increment iterator by one
        if(i has next element){
            i= i.next();
        }else{
           // reached end of list via iterator i .. return, no loop present
        }

        // Check the nodes are equal
        if(node(i) == node(j)){
                // Nodes are identical ..  loop found .. return loop position (i or j)
        }
}