Key preserved table

What does mean by key preserved table?

According to its definition: A table is key-preserved if every key of the table can also be a key of the result of the join. So, a key-preserved table has its keys preserved through a join.

Let's illustrate this by an example.

 
create table a (a_id number primary key);
create table b (b_id number primary key, a_id number,
  foreign key (a_id) REFERENCES a(a_id) on delete cascade);

create or replace view c as (
  select a.a_id, b.b_id from a,b where a.a_id = b.a_id
)

insert into a values (1);
insert into b values (2,1);
insert into b values (3,1);

select * from c;

The result is

 
A_ID B_ID
---------
1    2
1    3

Clearly A's primary key A_ID cannot be used as a primary key in the view, so table A is not a key preserved table. On the other hand, table B's primary key B_ID can be used as a primary key in the view, so table B is a key preserved table for this view C.

So what happens when you

 
delete from c;

is all the rows in table B are deleted.

Rules for updating a join view

http://docs.oracle.com/cd/E11882_01/server.112/e25494/views.htm#ADMIN11782

What does EntityManager.clear() do?

It clears L1 cache. 

See an example

 
@Transactional
public void test(){
   Book book = bookDao.findById(1);
   System.out.println("Old Author: "+book.getAuthor());
   bookDao.updateBookAuthor(1, "New author");
   book = bookDao.findById(1);
   System.out.println("New Author: "+book.getAuthor());
}

The output is
Old Author: Old Author
New Author: Old Author

Line 1, JPA loads the Book entity from database and saves it into L1 cache.
Line 3 is a JPQL bulk update statement:

update Book b set b.author = :author where b.id = :id

It changes the entity's author and stores it into L2 cache, while the entity at L1 cache is unchanged.

Line 4, JPA loads the entity from L1 cache and therefore still shows the old author value.

Now check the changes that the clear() method brings.

@Transactional
public void test(){
   Book book = bookDao.findById(1);
   System.out.println("Old Author: "+book.getAuthor());
   bookDao.updateBookAuthor(1, "New author");
   entityManager.clear();
   book = bookDao.findById(1);
   System.out.println("New Author: "+book.getAuthor());
}

The output is
Old Author: Old Author
New Author: New Author

EntityManager.clear() clears the L1 cache so that at line 5, JPA has to load the entity from L2 cache.

So the clear() method doesn't clear any changes made to the entity. Namely, all the changes will still be committed to database. It does nothing more than just clearing the L1 cache. 

Find Nth to last element in a singly linked list

Use recursion

 public class FindNthToLast {  
        
      public static void main(String[] args){  
           LinkedListNode node 
              = LinkedListNode.createLinkedList(new int[]{1,2,3,4,5,6,7,8,9});  
           LinkedListNode.print(node);  
           System.out.println("\n=====================");  
           LinkedListNode found = find(node, 2);  
           System.out.println(found.data);  
      }  
        
      private static int count = 0;  
        
      public static LinkedListNode find(LinkedListNode head, int n){  
           if (head == null){  
                return null;  
           }  
           LinkedListNode found = find(head.next, n);  
           count++;  
           if (count==n){  
                return head;  
           }  
           return found;  
      }  
 }  

 public class LinkedListNode {  
      public int data;  
      public LinkedListNode next;  
        
      public LinkedListNode(int data) {  
           super();  
           this.data = data;  
      }  
        
      public static void print(LinkedListNode head){  
           LinkedListNode current = head;  
           while (current != null){  
                System.out.print(current.data+" ");  
                current = current.next;  
           }  
      }  
        
      public static LinkedListNode createLinkedList(int[] arr){  
           LinkedListNode head = new LinkedListNode(arr[0]);  
           LinkedListNode current = head;  
           for (int i=1; i<arr.length; i++){  
                LinkedListNode temp = new LinkedListNode(arr[i]);  
                current.next = temp;  
                current = temp;  
           }  
           return head;  
      }  
 }  

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