鲸落的博客

Brain-dumping.

Stack in Java

Stack作为一个LIFO (Last-In-First-Out)是非常重要的数据结构,Java中从最初版本就有了Stack类,但是该类由于是继承自Vector,在Java Collections发布后就被废弃了。

Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class. When a deque is used as a stack, elements are pushed and popped from the beginning of the deque.

Top K Algorithms

背景

去年面试Facebook时,被问到了一道Top K的问题,这类的问题解法往往具有共通性。今天在LeetCode上又遇到了一道类似的问题,于是网上搜了一下解题思路,摘录留下备用。

JDK里有一个强大的集合类 – PriorityQueue,掌握了它的用法便能迎刃而解这类问题。

值得注意的是PriorityQueue没有继承自List,不具有随机访问第i个元素的方法。

1
E get(int index);

Given a non-empty array of integers, return the k most frequent elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Pair {
    int num;
    int count;

    Pair(int num, int count) {
        this.num=num;
        this.count=count;
    }
}

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        //count the frequency for each element
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int num: nums){
            if (map.containsKey(num)) {
                map.put(num, map.get(num)+1);
            } else {
                map.put(num, 1);
            }
        }

        // create a min heap
        PriorityQueue<Pair> queue = new PriorityQueue<>(new Comparator<Pair>() {
            public int compare(Pair a, Pair b) {
                return a.count - b.count;
            }
        });

        //maintain a heap of size k.
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            Pair p = new Pair(entry.getKey(), entry.getValue());
            queue.offer(p);
            if(queue.size() > k) {
                queue.poll();
            }
        }

        //get all elements from the heap
        List<Integer> result = new ArrayList<Integer>();
        while(queue.size() > 0) {
            result.add(queue.poll().num);
        }
        //reverse the order
        Collections.reverse(result);

        return result;
    }
}

Java Concurrency

为何要同步线程?

Since all threads run in the same address space, they all have access to the same data and variables. If two threads simultaneously attempt to update a global counter variable, it is possible for their operations to interleave in such way that the global state is not correctly modified. Although such a case may only arise only one time out of thousands, a concurrent program needs to coordinate the activities of multiple threads using something more reliable that just depending on the fact that such interference is rare.

Executor: An object that executes submitted Runnable tasks.
ExecutorService: A more extensive interface.
ThreadPoolExecutor: Provides an extensible thread pool implementation.
Executors: Provides convenient factory methods for these Executors.

AbstractExecutorService: Provides default implementations of ExecutorService execution methods.
ScheduledExecutorService: An ExecutorService that can schedule commands to run after a given delay, or to execute periodically.

ExecutorService的生命周期

  • Active
  • Shutting Down
  • Shutdown

Synchronizers (synchronization aids)

  • CyclicBarrier循环屏障: A synchronization aid that allows a set of threads to all wait for each other to reach a common barrier point.
  • Phaser
  • CountDownLatch: 当counter为1时为被用作start signal,为N时为complete signal。
  • Exchanger
  • Semaphore
  • SynchronousQueue

Potential threading problems

  • Deadlock
  • Starvation
  • Livelock
  • Race conditions

Concurrent Collections