Coins

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

 /**  
  * numberOfWays(25, 3) = numberOfWays(25-1, 0) + numberOfWays(25-5, 1)  
  * + numberOfWays (25-10, 2) + numberOfWays (25-25, 3)  
  *   
  * numberOfWays(25-1, 0) = 1  
  * numberOfWays(25-5, 1) = numberOfWays(20, 1) = numberOfWays(20-1, 0)   
  * + numberOfWays(20-5, 1)   
  * ......   
  * @author zsunm  
  *  
  */  
 public class Coin {  
        
      private static final int[] COINS = {1, 5, 10, 25};  
        
      public static int numberOfWays(int n){  
           if (n == 0) return 0;  
           return numberOfWays(n, 3);  
      }  
        
      /**  
       * The number of ways to represent n cents by using the coins  
       * up to the specified coinIndex of the COINS array  
       * Example 1: numberOfWays(10, 2) means the number of ways  
       * to represent 10 cents using 1 cent, 5 cents, and 10 cents,   
       * because COINTS[2] = 10  
       *   
       * Example 2: numberOfWays(25, 3) means the number of ways  
       * to represent 25 cents using 1 cent, 5 cents, 10 cents, and 25 cents   
       * because COINTS[3] = 25  
       *   
       * @param n cents  
       * @param coinIndex the coin index of COINS array that can be used up to  
       * @return  
       */  
      private static int numberOfWays(int n, int coinIndex) {  
           if (n < 0){  
                return 0;  
           }  
           if (n == 0){  
                return 1;  
           }  
           int result = 0;  
           for (int i=0; i<=coinIndex; i++){  
                result += numberOfWays(n-COINS[i], i);  
           }  
           return result;  
      }  
   
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           System.out.println(numberOfWays(25));  
      }  
   
 }  

Solve Eight Queens problem with 1D array

The following program prints out all solutions for N Queens problem. 

There are 92 solutions for 8 Queens.

 The solution uses a 1D array and does not use recursion.

 public class EightQueen {  
   
      private static final int N = 8;  
      //queens[2]=3, means the queen on row 2 is placed on column 3
      private static int[] queens = new int[N];  
      private static int index = 0;  
      private static int counter = 0;  
        
      public static void placeQueens(){  
           int previousColumn = -1;  
           boolean noMoreSolutions = false;  
           while (!noMoreSolutions){  
                while (index < N){  
                     int col = getColumnForNextRow(previousColumn);  
                     if (col != -1){  
                          queens[index++] = col;  
                          previousColumn = -1;  
                     }else if (index > 0){  
                          previousColumn = queens[--index];  
                     }else{  
                          noMoreSolutions = true;  
                          System.out.println("No More Solutions");  
                          break;  
                     }  
                }  
                if (!noMoreSolutions){  
                     print();  
                     System.out.println("Solution #"+ ++counter);  
                     //Let's find another solution  
                     previousColumn = queens[--index];  
                }  
           }  
      }  
        
      private static int getColumnForNextRow(int previousColumn) {  
           int startCol = previousColumn + 1;  
           for (int j=startCol; j < N; j++){  
                if (!canAttackExistingQueens(j)){  
                     return j;  
                }  
           }  
           return -1;  
      }  
        
      private static boolean canAttackExistingQueens(int col) {  
           for (int i=0; i<index; i++){  
                if (canAttackQueen(index, col, i, queens[i])){  
                     return true;  
                }  
           }  
           return false;  
      }  
   
      private static boolean canAttackQueen(int row1, int col1, int row2, int col2) {  
           return sameCol(col1, col2) || sameDiagonal(row1, col1, row2, col2);  
      }  
   
      private static boolean sameCol(int col1, int col2) {  
           return col1 == col2;  
      }  
   
      private static boolean sameDiagonal(int row1, int col1, int row2, int col2) {  
           return col1 - col2 == row1 - row2 || col1 - col2 == row2 - row1;  
      }  
        
      private static void print(){  
           for (int i=0; i<N; i++){  
                for (int j=0; j<N; j++){  
                     if (queens[i] == j){  
                          System.out.print("Q ");  
                     }else{  
                          System.out.print("* ");  
                     }  
                }  
                System.out.println();  
           }       
      }  
   
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           placeQueens();  
      }  
 }  

Don't use HibernateTemplate.setMaxResults()

Say you have an EmployeeDao class and write a method to return the top N salary employees.

You implement it with HibernateTemplate.setMaxResults().

     public List<Employee> findTopSalaryEmployees(int maxResults) {  
         HibernateTemplate ht = getHibernateTemplate();  
         ht.setMaxResults(maxResults);  
         return ht.find("from Employee e order by e.salary desc");  
     }  

Then you need to write a second method to return all employees.

     public List<Employee> findAllEmployees(){  
         return getHibernateTemplate().find("from Employee e");  
     }  

When you test them separately, they are working fine. However, when they are tested together, a problem might occur.  You may find the findAllEmployees() only returns part of the employees.

Why?

Because the HibernateTemplate object is shared across different methods and when the max results variable is set, it doesn't get reset at the end of the method.

One of the solutions is to reset it to 0 at the end of the method. But I don't like this solution because developers can easily forget to do so.

I would suggest using HibernateCallback:

     public List<Employee> findTopSalaryEmployees(final int maxResults) {  
         List<Employee> list = getHibernateTemplate().execute(  
             new HibernateCallback<List<Employee>>() {  
                 @Override  
                 public List<Employee> doInHibernate(Session session)  
                         throws HibernateException, SQLException {  
                     Query query = session.createQuery("from Employee e order by e.salary desc");  
                     query.setMaxResults(maxResults);  
                     return query.list();  
                 }  
             });  
         return list;  
     }  

It is indeed a bit longer than the previous solution, but you don't need to reset the max result value to 0 at the end of the method.

Left shift <<, Right shift >> and Unsigned right shift >>>

The left shift operator, <<, shifts all of the bits in a value to the left a specified number of times. For each shift left, the high-order bit is shifted out (and lost), and a zero is brought in on the right.

For example,

int value = -49;
System.out.println(Integer.toBinaryString(value));
System.out.println(Integer.toBinaryString(value << 1));
System.out.println(Integer.toBinaryString(value << 8));
System.out.println(Integer.toBinaryString(value << 31));
System.out.println(Integer.toBinaryString(value << 32));

Result is:

11111111111111111111111111001111
11111111111111111111111110011110
11111111111111111100111100000000
10000000000000000000000000000000
11111111111111111111111111001111

It is interesting to note that when you left shift a value 32 bits, the result is not 0 as you may have expected. It turns out the shift distance is calculated mod 32. So value << 32 is exactly the same as value << 0 (do nothing).

What about left shift a negative value?

System.out.println(Integer.toBinaryString(value << -1));
System.out.println(Integer.toBinaryString(value << -24));

Result is:

10000000000000000000000000000000
11111111111111111100111100000000

You can see value << -1 is exactly the same as value << 31, value << -24 is exactly the same as value << 8.

The right shift operator, >>, shifts all of the bits in a value to the right a specified number of times. For each right left, the low-order bit is shifted out (and lost), and a zero is brought in on the left if the top bit is 0 (positive number), a one is brought in on the left if the top bit is 1(negative number).

int value = -49;
System.out.println(Integer.toBinaryString(value));
System.out.println(Integer.toBinaryString(value >> 1));
System.out.println(Integer.toBinaryString(value >> 8));
System.out.println(Integer.toBinaryString(value >> 31));
System.out.println(Integer.toBinaryString(value >> 32));
value = 49;
System.out.println(Integer.toBinaryString(value));
System.out.println(Integer.toBinaryString(value >> 1));
System.out.println(Integer.toBinaryString(value >> 8));
System.out.println(Integer.toBinaryString(value >> 31));
System.out.println(Integer.toBinaryString(value >> 32));

Result is:

11111111111111111111111111001111
11111111111111111111111111100111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111001111
110001
11000
0
0
110001

When the shift distance is 32, just like left shift operation, it has no effect. When the shift distance is negative, the behavior is similar to that of left shift operation --- e.g. value >> -1 is the same as value >> 31.

The unsigned right shift operator, >>>, shifts all of the bits in a value to the right a specified number of times. For each right left, the low-order bit is shifted out (and lost), and a zero is always brought in on the left regardless the top bit is 0 (positive number) or 1 (negative number).

int value = -49;
System.out.println(Integer.toBinaryString(value));
System.out.println(Integer.toBinaryString(value >>> 1));
System.out.println(Integer.toBinaryString(value >>> 8));
System.out.println(Integer.toBinaryString(value >>> 31));
System.out.println(Integer.toBinaryString(value >>> 32));
value = 49;
System.out.println(Integer.toBinaryString(value));
System.out.println(Integer.toBinaryString(value >>> 1));
System.out.println(Integer.toBinaryString(value >>> 8));
System.out.println(Integer.toBinaryString(value >>> 31));
System.out.println(Integer.toBinaryString(value >>> 32));

Result is:

11111111111111111111111111001111
1111111111111111111111111100111
111111111111111111111111
1
11111111111111111111111111001111
110001
11000
0
0
110001

Puzzle 6: Multicast

int i = -1;
byte b = (byte)i;
char c = (char)b;
int i2 = (int)c;

The value of the variable in binary format is:

i = 1111 1111 1111 1111 1111 1111 1111 1111
b = 1111 1111
c = 1111 1111 1111 1111
i2 = 0000 0000 0000 0000 1111 1111 1111 1111

So we can see, from char to int, the sign is not considered. Simply prefixing 0s will do it.

If you wish to keep the sign, you need to cast char to short

short s = (short)c;
int i3 = (int)s;

result is:

s = 1111 1111 1111 1111
i3 = 1111 1111 1111 1111 1111 1111 1111 1111

If you cast byte to char, and you don't want to keep the sign. e.g. you want to achieve the following effect.

b = 1111 1111
c = 0000 0000 1111 1111

You can use bit mask:

char c = (char)(b & 0xff);

b & 0xff is of type int, so effectively

b & 0xff = 0000 0000 0000 0000 0000 0000 1111 1111

Puzzle 5: What does it mean by Hex and Octal literals are negative if their high-order bit is set?

In the book, "Java Puzzle", Puzzle 5: The Joy of Hex, there is a bold line Hex and Octal literals are negative if their high-order bit is set to explain the number 0xcafebabe is equivalent to the decimal value -889275714.

So what does "high-order bit is set" mean?

"high-order bit" is the left most bit of a given type. For example, if type is integer, which has 32 bits, then the high-order bit is the 32nd bit counting from right to left.

The 32nd bit counting from right to left is 0 in the following case, so the number is a positive number

int max = Integer.valueOf("01111111111111111111111111111111", 2);
System.out.println(max);

The result is

2147483647

which happens to be the maximum integer number.

Now let's convert the Hex format number 0xcafebabe to binary format

String s = Integer.toBinaryString(0xcafebabe);

The result is

11001010111111101011101010111110

The high-order bit is 1, therefore, it is a negative number.

Request, Flash, View Scope in Spring webflow

What is the difference among these 3 scopes?

According to the Java doc:

Request: Attributes placed in request scope exist for the life of the current request into the flow execution. When the request ends any attributes in request scope go out of scope.

Flash: Attributes placed in flash scope exist through the life of the current request and until the next view rendering. After the view renders, flash scope is cleared. Flash scope is typically used to store messages that should be preserved until after the next view renders.

View: Attributes placed in view scope exist through the life of the current view state and until the view state exits in a subsequent request. View scope is typically used to store view model objects manipulated over a series of Ajax requests.

I don't think I can see their distinction clearly from the definitions above. So I am going to run some experiments to find out myself.

In the spring-web-flow.xml, I create a <view-state>.

<view-state id="dummy">
    <on-entry>
        <set name="viewScope.viewScopeAttribute" value="'v'" />
        <set name="flashScope.flashScopeAttribute" value="'f'" />
        <set name="requestScope.requestScopeAttribute" value="'r'" />
    </on-entry>
</view-state>

the dummy.xhtml JSF page is very simple:

request scope: #{requestScopeAttribute}
flash scope: #{flashScopeAttribute}
view scope: #{viewScopeAttribute}

I was expecting to see all 3 attributes displayed, but the request scope attribute is missing.

Let's change the <view-state> to

<view-state id="dummy">
    <on-render>
        <set name="viewScope.viewScopeAttribute" value="'v'" />
        <set name="flashScope.flashScopeAttribute" value="'f'" />
        <set name="requestScope.requestScopeAttribute" value="'r'" />
    </on-render>
</view-state>

All 3 attributes display this time. why?

This is because every time Spring webflow needs to render a view, it will issue a redirect causing the view to be rendered in the subsequent GET request. This is useful because when the user hit Refresh or Back button, the browser won't give any warning.

The actions in <on-entry> occur during the first request and any attributes in this request's scope will have been blown off by the time the view is rendered. Because the view is rendered in the second request.

The actions in <on-render> occur during the second request, so the attributes in this request's scope will be kept when the view is rendered.

As for the difference between viewScope and flashScope, I really cannot tell any as long as they are in <view-state>.  I think they can be used interchangeably in <view-state>. (I could be very wrong here).

However, viewScope cannot be used in <action-state> or <decision-state>.

flashScope will retain in memory until after the view is rendered. For example:

<action-state id="dummy0">
    <on-entry>
        <set name="flashScope.flashScopeAttribute" value="'f'" />
    </on-entry>
    <evaluate expression="new java.lang.String()" />
    <transition to="dummy"/>
</action-state>
 
<view-state id="dummy" /> 

The flash scope attribute still displays on the page.