Posts

A cheatsheet that gets you started. The original tutorial can be found here Main function The normal version: object Hello { def main(args: Array[String]) = { println("Hello, world") } } The version that extends App trait object Hello extends App { println("Hello, world") } // To access args. object Hello extends App { if (args.size == 0) println("Hello, you") else println("Hello, " + args(0)) } As you may notice: no ; needed as ending in Scala. Variables The type in declaration is optional. val s: String = "hello" // val for immutable, final in Java. val s = "hello" // Same as above. var i: Int = 42 // var for mutable. var i = 42 // Same as above. Built-in types: val b: Byte = 1 // 8-bit signed [-128, 127](-2^7 to 2^7-1, inclusive) val s: Short = 1 // 16-bit signed. val x: Int = 1 // 32-bit signed. val l: Long = 1 // 64-bit signed. val f: Float = 3.0 // 32-bit IEEE 754 single-precision float. val d: Double = 2.0 // 64-bit IEEE 754 double-precision float. val c: Char = 'a' // 16-bit unsigned Unicode character. val s: String = "str" // A sequence of Char BigInt and BigDecimal for large numbers: ...

一个场景 当内存无法加载全部数据时，如何从包含未知大小的数据流中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。 水塘抽样 把上述问题具体化为给定一个未知大小数组data[]，从中选取k个数，要求每个数被选中的概率相等。假设数组长度为n，则每个数被选中概率应为k/n。 ...

A quick review of Java Collection and Map key methods. Array based collections usually have: Method Time complexity add O(1) insert(int index) O(N) remove O(1) remove(int index) O(N) find(Object value) O(N) PriorityQueue, TreeSet and TreeMap are implemented based on balanced tree, thus: Method Time complexity offer O(logN) poll O(logN) peek O(1) Overview via a diagram Collections extends Iterable which has below key methods: Method Description boolean hasNext() This method returns true if the iterator has more elements. object next() It returns the element and moves the cursor pointer to the next element. void remove() This method removes the last elements returned by the iterator. List methods Method Description void add​(int index, E element) Inserts the specified element at the specified position in this list (optional operation). boolean add​(E e) Appends the specified element to the end of this list (optional operation). boolean addAll​(Collection<? extends E> c) Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection’s iterator (optional operation). Eget​(int index) Returns the element at the specified position in this list. E set​(int index, E element) Replaces the element at the specified position in this list with the specified element (optional operation). booleanisEmpty() Returns true if this list contains no elements. int size() Returns the number of elements in this list. <T> T[] toArray​(T[] a) Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array. E.g., String[] y = x.toArray(new String[0]); Queue methods Method Description void add(E e) Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available. E element() Retrieves, but does not remove, the head of this queue. boolean offer​(E e) Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. E peek() Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty. E poll() Retrieves and removes the head of this queue, or returns null if this queue is empty. E remove() Retrieves and removes the head of this queue. Dequeue / LinkedList Methods Method Description void addFirst​(E e) Inserts the specified element at the front of this deque if it is possible to do so immediately without violating capacity restrictions, throwing an IllegalStateException if no space is currently available. void addLast​(E e) Inserts the specified element at the end of this deque if it is possible to do so immediately without violating capacity restrictions, throwing an IllegalStateException if no space is currently available. boolean offerFirst​(E e) Inserts the specified element at the front of this deque unless it would violate capacity restrictions. boolean offerLast​(E e) Inserts the specified element at the end of this deque unless it would violate capacity restrictions. E peekFirst() Retrieves, but does not remove, the first element of this deque, or returns null if this deque is empty. E peekLast() Retrieves, but does not remove, the last element of this deque, or returns null if this deque is empty. E pollFirst() Retrieves and removes the first element of this deque, or returns null if this deque is empty. E pollLast() Retrieves and removes the last element of this deque, or returns null if this deque is empty. E pop() Pops an element from the stack represented by this deque. void push​(E e) Pushes an element onto the stack represented by this deque (in other words, at the head of this deque) if it is possible to do so immediately without violating capacity restrictions, throwing an IllegalStateException if no space is currently available. E removeFirst() Retrieves and removes the first element of this deque.` E removeLast() Retrieves and removes the last element of this deque. Summary of Deque methods First Element (Head) Last Element (Tail) Throws exception Special value Throws exception Special value Insert addFirst(e) offerFirst(e) addLast(e) offerLast(e) Remove removeFirst() pollFirst() removeLast() pollLast() Examine getFirst() peekFirst() getLast() peekLast() Comparison of Queue and Deque methods Queue Method Equivalent Deque Method add(e) addLast(e) offer(e) offerLast(e) remove() removeFirst() poll() pollFirst() element() getFirst() peek() peekFirst() Comparison of Stack and Deque methods Stack Method Equivalent Deque Method push(e) addFirst(e) pop() removeFirst() peek() getFirst() Method Description boolean add​(E e) Adds the specified element to this set if it is not already present. TreeSet methods Method Description boolean add​(E e) E ceiling​(E e) Returns the least element in this set greater than or equal to the given element, or null if there is no such element. E first() Returns the first (lowest) element currently in this set. E floor​(E e) Returns the greatest element in this set less than or equal to the given element, or null if there is no such element. SortedSet headSet​(E toElement) Returns a view of the portion of this set whose elements are strictly less than toElement. NavigableSet headSet​(E toElement, boolean inclusive) Returns a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement. E higher​(E e) Returns the least element in this set strictly greater than the given element, or null if there is no such element. E last() Returns the last (highest) element currently in this set. E lower​(E e) Returns the greatest element in this set strictly less than the given element, or null if there is no such element. E pollFirst() Retrieves and removes the first (lowest) element, or returns null if this set is empty. E pollLast() Retrieves and removes the last (highest) element, or returns null if this set is empty. NavigableSet subSet​(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) Returns a view of the portion of this set whose elements range from fromElement to toElement. SortedSet subSet​(E fromElement, E toElement) Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive. SortedSet tailSet​(E fromElement) Returns a view of the portion of this set whose elements are greater than or equal to fromElement. NavigableSet tailSet​(E fromElement, boolean inclusive) Returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement. Map methods Method Description V get​(Object key) Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key. V put​(K key, V value) Associates the specified value with the specified key in this map (optional operation). boolean containsKey​(Object key) Returns true if this map contains a mapping for the specified key. boolean containsValue​(Object value) Returns true if this map maps one or more keys to the specified value. Set<Map.Entry<K,​V» entrySet() Returns a Set view of the mappings contained in this map. Set keySet() Returns a Set view of the keys contained in this map. Collection values() Returns a Collection view of the values contained in this map. Default methods: ...

懒更新(lazy update) 上文留下一个问题没有解决，就是对一个区间更新。对一个元素的更新复杂度为O(N),N为数组长度,按上文方法对区间更新，则复杂度为L*O(N), L为区间长度。 另外，更新原数组元素，是从线段树中对应的叶子节点，一路向上更新到根节点。如果所要更新的区间有很多公共祖先节点，那么这些节点每次都需要被更新一次。如图中如果我们要更新数组中的2, 8, 6分别+5, +1, +9，可以看到图中公共节点如19会更新2次，37则有3次。 ...

何为线段树 线段树是基于要研究的数组而构建的数据结构，呈二叉树状。线段树的叶子结点就是所要研究的数组，非叶子节点表示数组的一段区间的某个性质的值。比如此区间的和，或者最大值最小值等等。 ...

何为BIT BIT是一种数据结构，名为树其实用数组即可表达。其主要作用是给定了一个数组(或多维数组)，BIT可用来： O(logN)的复杂度计算给定范围的和,也就是求sum(low, high) O(logN)的复杂度更新数组的一个元素 其构造方法巧妙但简单，可谓大道至简。 ...

归并排序基于分治思想，基本步骤是把数组一分为二，分别排序，然后将两个排序好的数组合并，合并两个排序好的数组可以在O(N)的复杂度完成。根据T(N) = 2T(2/N) + N,可以推导出时间复杂度为O(NlogN)。代码如下： ...

What’s Union Find? Union Find is useful in finding connected components. The idea behind UF is quite simple. You have N items initially. Each item forms its own group by setting parent to pointing to itself, i.e., parents[i] = i. Then you can union two items if they are connected or share some common properties in your problem definition. E.g., union(1,3) will connect item 1 and 3 and make their parents both pointing to the same item. You can continue union(x, y) and put more items into one group. A very common implementation of Disjoint Set Union. Here I applied two optimization: path compression and union by rank. The idea is to flatten the tree when find(x) is called so as to reduce the time complexity, which is O(logN) now. In reality, the amortized time complexity is a very small constant. Refer to wiki for more detailed discussion. ...

此一年波谲云诡，世事多艰，终于今宵。纵困苦艰难，江河依旧辽阔。新年至，昂首向前，爆竹声中，品人间烟火。 庚子弥年多诡谲，今岁今日终今宵。 寒随一夜冬雪去，暖入春风催竹梢。 稚齿犹恋除夕夜，三更欲等雄鸡叫。 家别万里相思浓，一柱清香扫尘嚣。 ...

书接前文，pm升到partner level后，打算再接再厉，把clubhouse推向全宇宙。 之前一个房间参考微信设置只能容纳500人，pm说500人太少了，应该能容纳5亿人。 ...