On teh way

This time, we will solve a common problem – matrix transposition. Description and simple solution Give matrix of n*n , return the transposed matrix. We can come up with the simple solution from the definition of matrix transposition: for x < n for y < x swap( a [x,y], a [y,x]) Different problem It’s so easy, right? Now we move another similar problem: how to efficient transpose a very large matrix(n*n) on the tape? They are similar, both want to transpose a matrix. They are also very different for the data source affect how we can retrieve data effectively. When we have to read data from tape, element can’t be randomly accessed any more. Upper solution works, but too slow. int n = 200 ; // I use LinkedList to simulate the tape LinkedList<Integer> matrix; // init code long start = System.nanoTime(); for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) { final int origin = i * n + j; fin...

I was asked some confusing point about generic during my interview, so I review the generic after it. Following is some note. Basic use First, we write our simple container: public class Container<T> { private T[] a; private T get ( int i) { return a[i]; } private void set ( int i, T t) { a[i] = t; } } In our example, generic only work like some place holder which can be replaced by Integer or String or Object. bounded type parameter Now, we move to more complex usage. We add one more method to our container: addAll to add all element from other Collection. public void simpleAddAll (Collection<T> c) { for (T t : c) { list.add(t); } } This works, but somewhat limited. We can only add the same type element into our container rather than like what standard library can do. Learning from the jdk source, we can change our method into: public <E extends T> void addAll (Collect...

Origin When I optimize a mysql pagination interface , I want ot use Redis cache to store some result to speed it up. In order to estimate how much memory I will spend, I have to do some memory estimation. Solution This solution comes from this stackoverflow question . Steps Write the following source: package memory; import java.lang.instrument.Instrumentation; public class ObjectSizeFetcher { private static Instrumentation instrumentation; public static void premain (String args, Instrumentation inst) { instrumentation = inst; } public static long getObjectSize (Object o) { return instrumentation.getObjectSize(o); } } Add the following line to your MANIFEST.MF : Premain-Class: memory.ObjectSizeFetcher Use getObjectSize: package memory; public class C { private int x; private int y; public static void main (String [] args) { System. out .println( ObjectSizeFetc...

First we checkout the definition of problem: the longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings. For example, given ‘abcda’ and ‘bcdabc’, we should give ‘bcda’. First trial – brute force For this problem, we can easily come up with the brute force solution which compare substrings with same length like following: max = 0 for i of s1[ 0 , n] for j of s2[ 0 , m] for l of [ 0 , min (n-i, m-j)] if is_same(s1[i, i+l], s2[j, j+l]) compare with max then set max else break This works, but is also slow – with time complexity O(n * m * min(n, m)^2) . Or we make a little optimization by just comparing last char so we can achieve it with O(n * m * min(n, m)) . max = 0 for i of s1[ 0 , n] for j of s2[ 0 , m] for l of [ 0 , min (n-i, m-j)] if is_same(s1[i+l], s2[j+l]) ...

leetcode problem: Trapping Rain Water Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. common problem analysis method Inspired by this Chinese blog , I list some generalized rules to solve a problem and help us thinking. I will try to use those rules to analyze this problem. generalize condition: abstraction can let us skim the detail of problem and focus on main obstacle. More than that, abstraction can also help us draw conclusion/common solution from this kind of problems make condition more accurate: use some special case to inspire us how to solve it induce from result: the result may contains some more conditions to help us similar problem: the solution, the process to solve a similar problem may provide us some clues to solve this one adjust the conditions of problem( delete a condition, add a cond...