new java puzzlers (As presented in Javapolis --2007)

Just to flex your java muscles here are some java puzzlers -- taken from the javapolis 2007 session by neal gafter and josh bloch

1) Set of Shorts (hehehe)

public class ShortSet {
public static void main(String[] args) {
SetshortSet=new HashSet();
for(short i=0;i<100;i++){
shortSet.add(i);
shortSet.remove(i-1);
}
System.out.println("Size of Set =" + shortSet.size()) ;
}
}
The choices are
1)1
2)100
3) Throws an exception
4) None of the above

2)Racy little number

public class Test extends TestCase {
int number;
public void test()throws InterruptedException{
number=0;
Thread t=new Thread(new Runnable(){
public void run(){
assertEquals(2, number);
}
});
number=1;
t.start();
number++;
t.join();
}

}
What is the outcome of this test
1) Passes Sometimes
2)Fails Sometimes
3)Always passes
4) Always hangs

How to derail your experts and ruin their performance

Its very simple, force them to follow rules. Experts draw a lot based on their experience and intuition as opposed to novices who need a set of rules which tells them what to do exactly to finish the task at hand, like filling your tax return forms(i never figured that out, just follow whats written there). Any corporate/methodology which follows iron clad rules for development tends to pull the experts down and drags their performance to a novice level. The industry tends to ruin experts often in this way. We can say that they are trying to herd racehorses, rather than racing them. Intuition is a tool to an expert, but organizations discount it saying its not scientific/repeatable etc. Conversely, we also tend to take novices and throw them in the
deep end of the development pool—far over their heads. Here we’re trying to race sheep. A misguided sense of political correctness tends to treat all developers the same way, irrespective of the fact that there is a 20:1 to 40:1 in the productivity of the developers.

Living out of the box

I managed to read the book from the Arbinger institute related to living out of the box(cant remember the name of the book). Seems a similar concept to the one proposed by psychologists Kruger and Dunning in their paper Unskilled and Unaware of it:How difficulties in recognizing one's own incompetence leads to Inflated Self Assessment.

The Dreyfus model

Developed by two brothers who were interested in AI, the Dreyfus model has been used successfully in different areas for developing skills and understanding how to transition from novice to an expert. Rather than analyzing something as a whole, it treats things on a per skill level. For example, someone might be a novice cook but be great at playing tennis. Interesting concept and worth reading, researching and applying.

The bane of java exceptional handling

Exception handling should be fail safe. What it implies is that the last exception which is thrown should be propagated up the call stack. However taking a look at a simple example shows how complicated exceptional handling can be.
Lets take a scenario of the following block of code where we are trying to open a file

InputStream input = null;

 try{

   input = new FileInputStream("myFile.txt");

   //do something with the stream

 } catch(IOException e){
   throw new WrapperException(e);
 } finally {
   try{
    input.close();
   } catch(IOException e){
      throw new WrapperException(e);
   }
 }

Now suppose that the file myFile.txt does not exist, so an FNFE(FileNotFoundException) would be
thrown from the try block. The catch blocked would catch the FNFE , wrap the exception and rethrow it.
Till now all seems well. When the call reaches the finally block, since input is null,
a call to input.close() would result in a NullPointerException(NPE) being thrown. 
Now since the finally block never catches a NPE, it would propagate up the call stack.
The WrappedException(WE) from the catch block simply disappears.

The way to avoid this would be to check whether the resource in not null in the finally block.Right, makes
complete sense, but lets take another scenario. Lets say the file myFile.txt is found but there is an
IOException(IOE) thrown due to some other reason. What happens, the try block throws IOE, which is
wrapped and rethrown. Now before the exception propagates up the call stack, the finally block is executed,
if the call to input.close() fails, a new IOE would be thrown, but the original exception would still be lost.
Damn Cute, aint it.

Iterating over Map's

A lot of times, i have come across the following code for iterating over a Map

Map values=new HashMap();
Setkeys=values.keySet();
for(Integer key:keys){
String val=values.get(key);
}
A better way is
Map values=new HashMap();
Setkeys=values.keySet();
for(Map.Entryentry:values.entrySet()){
String val=entry.getValue();
}
It is better to get a reference to Map.Entry and then iterate instead of getting all the keys and making the Map object do the work of fetching the value each time

N Queen Problem

This would be a good problem to solve. Its been a long time since i tried something like this.

The N Queen Problem is a generalized form of the 8 queen problem. In the 8 Queen problem, we have to place 8 queens on a chess board so that none of the queens is in check from any other queen(The queen should not be in the same row, column or diagonal). The N Queen problem would involve generalizing this to a n X n board with n queens.

Identifying Patterns and creating Higher Order Functions

A higher order function is a function which takes functions as parameters or returns a function. As an example, let us consider the following

1) Sum of all integers between two integers a and b
def sumInts(a:Int,b:Int):Int ={
if (a>b)
0
else
a+sumInts(a+1,b)
}

2) Sum of square of all integers between two integers a and b

def square(x:Int) :Int=x*x

def sumSqaure(a:Int,b:Int):Int ={
If(a>b)
0
else
square(a) +sumSquare(a+1,b)
}

3) A function to square all the powers 2^n where n betweentwo integers a and b

def powerOfTwo(x:Int):Int={
if(x==0)
1
else
2*powerOfTwo(x-1)
}

def sumPowerOfTwo(a:Int,b:Int):Int ={
if(a>b)
0
else
powerOfTwo(a) + sumPowerOfTwo(a+1,b)
}

These functions are all instances of {Summation from a to b} for different values of f . We can factor out the common pattern by defining a function sum

def sum(f: Int => Int, a: Int, b: Int): Int ={
if (a > b)
0
else
f(a) + sum(f, a + 1, b)
}


Using sum, we can formulate the three summing functions as follows.

def sumInts(a: Int, b: Int): Int ={
sum(id, a, b)
}

def sumSquares(a: Int, b: Int): Int ={
sum(square, a, b)
}

def sumPowerOfTwo(a: Int, b: Int): Int = {
sum(powerOfTwo, a, b)
}

where
def id(x: Int): Int = x

def square(x: Int): Int = x * x

def powerOfTwo(x: Int): Int = {
if (x == 0)
1
else
2 * powerOfTwo(x-1)
}

Tail Recursion

Consider the following 2 recursive functions

def gcd(a:Int,b:Int):Int ={
if(b==0)
b
else
gcd(b,a%b)


def factorial(n:Int):Int={
if(n==0)
1
else
n *factorial(n-1)


There is an important difference between the two rewrite sequences: The terms in the rewrite sequence of gcd have the same form repeatedly. As evaluation proceeds, their size is bounded by a constant.

By contrast, in the evaluation of factorial we get longer and longer chains of operands which are then multiplied in the last part of the evaluation sequence.

In the implementation of gcd, one notes that the recursive call to gcd is the last action performed in the evaluation of its body. One also says that gcd is tail-recursive.

The final call in a tail-recursive function can be implemented by a jump back to the
beginning of that function. The arguments of that call can overwrite the parameters
of the current instantiation of gcd, so that no new stack space is needed. Hence,
tail recursive functions are iterative processes, which can be executed in constant
space.
By contrast, the recursive call in factorial is followed by a multiplication. Hence,
a new stack frame is allocated for the recursive instance of factorial, and is deallocated
after that instance has finished. The given formulation of the factorial function
is not tail-recursive; it needs space proportional to its input parameter for its
execution.
More generally, if the last action of a function is a call to another (possibly the same)
function, only a single stack frame is needed for both functions. Such calls are called
tail calls. In principle, tail calls can always re-use the stack frame of the calling
function.

Scala vs Java : Implementing quicksort -- not optimized

Below is an implementation of a quicksort the java way

void sort(int[] xs) {
 sort(xs, 0, xs.length -1 );
}
void sort(int[] xs, int l, int r) {
 int pivot = xs[(l+r)/2];
 int a = l; int b = r;
 while (a <= b)
   while (xs[a] < pivot) { a = a + 1; }
   while (xs[b] > pivot) { b = b – 1; }
   if (a <= b) {
     swap(xs, a, b);
     a = a + 1;
     b = b – 1;
   }
 }
 if (l < b) sort(xs, l, b);
 if (b < r) sort(xs, a, r);
}
void swap(int[] arr, int i, int j) {
 int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
Quicksort the scala way ... looks neater and is easier to understand

object QuickSort {
 def sort(xs:Array[Int]):Array[Int]={
    if(xs.length<1)xs
                  else{
                    val pivot=xs(xs.length/2)
                    Array.concat(
                        sort(xs filter (pivot >)),
                          xs filter (pivot ==),
                        sort(xs filter (pivot <)))
                  }
       }
}