Monthly Archives: August 2015

Springbatch cursor reader

Spingbatch default cursor reader reads data readily. It has below advantages over jdbctemplate:
1. Traditional jdbctemplate reader reads data in one time, which makes wait for a very long time. But cursor reader reads steadily, we don’t need to wait.
2. Jdbctemplate reads in one time, and put everything in memory. But cursor reader can avoid this problem by reading item one by one.

Serialize, deserialize tree

Given a tree structure, serialize it, and deserialize it. One of the way to do it, is to store the number of children in the serializing. Take below tree as an example:

The serializing result will be:

The red ones are the number of children information. And use queue to implement it.

Check my code on github.

Pickup coin/gold

Problem description: Number of coins lined up, two persons take turn to pick up coins from both ends, what is the maximum total sum of money first person can pick?

This post is to response to junmin‘s code. This one is a good one for dp. I wrote it in recursive way before. The formula for this problem is below:
DP(i,j) = Max(
*     Min(DP(i,j-2), DP(i+1,j-1))+coins[j],
*     Min(DP(i+2,j), DP(i+1,j-1))+coins[i])

This time, I tried with a less time complexity O(n^2). Key idea for this is to use a 2-d array to memorize sub-solution. For example, 2-d array memo[i][j] saves the max value between gold[i], gold[i+1], … gold[j]. Take [1, 2, 3, 1] for example, the memo[][] array and the calculation sequence will be like below:

Check my code on github: GetMaxGold