HackerRank: Jim and the Skyscrapers

还是用ordered stack。非递增stack。

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        Stack<Integer> stack = new Stack<Integer>();
        long res = 0;
        for (int i = 0; i < size; i++) {
            int cur = sc.nextInt();
            if (!stack.isEmpty() && stack.peek() < cur) {
                int tmp = stack.pop();
                long dupCount = 1;
                while (!stack.isEmpty() && stack.peek() < cur) {
                    int top = stack.pop();
                    if (top == tmp) {
                        dupCount++;
                    } else {
                        //update possible routes
                        res += dupCount * (dupCount - 1);
                        tmp = top;
                        dupCount = 1;
                    }
                }
                res += dupCount * (dupCount - 1);
            }
            stack.push(cur);
        }
        while (!stack.isEmpty()) {
            int tmp = stack.pop();
            long dupCount = 1;
            while (!stack.isEmpty() && stack.peek() == tmp) {
                dupCount++;
                stack.pop();
            } 
            res += dupCount * (dupCount - 1);
        }
        System.out.println(res);
    }

Effective Java 学习笔记 — Chapter 10. Concurrency

Item 66. Synchronize access to shared mutable data
(1) 用 synchronized 关键字可以保证
1.1 其他的thread不会看到inconsistent 状态的变量, 即mutual exclusion
1.2 每个thread都会看到变量的最新状态,这一点非常重要,即communication purpose
(2) Java中,除了long和double意外的变量进行读写操作都是atomic的。
但是,atomic并不能保证 a value written by one thread will be visible to another,因此对于atomic的操作有时也是需要synchronized。例如一下例子中虽然主线程会将stopRequested设为true,但是并没有保证新线程什么时候会看到这个变化,再加上虚拟机的代码优化可能导致死循环。

// Broken! - How long would you expect this program to run?
   public class StopThread {
       private static boolean stopRequested;
       public static void main(String[] args)
               throws InterruptedException {
           Thread backgroundThread = new Thread(new Runnable() {
               public void run() {
                   int i = 0;
                   while (!stopRequested)
i++; }
           });
           backgroundThread.start();
           TimeUnit.SECONDS.sleep(1);
           stopRequested = true;
       }
}

应该加上synchronized关键字:

// Properly synchronized cooperative thread termination
public class StopThread {
    private static boolean stopRequested;
    private static synchronized void requestStop() {
       stopRequested = true;
       }
    private static synchronized boolean stopRequested() {
       return stopRequested;
    }
    public static void main(String[] args) throws InterruptedException {
       Thread backgroundThread = new Thread(new Runnable() {
           public void run() {
               int i = 0;
               while (!stopRequested())
                   i++; 
           }
       });
       backgroundThread.start();
       TimeUnit.SECONDS.sleep(1);
       requestStop(); 
    }
}

(3) “synchronization has no effect unless both read and write operations are synchronised.”
(4) volatile关键字不能起到mutual exclusive作用,但是在上例中可以起到communication作用,即让每个thread看到这个变量的最新状态。

private static volatile boolean stopRequested;

由于volative不能起到mutual exclusive作用,一下代码会出错,解决办法是用synchronized代替volatile

// Broken - requires synchronization!
private static volatile int nextSerialNumber = 0;
   public static int generateSerialNumber() {
       return nextSerialNumber++;
}

Item 67. Avoid excessive synchronization
(1) Inside a synchronized region, do not invoke a method that is designed to be overridden, or one provided by a client in the form of a function object.否则有可能导致死锁等问题。
(2) As a rule, you should do as little work as possible inside synchronized regions.
(3) 过度使用synchronization会导致performance下降。在现代计算机中,性能下降主要并不是体现在等待锁上,而是失去了很多parallelism和代码优化机会。

Item 68. Prefer executors and tasks to threads
Executors.newCachedThreadPool,新提交的task不会被queue,而是新建一个thread来执行,如果server load已经很重会make things worse。但是优点是不用复杂的configuration。
Executors.newFixedThreadPool,只新建特定数量的thread来处理queue中的tasks。

Item 69. Prefer concurrency utilities to wait and notify
(1)尽量使用JAVA中concurrency下的库,例如ConcurrentHashMap,而不是用Collections.synchronizedMap 或者 Hashtable。
最常用的synchronizers包括CountDownLatch和Semaphore。
(2)如果要用wait,一定要套用以下代码:Always use the wait loop idiom to invoke the wait method; never invoke it outside of a loop。

synchronized (obj) {
   while (<condition does not hold>)
       obj.wait(); // (Releases lock, and reacquires on wakeup)
   ... // Perform action appropriate to condition
}

(3)尽量使用notifyAll来代替notify,因为notifyAll并不会导致程序运行错误(等待的线程即使被notify也会再次检查condition)

Item 70. Document thread safety

Item 71. Use lazy initialization judiciously
如果能够不用lazy initialisation就尽量不用

Item 72. Don’t depend on the thread scheduler

Item 73. Avoid thread groups

Lintcode: Fast Power

Calculate the an % b where a, b and n are all 32bit integers.


运算法则:(a * b) % p = (a % p * b % p) % p,注意会溢出

class Solution {
    public int fastPower(int a, int b, int n) {
        return (int)sub(a, b, n);
    }
    private long sub(int a, int b, int n) {
        if (n == 0) {
            return 1 % b;
        } else if (n == 1) {
            return a % b;
        }
        long pre = fastPower(a, b, n/2); 
        return (pre * pre) % b * (n % 2 != 0 ? a % b : 1) % b;
    }
};

Lintcode: Rehashing

The size of the hash table is not determinate at the very beginning. If the total size of keys is too large (e.g. size >= capacity / 10), we should double the size of the hash table and rehash every keys. Say you have a hash table looks like below:

size=3, capacity=4
[null, 21->9->null, 14->null, null]
The hash function is:
int hashcode(int key, int capacity) {
return key % capacity;
}

here we have three numbers, 9, 14 and 21, where 21 and 9 share the same position as they all have the same hashcode 1 (21 % 4 = 9 % 4 = 1). We store them in the hash table by linked list.
rehashing this hash table, double the capacity, you will get:

size=3, capacity=8
index: 0 1 2 3 4 5 6 7
hash table: [null, 9, null, null, null, 21, 14, null]

Given the original hash table, return the new hash table after rehashing .


对于正数或者负数取模都可以用的办法:(a % b + b) % b

public class Solution {  
    public ListNode[] rehashing(ListNode[] hashTable) {
        if (hashTable == null || hashTable.length == 0) {
            return hashTable;
        }
        int preSize = hashTable.length;
        ListNode[] res = new ListNode[preSize*2];
        ListNode[] tail = new ListNode[preSize*2];
        for (int i = 0; i < preSize; i++) {
            ListNode cur = hashTable[i];
            while (cur != null) {
            	ListNode copy = new ListNode(cur.val);
            	hashTable[i] = cur.next;
                int curVal = (cur.val%(preSize*2) + preSize*2) % (preSize*2);
                if (res[curVal] == null) {
                    res[curVal] = copy;
                    tail[curVal] = copy;
                } else {
                    tail[curVal].next = copy;
                    tail[curVal] = copy;
                }
                cur = cur.next;
            }
        }
        return res;
    }
};

Lintcode: Topological order

Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A–>B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.
Find any topological order for the given graph.


非常典型的DFS,在visit完当前点的所有子节点后再把自己加到结果中去。最后reverse就是结果。很有助于加深理解DFS.

public class Solution {
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        ArrayList<DirectedGraphNode> res = new ArrayList<DirectedGraphNode>();
        if (graph == null || graph.size() == 0) {
            return res;
        }
        List<DirectedGraphNode> noLink = new ArrayList<DirectedGraphNode>();
        noLink.addAll(graph);
        Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>();
        for (DirectedGraphNode node : graph) {
            if (!visited.contains(node)) {
                visited.add(node);
                for (DirectedGraphNode neighbor : node.neighbors) {
                    noLink.remove(neighbor);
                }
            }
        }
        Stack<DirectedGraphNode> stack = new Stack<DirectedGraphNode>();
        visited.clear();
        while (!noLink.isEmpty()) {
            stack.push(noLink.remove(0));
            visit(res, stack, visited);
        }
        Collections.reverse(res);
        return res;
    }
	
    private void visit(ArrayList<DirectedGraphNode> res, Stack<DirectedGraphNode> stack,  Set<DirectedGraphNode> visited) {
	DirectedGraphNode node = stack.pop();
	visited.add(node);
	for (DirectedGraphNode neighbor : node.neighbors) {
		if (!visited.contains(neighbor)) {
			stack.push(neighbor);
			visit(res, stack, visited);
		}
	}
	res.add(node);
    }
}

Longest Increasing Subsequence

Given a sequence of integers, find the longest increasing subsequence (LIS).
You code should return the length of the LIS.

Example
For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4


虽然思路不难,但是store[i]的更新很容易写错

public class Solution {
    public int longestIncreasingSubsequence(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] store = new int[nums.length];
        store[0] = 1;
        int res = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] <= nums[i]){
                    store[i] = Math.max(store[j], store[i]);
                }
            }
            store[i]++;
            res = Math.max(res, store[i]);
        }
        return res;
    }
}

Lintcode: delete digits

Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer. Make this new positive integers as small as possible.
N <= 240 and k <=N,


Solution 1: DP 但是数字太大会溢出,另外复杂度也太高

public String DeleteDigits(String A, int k) {
        if (A == null || A.length() <= k) {
        	return "";
        }
        int[][] store = new int[A.length()][k+1];
        for (int i = 0; i < A.length(); i++) {
        	for (int j = 0; j <= k; j++) {
        		if (j == 0) {
        			store[i][j] = Integer.parseInt(A.substring(0, i+1));
        		} else if (i < j) {
        			store[i][j] = 0;
        		} else {
        			int withCur = store[i-1][j] * 10 + Integer.parseInt(A.substring(i, i+1));
        			store[i][j] = Math.min(store[i-1][j-1], withCur);
        		}
        	}
        }
        return String.valueOf(store[A.length()-1][k]);
    }

Solution 2: 类似于next permutation的做法, greedy, 用stack

public String DeleteDigits(String A, int k) {
    if (A == null || A.length() <= k) {
        return "";
    }
    Stack<Integer> stack = new Stack<Integer>();
    int deleted = 0;
    for (int i =0; i< A.length(); i++) {
	int cur = A.charAt(i) - '0';
	while (!stack.isEmpty() && stack.peek() > cur && deleted < k) {
		deleted++;
		stack.pop();
	}
	stack.push(cur);
    }
    while (deleted < k) {
	deleted++;
	stack.pop();
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
	sb.insert(0,  stack.pop());
    }
    while (sb.length() > 0 && sb.charAt(0) == '0') {
	sb.deleteCharAt(0);
    }
    return sb.toString();
}

Java 设计模式

1. Decorator
在一个object上加上一些额外的功能,即进行功能扩展。“allows behavior to be added to an individual object, either statically or dynamically, without affecting the behavior of other objects from the same class”.
定义一个interface或者abstract class,例如Java 中的InputStream,再定义很多个实体类,例如FileInputStream, BufferedInputStream, GzipInputStream, ObjectInputStream,每个类的构造函数都有一个类型为InputStream的参数。因此调用的时候可以多次嵌套decorator:

ObjectInputStream res = new ObjectInputStream(new BufferedInputStream(new FileInputStream("abc.txt")));

2. Adaptor
An adapter helps two incompatible interfaces to work together.
例如,System.in 是 InputStream 的一个静态变量,读取byte stream, 而BufferedReader 的参数是character stream.为了让它们兼容,定义了一个InputStreamReader (和BufferedReader一样都继承自Reader),参数为InputStream即可。

Java: Clone, String, intern(),garbage collection(GC),程序初始化

1. Clone, String, intern()
http://blog.csdn.net/stypace/article/details/41441509
String:
intern()函数会返回这个string在常量池(constant pool)中的引用

2. Garbage collection
There are two approaches to perform GC,第二种办法比较常用:
(1) reference counting,当指向一个object的reference数为0的时候,就说明可以回收了。这种办法的难点是很难保证counter的精确性。另外很重要的一点,如果两个object互相为reference,它们都不会被回收。
(2) tracing collectors,通过一系列的名为“GC Roots”的对象作为起始点,从这些节点开始向下搜索,搜索所走过的路径称为引用链(Reference Chain),当一个对象到GC Roots没有任何引用链相连(用图论的话来说就是从GC Roots到这个对象不可达)时,则证明此对象是不可用的。

Tracing collectors 有几种算法:
2.1 Copying collectors:将heap分成两部分,每次都只用其中一个部分,GC的时候将这个部分的alive的object一起复制到另外一个部分,然后将这个部分清空。优点:没有碎片,缺点:每次复制的过程整个application都被lock住了,另外,比较浪费空间。
2.2 Mark-and-sweep collectors:大部分的商业JVM都用这种办法。将整个heap扫描一遍,标记所有可以被回收的地址,存到一个list里。之后如果需要空间来放新object,通过这个list找到对应可用的地址。优点:缺点:其一,效率比较低,因为sweep的时间是dependent on heap size, 其二,会有碎片,减少碎片的方法之一是allocate memory的时候根据object大小找到大小最接近的chunck来存放。

(3) Generational garbage collection, 根据object的存活周期将heap分为几个部分。存活周期指的时the number of GC cycles that the object has survived。通常只有两个区域。GC的时候,young generation区域里还存活着的对象会被移至old generation区。有时候特别大的object会被直接allocate到old generation区域,因为copy这些对象的cost太高。young区GC的频率比old区高。

3. 重要!!!程序初始化顺序,参考 java面试之程序初始化
父类–静态变量/父类–静态初始化块(注意没有静态方法)
子类–静态变量/子类–静态初始化块(注意没有静态方法)
main方法
父类–变量/父类–初始化块
父类–构造器
子类–初始化块/子类–变量
子类–构造器

4. finally执行顺序
http://blog.csdn.net/stypace/article/details/42102181

Java: final 关键字

摘自java面试之Final、finally、finalize区别

try语句在返回前,将其他所有的操作执行完,保留好要返回的值,而后转入执行finally中的语句,而后分为以下三种情况:

情况一:如果finally中有return语句,则会将try中的return语句”覆盖“掉,直接执行finally中的return语句,得到返回值,这样便无法得到try之前保留好的返回值。

情况二:如果finally中没有return语句,也没有改变要返回值,则执行完finally中的语句后,会接着执行try中的return语句,返回之前保留的值。

情况三:如果finally中没有return语句,但是改变了要返回的值,这里有点类似与引用传递和值传递的区别,分以下两种情况,:

如果return的数据是基本数据类型,则在finally中对该基本数据的改变不起作用,try中的return语句依然会返回进入finally块之前保留的值。
如果return的数据是引用数据类型,而在finally中对该引用数据类型的属性值的改变起作用,try中的return语句返回的就是在finally中改变后的该属性的值。