Monthly Archives: April 2016

Integer Break

https://leetcode.com/problems/integer-break/

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Solution. This is a classical dp problem.

For n, split n to left and right part. So, left part has i, right part has n – i. Then we calculate leftMax and rightMax:
leftMax = max(i, dp[i])
rightMax = max(n – i, dp[n – i])

so, dp[n] = max(leftMax * rightMax)

check my code on github: java, python

Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Solution. This problem is the same as deepIterator. Each time, we store the iterator of the list in stack. But in my previous deepIterator, I didn’t handle when a list is empty.

For this problem, I use currInteger to tell if iterator has next.

The main part is the refresh() function. It iterates until it finds an element is Integer. When current iterator doesn’t has next or list is totally empty, it pops the stop. When current element is a list, it pushes to stack.

private void refresh() {
    currInteger = null;
    while (!s.isEmpty()) {
        if (!s.peek().hasNext()) {  // iterator is empty. Another situation could be that iterator for the list is empty at all
            s.pop();
            continue;
        }
        NestedInteger curr = s.peek().next();
        if (curr.isInteger()) {
            currInteger = curr.getInteger();
            return;
        }
        // comes to here, it means it is a list
        s.push(curr.getList().iterator());
    }
}

Check my code on github: link

Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Solution. This is another good one for bit manipulation.

First of all, any negative number should return false.

2nd, we can use num & (-num) to test if binary form only has one 1. In another word, to see if num is power of 2.

In the end, because power of four only has 1 in odd position:
1
100
10000
1000000
To test if 1 exists at odd position, we need to use num & 0x55555555

The final answer is return (num & (num 1)) == 0 && (num & 0x55555555) != 0;

Check my code on github: link

Read file name when using MultiResourceItemReader in Springbatch

Springbatch provides MultiResourceItemReader to allow us to read all files in a folder:

<bean id="filenameReader" class=" org.springframework.batch.item.file.MultiResourceItemReader">
    <property name="resources" value="file:SpringBatchReadFilename/tmp/*.csv" />
    <property name="delegate" ref="filenameFlatReader" />
</bean>

However, there maybe some cases that we want. Assume we have below 2 files and we want to output the filename in processor or writer.

20160402.csv
id,value
4,d

20160403.csv
id,value
1,a
2,b
3,c

How do we do that? My friend Yidong Du provides an brilliant solution: write a self-defined FlatFileItemReader and overwrite setResource(), doReader() methods. In each doReader set the filename in entity:

@Data
public class FilenameItemReader extends FlatFileItemReader<FilenameEntity> {

    private Resource myresource;

    @Override
    public void setResource(Resource var1) {
        super.setResource(var1);
        myresource = var1;
    }

    @Override
    protected FilenameEntity doRead() throws Exception {
        FilenameEntity filenameEntity = super.doRead();
        if (filenameEntity == null) {
            return null;
        }
        filenameEntity.setFileName(myresource.getFile().getName());
        return filenameEntity;
    }

}

In writer, it writes the entities with fileName:
FilenameEntity(id=4, value=d, fileName=20160402.csv)
FilenameEntity(id=1, value=a, fileName=20160403.csv)
FilenameEntity(id=2, value=b, fileName=20160403.csv)
FilenameEntity(id=3, value=c, fileName=20160403.csv)

Check my code on github: link

log4j output to different log files

Normally when we load a logger in Java, we do like below:

private static Logger logger = LoggerFactory.getLogger(App.class);

Or

private Logger logger3 = LoggerFactory.getLogger(getClass());

Logger like this will by default load the root logger.

Alternatively, we can define our own logger. And we can add appender to self-defined logger. In this way, we can output to different log files by using different logger.

Below is an example.

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE log4j:configuration SYSTEM "log4j.dtd">
<log4j:configuration debug="true">

       <appender name="console" class="org.apache.log4j.ConsoleAppender">
              <layout class="org.apache.log4j.PatternLayout">
                     <param name="ConversionPattern"
                            value="%d{yyyy-MM-dd HH:mm:ss} %-5p %c{1}:%L - %m%n" />
              </layout>
       </appender>

       <appender name="file" class="org.apache.log4j.RollingFileAppender">
              <param name="append" value="true" />
              <param name="maxFileSize" value="1MB" />
              <param name="maxBackupIndex" value="10" />
              <param name="file" value="test.log" />
              <layout class="org.apache.log4j.PatternLayout">
                     <param name="ConversionPattern"
                            value="%d{yyyy-MM-dd HH:mm:ss} %-5p %c{1}:%L - %m%n" />
              </layout>
       </appender>

       <appender name="myFile" class="org.apache.log4j.RollingFileAppender">
              <param name="append" value="true" />
              <param name="maxFileSize" value="1MB" />
              <param name="maxBackupIndex" value="10" />
              <param name="file" value="test2.log" />
              <layout class="org.apache.log4j.PatternLayout">
                     <param name="ConversionPattern" value="%d{yyyy-MM-dd HH:mm:ss} %-5p %c{1}:%L - %m%n" />
              </layout>
       </appender>

       <!--A self defined logger. It is used to output into a separate file. By default, additivity is true.
       If additivity=true, sub logger will append to root logger.
       If additivity=false, sub logger won't append to root logger.
       -->
       <logger name="logger2" additivity="true">
              <level value="INFO" />
              <appender-ref ref="myFile" />
       </logger>

       <root>
              <level value="DEBUG" />
              <appender-ref ref="console" />
              <appender-ref ref="file" />
       </root>

</log4j:configuration>

App.java

public class App {

    private static Logger logger = LoggerFactory.getLogger(App.class);
    private static Logger logger2 = LoggerFactory.getLogger("logger2");

    public static void main(String[] args) {
        logger.info("information");
        logger.warn("warning");
        logger.error("error");
        logger2.info("self-defined logger");
    }
}

Root logger output to test.log with “information”, “warning” and “error”, logger2 output to test2.log with “self-defined logger.
Another thing we should notice is additivity=”true” parameter in logger. If it is set true, all the sub logger will also be output by root logger. If it is set as false, it won’t show in root logger.
Check my code on github: link

Number of 1 Bits

https://leetcode.com/problems/number-of-1-bits/

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

Solution: My initial formula uses n = n & ~(n & (-n)). But there is a better one: n = n & (n – 1).

So we have java code like below:

public int hammingWeight(int n) {
    int ans = 0;
    while (n != 0) {
        n = n & (n - 1);
        ans++;
    }
    return ans;
}

This problem gives condition that it is an unsigned integer. If it is an negative number, neither in Java nor Python, it won’t show up 0 by shifting right.

Define bean in SpringMVC

Today, I tested from scratch to see how to use bean in SpringMVC. The conclusion is that we can either use @Component or xml to define bean.

First, I used Intellij to create a HelloWorld SpringMVC project. Then I added a TestClass bean which I hope to get it from container. The project structure is like below:
springmvcprojectstructure2

TestClass.java

@Data
@Component
public class TestClass {
    private String msg = "bean by component";
}

HelloController.java. We should pay attention to TestClass. It has AutoWired annotation, which means it is injected from bean. So in order to do this, we need to find way to generate TestClass bean. Keep looking below other files.

@Controller
@RequestMapping("/")
public class HelloController {

   @Autowired
   private TestClass t;

   @RequestMapping(method = RequestMethod.GET)
   public String printWelcome(ModelMap model) {
      model.addAttribute("message", "Hello world!" + t.getMsg());
      return "hello";
   }
}

hello.jsp

<html>
<body>
   <h1>${message}</h1>
</body>
</html>

mvc-dispatcher-servlet.xml. A servlet configuration. It scan all the components in base-package. In this way, the class which annotated with component will be added into container. In this way, the @AutoWired annotated TestClass can be injected.

<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xmlns:context="http://www.springframework.org/schema/context"
       xsi:schemaLocation="http://www.springframework.org/schema/beans
        http://www.springframework.org/schema/beans/spring-beans.xsd
        http://www.springframework.org/schema/context http://www.springframework.org/schema/context/spring-context.xsd">

    <context:component-scan base-package="com.pli.project.springmvc"/>

    <bean class="org.springframework.web.servlet.view.InternalResourceViewResolver">
        <property name="prefix" value="/WEB-INF/pages/"/>
        <property name="suffix" value=".jsp"/>
    </bean>

</beans>

web.xml. This is the entry for the servlet. The definition says all url will be forwarded to mvc-dispatcher. In this way, mvc-dispatcher-servlet.xml will be responsible for all requests.

<web-app version="2.4"
   xmlns="http://java.sun.com/xml/ns/j2ee" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
   xsi:schemaLocation="http://java.sun.com/xml/ns/j2ee 
   http://java.sun.com/xml/ns/j2ee/web-app_2_4.xsd">

   <display-name>Spring MVC Application</display-name>

    <servlet>
      <servlet-name>mvc-dispatcher</servlet-name>
      <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
        <load-on-startup>1</load-on-startup>
   </servlet>

   <servlet-mapping>
      <servlet-name>mvc-dispatcher</servlet-name>
      <url-pattern>/</url-pattern>
   </servlet-mapping>
</web-app>

By here, it is done. When we launch jboss and test the webpage, we see below:
springmvcbycomponent

Pay attention to mvc-dispatcher-servlet.xml file. We see that this one is actually a xml file, it defines beans. In this way, we come up another way for beans. We put the bean definition in mvc-dispatcher-servlet.xml file, like below:

<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xmlns:context="http://www.springframework.org/schema/context"
       xsi:schemaLocation="http://www.springframework.org/schema/beans
        http://www.springframework.org/schema/beans/spring-beans.xsd
        http://www.springframework.org/schema/context http://www.springframework.org/schema/context/spring-context.xsd">

    <context:component-scan base-package="com.pli.project.springmvc"/>

    <bean class="org.springframework.web.servlet.view.InternalResourceViewResolver">
        <property name="prefix" value="/WEB-INF/pages/"/>
        <property name="suffix" value=".jsp"/>
    </bean>

    <bean id="testClass" class="com.pli.project.springmvc.domain.TestClass">
        <property name="msg" value="Bean by xml" />
    </bean>

</beans>

This is more comfortable way which we used a lot in Spring project. Accordingly, I can remove the @Component annotation from TestClass:

@Data
public class TestClass {
    private String msg;
}

After we run launch jboss, we see result like below:
springmvcbyxml

This post summaries 2 ways to define beans in SpringMVC. Hope it helps.

Check my code on github the 2 cases: Bean by component annotationBean by Xml

Nested List Weight Sum

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]], return 10. (four 1’s at depth 2, one 2 at depth 1)

Example 2:
Given the list [1,[4,[6]]], return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 42 + 63 = 27)

Solution. This can be easily solved by recursion. For each list, if is a number, add to ans[]. If not, call recursion on it.

Java solution:

public int weightedSum(List list) {
    return weightedSumHelper(list, 1);
}

public int weightedSumHelper(List<Object> list, int depth) {
    int ans = 0;
    for (Object l : list) {
        if (l instanceof List) {
            ans += weightedSumHelper((List)l, depth + 1);
        }
        else {
            int num = (Integer)l;
            ans += depth * num;
        }
    }
    return ans;
}

Python solution:

def weightedSum(self, list):
    ans = [0]
    self.weightedSumHelper(l, 1, ans)
    return ans[0]

def weightedSumHelper(self, l, depth, ans):
    for ele in l:
        if isinstance(ele, list):
            self.weightedSumHelper(ele, depth + 1, ans)
        else:
            ans[0] += ele * depth

Mybatis is way slower than running query in Oracle.

Today, when I tried a query in mybatis. It is super slow. After an hour investigation, I found the root reason is that we should use #{username} instead of ${value}. Accordingly, we should use map as the type.

<select id="getChgoffDt" resultType="java.util.Date" parameterType="map">
SELECT acc_chgoff_dt FROM daybreak.accounts WHERE acc_nbr = #{accNbr}
</select>>