2018年12月18日 星期二

[FWD] Stevey's Blog Rants: Get that job at Google

http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

Quote:
You just happened to squeak by. Because of the inherently flawed nature of the interviewing process, it's highly likely that someone on the loop will be unimpressed with you, even if you are Alan Turing. Especially if you're Alan Turing, in fact, since it means you obviously don't know C++.

2018年9月28日 星期五

[Java] Doubly Linked List

Reference: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

The time complexity of remove() method of java.util.LinkedList is O(n) because Java standard LinkedList class does not expose the internal Node details for clients.

Therefore, we implement a custom DoublyLinkedList class for competitive programming. In this implementation, both time complexity of add() and of remove() are O(1).
    
    public class DoublyLinkedList<V> {
        private int size;
        private Node<V> head;
        private Node<V> tail;

        public DoublyLinkedList() {
            this.size = 0;
            this.head = new Node<V>();
            this.tail = new Node<V>();
            this.head.next = this.tail;
            this.tail.prev = this.head;
        }
        
        public void addFirst(Node<V> node) {
            this.size++;
            node.next = this.head.next;
            node.next.prev = node;
            node.prev = this.head;
            node.prev.next = node;
        }
        
        public void addLast(Node<V> node) {
            this.size++;
            node.prev = this.tail.prev;
            node.prev.next = node;
            node.next = this.tail;
            node.next.prev = node;
        }
        
        public void remove(Node<V> node) {
            if (node.prev != null && node.next != null) {
                this.size--;
                node.next.prev = node.prev;
                node.prev.next = node.next;
                node.prev = node.next = null;
            }
        }
        
        public Node<V> getFirst() {
            return isEmpty() ? null : this.head.next;
        }

        public Node<V> getLast() {
            return isEmpty() ? null : this.tail.prev;
        }
        
        public int size() {
            return this.size;    
        }
        
        public boolean isEmpty() {
            return this.size == 0;
        }
        
        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            Node<V> curr = this.head.next;
            while (curr != this.tail) {
                builder.append(curr.getValue());
                builder.append(" -> ");
                curr = curr.next;
            }
            builder.append("END \n");
            return builder.toString();
        }
    }

    public class Node<V> {
        private V value;
        private Node prev;
        private Node next;

        public Node(V value) {
            this.value = value;
        }

        public Node() {
            this.value = null;
        }
        
        public V getValue() {
            return this.value;
        }
        
        @Override
        public String toString() {
            return this.value == null ? null : this.value.toString();
        }
    }

[Java] Map Implementations

Documents: https://docs.oracle.com/javase/tutorial/collections/implementations/map.html


General-Purpose Map Implementations:
  • HashMap
  • TreeMap
  • LinkedHashMap

Special-Purpose Map Implementations:
  • EnumMap
  • WeakHashMap
  • IdentityHashMap

Concurrent Map Implementations:
  • The java.util.concurrent package contains the ConcurrentMap interface, which extends Map with atomic putIfAbsent, remove, and replace methods, and the ConcurrentHashMap implementation of that interface.


Example: [LeetCode] 146. LRU Cache

public class LRUCache {
    private int capacity;
    private Map<Integer, Node> cache;
    private DoublyLinkedList doublyLinkedList;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.doublyLinkedList = new DoublyLinkedList();
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        doublyLinkedList.moveToTail(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            doublyLinkedList.moveToTail(node);
            node.value = value;
            return;
        }

        if (cache.size() == capacity) {
            cache.remove(doublyLinkedList.first().key);
            doublyLinkedList.remove(doublyLinkedList.first());
        }

        Node insert = new Node(key, value);
        cache.put(key, insert);
        doublyLinkedList.addToTail(insert);
    }
    
    public static class DoublyLinkedList {
        private Node head;
        private Node tail;

        public DoublyLinkedList() {
            this.head = new Node();
            this.tail = new Node();
            this.head.next = this.tail;
            this.tail.prev = this.head;
        }
        
        public Node first() {
            return head.next;
        }
        
        public void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        public void addToTail(Node node) {
            node.prev = tail.prev;
            tail.prev = node;
            node.prev.next = node;
            node.next = tail;
        }
        
        public void moveToTail(Node node) {
            remove(node);
            addToTail(node);
        }
    }
    
    public static class Node {
        public int key;
        public int value;
        public Node prev;
        public Node next;
        
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
        
        public Node() {
            this.key = -1;
            this.value = -1;
        }
    }
}



Example: [LeetCode] 460. LFU Cache
class LFUCache {
    private int capacity;
    private HashMap<Integer, Integer> valueHash;
    private Node head;
    private HashMap<Integer, Node> nodeHash;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.valueHash = new HashMap<>();
        this.nodeHash = new HashMap<>();
    }
    
    public int get(int key) {
        if (valueHash.containsKey(key)) {
            increaseFrequency(key);
            return valueHash.get(key);
        } else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (!valueHash.containsKey(key)) {
            if (valueHash.size() == capacity) {
                removeOldestKey();
            }
            addToHead(key);
        }
        valueHash.put(key, value);    
        increaseFrequency(key);
    }
    
    private void addToHead(int key) {
        if (head == null) {
            head = new Node(0);
        } else if (head.frequency > 0) {
            Node node = new Node(0);
            node.next = head;
            head.prev = node;
            head = node;
        }
        head.bucket.add(key);
        nodeHash.put(key, head);      
    }
    
    private void increaseFrequency(int key) {
        Node node = nodeHash.get(key);
        node.bucket.remove(key);
        
        if (node.next == null) {
            node.next = new Node(node.frequency + 1);
            node.next.prev = node;
        } else if (node.next.frequency > node.frequency + 1) {
            Node middle = new Node(node.frequency + 1);
            middle.prev = node;
            middle.next = node.next;
            node.next.prev = middle;
            node.next = middle;
        }
        node.next.bucket.add(key);
        nodeHash.put(key, node.next);
        if (node.bucket.isEmpty()) {
            removeNode(node);
        }
    }
    
    private void removeOldestKey() {
        if (head == null) { 
            return;
        }
        int oldestKey = getOldestKey();
        head.bucket.remove(oldestKey);
        if (head.bucket.isEmpty()) {
            removeNode(head);   
        }
        nodeHash.remove(oldestKey);
        valueHash.remove(oldestKey);
    }
    
    private int getOldestKey() {
        for (int n : head.bucket) {
            return n;
        }
        return 0;
    }
    
    private void removeNode(Node node) {
        if (node.prev == null) {
            head = node.next;
        } else {
            node.prev.next = node.next;
        } 
        if (node.next != null) {
            node.next.prev = node.prev;
        }        
    }
    
    public static class Node {
        public int frequency;
        public LinkedHashSet<Integer> bucket;
        public Node prev;
        public Node next;
        
        public Node(int frequency) {
            this.frequency = frequency;
            this.bucket = new LinkedHashSet<>();
        }
    }
}

[Java] Set Implementations

Documents: https://docs.oracle.com/javase/tutorial/collections/implementations/set.html


There are three general-purpose Set implementations:
  • HashSet
    • No ordering guarantees.
  • TreeSet
    • Implements SortedSet interface
  • LinkedHashSet
    • Differs from HashSet in that it maintains a doubly-linked list running through all of its entries. 
    • This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order).

There are two special-purpose Set implementations:
  • EnumSet
  • CopyOnWriteArraySet

[FWD] Solving the 2x2x2 Rubik's Cube

Document: http://lghttp.38568.nexcesscdn.net/8013252/pdf/uploads/general_content/Rubiks_Cube_2x2x2_solving_guide.pdf


Comments:
  • Step 1: Solving the first layer (white) as 3x3x3.
  • Step 2: Orienting the yellow face.
    • There are only seven possible cases.
      • Left Soon algorithm: L' U' L U' L' U2 L
      • Right Soon algorithm: R U R' U R U2 R'
  • Step 3: Permuting the second layer.
    • x R' U R' D2 R U' R' D2 R2 x'

2018年9月18日 星期二

[HackerRank] Practice Interview Preparation Kit: Dynamic Programming


Link: https://www.hackerrank.com/interview/interview-preparation-kit/dynamic-programming/challenges



1. Max Array Sum: https://www.hackerrank.com/challenges/max-array-sum/problem

Solution: Naive dynamic programming. Time = O(n), Space = O(1).
  • Define 
    • f(i): max subarray sum from 1 to i which contains the last element.
    • g(i): max subarray sum from 1 to i which does not contain the last element.
  • Answer = max(f(n), g(n)).
  • Recursive formula:
    • f(i) = g(i - 1) + a[i]
    • g(i) = max(f(i - 1), g(i - 1)).

#!/bin/python3

import math
import os
import sys

# Complete the maxSubsetSum function below.
def maxSubsetSum(arr):
    best_w_last, best_wo_last = 0, 0
    for a in arr:
        best_w_last, best_wo_last = best_wo_last + a, max(best_w_last, best_wo_last)
    return max(best_w_last, best_wo_last)
        
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input())
    arr = list(map(int, input().rstrip().split()))
    res = maxSubsetSum(arr)
    fptr.write(str(res) + '\n')
    fptr.close()



2. Candies: https://www.hackerrank.com/challenges/candies/problem

Solution: Two pass greedy algorithm. Time = O(n), Space = O(n).

#!/bin/python3

import math
import os
import sys

# Complete the candies function below.
def candies(n, r):
    c = [1 for i in range(n)]
    for i in range(1, n):
        if r[i] > r[i - 1]:
            c[i] += c[i - 1];
    for i in range(n - 2, -1, -1):
        if r[i] > r[i + 1]:
            c[i] = max(c[i + 1] + 1, c[i])
    return sum(c)    

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input())
    arr = []
    for _ in range(n):
        arr_item = int(input())
        arr.append(arr_item)
    result = candies(n, arr)
    fptr.write(str(result) + '\n')
    fptr.close()



3. Abbreviation: https://www.hackerrank.com/challenges/abbr/problem



4. Decibinary Numbers: https://www.hackerrank.com/challenges/decibinary-numbers/problem

2018年9月8日 星期六

[IOI 2002] Batch Scheduling


Category: DP + Convex Hull Trick

Problem statement: https://ioinformatics.org/files/ioi2002problem4.pdf

Convex Hull Trick:


[IOI 2014 Practice Contest 2] Guardians of the Lunatics


Category:
  • DP + Divide and Conquer Optimization
  • DP + Knuth Optimization

Problem statement: https://www.hackerrank.com/contests/ioi-2014-practice-contest-2/challenges/guardians-lunatics-ioi14


Solution: https://www.hackerrank.com/contests/ioi-2014-practice-contest-2/challenges/guardians-lunatics-ioi14/editorial


Knuth Optimization:
  • Paper: http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/p429-yao.pdf
  • DP formulation:
    • c[i, i] = 0
    • c[i, j] = w(i, j) + min_{i
  • Quadrangle Inequalities (QI): w(i, j) + w(i', j') ≤ w(i, j') + w(i', j) for all i ≤ i' ≤ j ≤ j'.
  • Monotone on the lattice of intervals: w(i, j') ≤ w(i', j) for all i ≤ i' ≤ j ≤ j'.
  • Theorem: QI + Monotone => Time = O(n^2).
    • Lemma 1: w(i, j) is QI + Monotone => c[i, j] is QI.
    • Lemma 2: 
      • Define c_k(i, j) = w(i, j) + c[i, k-1] + c[k, j].
      • Define K_c(i, j) = max{ k : c_k(i, j) = c[i, j] }.
      • c[i, j] is QI => K_c(i, j) ≤ K_c(i, j + 1) ≤ K_c(i + 1, j + 1).


2018年9月7日 星期五

[Dynamic Programming] Optimal binary search trees


Quote from Section 15.5 from CLRS, Introduction to Algorithms, 3rd.

Definitions:
  • \sum p_i + \sum q_j = 1.
  • E[search cost in T] = 1 + \sum depth(k_i) p_i + \sum depth(d_j) q_j.
  • e[i, j] = the expected cost of searching an optimal BST containing the keys k_i, ..., k_j.
    • When j = i - 1, e[i, j] = q_{i - 1} by definition. (When j = i - 1, there are no actual keys; we have just the dummy key d_{i - 1}.)
    • i from 1 to n + 1.
    • j from 0 to n.
  • w(i, j) = \sum_{l from i to j} p_l + \sum_{w from i - 1 to j} q_l.
    • i from 1 to n + 1.
    • j from 0 to n.
    • w[i, j] = w[i, j - 1] + p_j + q_j.
  • If k_r is the root of an optimal BST, we have
    • e[i, j] = p_r + (e[i, r - 1] + w(i, r - 1)) + (e[r + 1, j] + w(r + 1, j)).
    • e[i, j] = e[i, r - 1] + e[r +1, j] + w(i, j) 
      • since w(i, j) = w(i, r - 1) + p_r + w(r + 1, j).
  • e[i, j] =
    • q_{i - 1} if j = i - 1.
    • min_{r from i to j}{ e[i, r - 1] + e[r + 1, j] + w(i, j) }.
  • Define root[i, j] be the index r for which k_r is the root of an optimal BST containing key k_i, ..., k_j.

Naive algorithm, Time = O(n^3)
  • let e[1 .. n + 1, 0 .. n], w[1 .. n + 1, 0 .. n], and root[1 .. n, 1 .. n] be new tables
  • for i = 1 to n + 1
    • e[i, i - 1] = q_{i - 1}
    • w[i, i - 1] = q_{i - 1}
  • for l = 1 to n
    • for i = 1 to n - l + 1
      • j = i + l - 1
      • e[i, j] = infinity
      • w[i, j] = w[i, j - 1] + p_j + q_j
      • for r = i to j
        • t = e[i, r - 1] + e[r + 1, j] + w[i, j]
        • if t < e[i, j]
          • e[i, j] = t
          • root[i, j] = r
  • return e and root

Knuth Optimization, Time = O(n^2)
  • Fact: root[i, j - 1] ≤ root[i, j] ≤ root[i + 1, j].
  • Change the innermost for loop to for r = root[i, j - 1] to root[i + 1, j].

2018年8月14日 星期二

[CP] IOI'96 Day 2: Problem 1: Sorting a Three-Valued Sequence

Problem: http://olympiads.win.tue.nl/ioi/ioi96/contest/ioi96s.html


Key idea: Counting sort. Time should be O(N).


Algorithm: Time = O(N).
  1. Counting each value 1, 2, 3, i.e., Count[1], Count[2], Count[3].
    • Count[1] + Count[2] + Count[3] = N
    • Target intervals:
      • I_1 = [0, Count[1])
      • I_2 = [Count[1], Count[1] + Count[2])
      • I_3 = [Count[1] + Count[2], Count[1] + Count[2] + Count[3])
  2. Counting each value on 3 different target intervals.
    • Define Count[i][j] = # of value i in the interval I_j.
  3. Swap i and j in min(Count[i][j], Count[j][i]) times for i ≠ j.
  4. Swap the rest unsorted values.
    • Let T_ij = abs(Count[i][j] - Count[j][i]).
      • Property: T_ij = T_jk = T_ki. 
      • Let T = T_ij = T_jk = T_jk.
    • Swap 1 -> 2 -> 3 cyclically: Take 2T times. 
#include <iostream>
#include <fstream>

using namespace std;

int main() {
    ofstream fout("sort3.out");
    ifstream fin("sort3.in");

    int N;
    fin >> N;

    int values[1000] = {0};
    int value_counts[3] = {0};
    int swapping_map[3][3] = {0};
    for (int i = 0; i < N; i++) {
        fin >> values[i];
        value_counts[values[i] - 1]++;
    }

    int begin_pos = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < value_counts[i]; j++) {
            swapping_map[i][values[begin_pos + j] - 1]++;
        }
        begin_pos += value_counts[i];
    }

    int swapping_count = 0;
    swapping_count += min(swapping_map[0][1], swapping_map[1][0]); // 1 <-> 2
    swapping_count += min(swapping_map[1][2], swapping_map[2][1]); // 2 <-> 3
    swapping_count += min(swapping_map[2][0], swapping_map[0][2]); // 3 <-> 1
    swapping_count += 2 * abs(swapping_map[0][1] - swapping_map[1][0]); // 1 -> 2 -> 3
    fout << swapping_count << '\n';

    return 0;
}

2018年7月18日 星期三

[Notes] Precalculated Values

Example: [Leetcode] 357. Count Numbers with Unique Digits: https://leetcode.com/problems/count-numbers-with-unique-digits/description/


Statement: Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.

class Solution {
    private int[] precalculated = new int[] { 
        1, 10, 91, 739, 5275, 32491, 168571, 712891, 2345851, 5611771, 8877691
    };

    public int countNumbersWithUniqueDigits(int n) {
        return precalculated[Math.min(n, 10)];
    }
}

2018年7月8日 星期日

[Notes] Video Suggestion and Discovery for YouTube: Taking Random Walks Through the View Graph

Paper: https://static.googleusercontent.com/media/research.google.com/zh-TW//pubs/archive/34407.pdf


ABSTRACT:
  • Adsorption, provides a simple method to efficiently propagate preference information through a variety of graphs.

INTRODUCTION:
  • The goal is to create a personalized page of video recommendations that not only shows the latest and most popular videos, but also provides users with recommendations tailored to their viewing habits.
  • The Video Co-View Graph:
    • Video-video co-view graph
    • User-video co-view graph
    • We attempt to use the broadest definition of co-view whenever possible.

THE ADSORPTION ALGORITHM
  • The genesis of the family of algorithms that we will collectively call adsorption is the following question: assuming we wish to classify a node in a graph in terms of (class) labels present on some of the other nodes, what is a principled way to do it?
  • The idea of recommending videos commonly co-viewed with a user’s watched videos nevertheless can be meaningfully abstracted as finding labeled nodes that have multiple short paths from the user node.
  • Thus our desiderata for our recommendation system include the ideas that a video v is relevant to a user u if: 
      • u and v have a short path between them;
      • u and v have several paths between them;
      • u and v have paths that avoid high-degree nodes.
  • Three equivalent views.
  • Adsorption via Averaging
    • Each node has two roles, forwarding labels and collecting labels. 
    • In the “full-information” model, let us imagine that each node keeps track of the history of all labels it receives.
    • Formal description:
      • G = (V, E, w), where V denotes the set of vertices (nodes), E denotes the set of edges, and w : E → R denotes a nonnegative weight function on the edges. 
      • Let L denote a set of labels, and assume that each node v in a subset V_L ⊆ V carries a probability distribution L_v on the label set L. 
        • We often refer to V_L as the set of labeled nodes. 
      • For the sake of exposition, we will introduce a pre-processing step, where for each vertex v ∈ V_L, we create a “shadow” vertex v~ with exactly one out-neighbor, namely v, connected via an edge (v, v~) of weight 1; furthermore, for each v ∈ V_L, we will re-locate the label distribution L_v from v to v~, leaving v with no label distribution
      • Let V~ denote the set of shadow vertices, V~ = {v~ | v ∈ V_L}. 
      • From now on, we will assume that at the beginning of the algorithm, only vertices in V~ have non-vacuous label distributions.
    • Algorithm.
  • Adsorption via Random Walks
    • For a vertex v ∈ V, denote by N_v the probability distribution on the set of neighbors of v described by N_v(u) = w(u, v)/(Σ_u w(u, v)), that is, the probability of u is proportional to the weight on the edge (u, v). 
    • The label distribution of a vertex v is simply a convex combination of the label distributions at its neighbors, that is, L_v = Σ_u N_v(u) L_u.
    • Therefore, if we pick an in-neighbor u of v at random according to N_v and sample a label according to the distribution L_u, then for each label l ∈ L, L_v(l) is precisely equal to Exp_u [L_u(l)], where the expectation arises from the process of picking a neighbor u according to N_v. 
    • Extending this to neighbors at distance 2, it is easy to see that for each label l ∈ L, L_v(l) = Exp_w Exp_u [L_w(l)], where an in-neighbor u of v is chosen according to N_v and an in-neighbor w of u is chosen according to N_u. Expanding this out, we see that L_v(l) = Σ_w Σ_u N_v(u) N_u(w) L_w(l).
    • N_v(u) is the probability of reaching u from v in one step of a random walk starting from v and picking a neighbor according to N_v, and similarly, N_u(w) is the probability of picking a neighbor w of u according to N_u. 
    • Notice also the crucial use of the Markov property (memorylessness) here, that is, conditioned on the random walk having reached u, the only information used in picking w is N_u, which depends only on u, and not on where we initiated the random walk from.
    • Algorithm.
  • Adsorption via Linear Systems
    • Doing so would give an embedding of the vertices of the graph into L_1 (since each convex combination can be written as a vector of unit L_1 norm in n dimensions, where n = |V|); this is a topic of active research in computer science.
    • The system of linear equations has a unique solution if and only if the underlying graph is connected.
    • Algorithm.
  • Injection and Dummy Probabilities
    • The probability with which we enter the absorbing state v~ might be determined as a function of various features of v. Thus, this parameter, which we call the injection probability is usually a crucial design choice in deploying a live recommendation system.
    • Instead of considering the standard random walk on an edge-weighted graph, one may consider a “hobbled walk,” where at each step, with some probability, which we call the abandonment probability or the dummy probability, the algorithm abandons the random walk without producing any output label.

EXPERIMENTAL SETUP
  • Algorithms and Variants Tested
    • The first reference algorithm is called GP, for global popularity. 
      • This algorithm first sorts all videos by their popularity during the training period. 
      • When we need recommendations for a user u, we proceed in order of this popularity measure, and output top videos that the user has not watched during the training period.
    • The second algorithm, called LP (for local popularity) takes into account the fact that what is globally popular is poorly personalized for many users. The idea behind this algorithm is another very commonly employed item-based-recommendation heuristic, and is based on co-views. 
      • For each video v, compute the list C(v) of videos z that it was co-viewed with, that is, users who watched v also watched z. 
      • Furthermore, for each video v and video z co-viewed with v, assign a score c(v, z) given by the number of users who co-viewed v and z.
      • When we need recommendations for user u, look at the set W(u) of all videos watched by u during the training period, and consider the set C(W(u)) = {z ∈ C(v) | v ∈ W(u)} of videos co-viewed with the videos watched by u. 
      • For each z ∈ C(W(u)), assign a score c(u, z) = Σ_v∈W(u) c(v, z).
      • Sort this set by total score, and output the first from this sorted list that user u has not watched already.
    • The third and final reference algorithm rectifies this: rather than define the “co-view score” c(v, z) between videos v and z to be the number of users who co-viewed v and z, we define c(v, z) by c(v, z) = |U(v)∩U(z)|/|U(v)∪U(z)|, where U(v) denotes the set of users who watched v. 
      • As before, we define c(u, z) for user u and video z to be Σ_v∈W(u) c(v, z). 
      • We call the resulting algorithm LR (for local rare).
    • Adsorption-N: At each user node, injection probability and dummy probability are 0; probability of continuing the random walk is 1. At each video node, injection probability is 1/4, dummy probability is 0, and probability of continuing the random walk is 1/2. 
    • Adsorption-D: At each user node, injection probability is 0, dummy probability is 1/4, and probability of continuing the random walk is 3/4. At each video node, injection probability is 1/4, dummy probability is 1/4, and probability of continuing the random walk is 1/2.
  • How the adsorption algorithm is used for the video recommendation problem:
    • One way to use the algorithm is to run the algorithm on the user–video view graph, and use the label distribution derived for each user as the recommendations; the labels will be the most relevant videos for that user.
    • An equivalent mechanism is one where for each user, we collect the distributions computed for each of her watched videos and take their average. 
    • Although this yields equivalent answers, it has an important benefit: we can use this procedure to make recommendation to new users (those that were not in the training set), as soon as they watch even a single video.

EMPIRICAL RESULTS
  •  Top-1 performance:
    • First, note that GP has the best performance for users who viewed just one video during the training period.
      • But it quickly degrades as the view frequency increases, becoming the worst among all the algorithms! 
      • This suggests that for very casual users (who visit a system infrequently), recommending the most popular videos is a useful strategy. 
      • However, for users with very high view frequency, the idea of the “popular but unwatched” videos is a somewhat questionable notion.
    • Algorithm Adsorption-D performs significantly better as the view frequency increases beyond 5, and the gains become much larger as the view frequency increases further.

2018年6月21日 星期四

[ProjectEuler] Problem 621: Expressing an integer as the sum of triangular numbers

Statement:
  • Gauss famously proved that every positive integer can be expressed as the sum of three triangular numbers (including 0 as the lowest triangular number). In fact most numbers can be expressed as a sum of three triangular numbers in several ways.
  • Let G(n) be the number of ways of expressing n as the sum of three triangular numbers, regarding different arrangements of the terms of the sum as distinct.
  • For example, G(9)=7, as 9 can be expressed as: 3+3+3, 0+3+6, 0+6+3, 3+0+6, 3+6+0, 6+0+3, 6+3+0.
  • You are given G(1000)=78 and G(10^6)=2106.
  • Find G(17526 × 10^9).


Proof of Integer is Sum of Three Triangular Numbers:

2018年6月15日 星期五

Google Phone Interview


Before:
  • Fail on Amazon Phone Interview.
    • Lesson learn: should practice leetcode.
  • Recruiter prescreen passed.
  • Recruiter said you might practice leetcode.

Data structure & algorithm (rusty):

System design:
After:
  • Reject.
  • Feedback:
    • Good at problem understanding 
    • Good at algorithm
    • Bad at coding
    • Wait for next 6 months
  • Lesson learn:
    • More practice on coding
    • No system design problem in the phone interview. Only algorithm and actual coding in google doc.

    2018年6月9日 星期六

    [Data Structure] Sliding Window

    Problems:


    239. Sliding Window Maximum:
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums == null || k == 0) {
                return new int[0];
            }
            int[] maxSlidingWindow = new int[nums.length - k + 1];
            int maxSlidingWindowPos = 0;
            Deque<Integer> potential = new ArrayDeque<>();
            for (int i = 0; i < nums.length; i++) {
                while (!potential.isEmpty() && potential.peekFirst() < i - k + 1) {
                    potential.pollFirst();
                }
                
                while (!potential.isEmpty() && nums[potential.peekLast()] < nums[i]) {
                    potential.pollLast();
                }
                
                potential.offer(i);
                
                if (i - k + 1 >= 0) {
                    maxSlidingWindow[maxSlidingWindowPos++] = nums[potential.peekFirst()];
                }
            }
            return maxSlidingWindow;
        }
    }
    

    [Algorithm][Graph] Topological sort

    Topological-Sort(G)
    1. call DFS(G) to compute finishing times v.f for each vertex v
    2. as each vertex is finished, insert in onto the front of a linked list
    3. return the linked list of vertices

    Problem:

    2018年6月8日 星期五

    [Data Structure] LRU Cache

    Video: https://www.youtube.com/watch?v=q1Njd3NWvlY

    Java: HashMap + doubly linked list (custom).

    [Algorithm][Geometry] Sweep line algorithm

    Problems:



    Articles: https://leetcode.com/articles/rectangle-area-ii/
    • Moving the sweep line
    • Sweeping algorithms typically manage two sets of data:
      • The sweep-line status gives the relationships among the objects intersected by the sweep line.
      • The event-point schedule is a sequence of x-coordinates, ordered from left to right, that defines the halting positions of the sweep line. We call each such halting position an event point. Changes to the sweep-line status occur only at event points.
    • The sweep-line status is a total preorder T:
      • INSERT(T, s): insert segment s into T.
      • DELETE(T, s): delete segment s from T.
      • ABOVE(T, s): return the segment immediately above segment s in T.
      • BELOW(T, s): return the segment immediately below segment s in T.
    Any-segments-intersect algorithm:
    ANY-SEGMENTS-INTERSECT(S)
    1. T -> {}
    2. sort the endpoints of the segments in S from left to right, breaking ties by putting points with lower y-coordinates first 
    3. for each point p in the sorted list of endpoints
    4.     if p is the left endpoint of a segment s
    5.     then INSERT(T, s)
    6.     if (ABOVE(T, s) exists and intersects s) or (BELOW(T, s) exists and intersects s)
    7.         then return TRUE
    8.     if p is the right endpoint of a segment s
    9.         if both ABOVE(T, s) and BELOW(T, s) exist and ABOVE(T, s) intersects BELOW(T, s)
    10.             return TRUE
    11.         DELETE(T, s)
    12. return FALSE



    Java:


    2018年5月27日 星期日

    [competitive-data-science] Week 5

    [competitive-data-science] Week 4

    Hyperparameter tuning

    KazAnova's Competition Pipeline (https://github.com/kaz-Anova)
    • Understand the problem
    • Exploratory analysis
    • Define CV strategy
    • Feature engineering 
    • Modelling 
    • Ensembling

    Understand broadly the problem
    • Type of problem
    • How BIG is the data
    • Hardware needed (CPUs, GPUs, RAM, Disk space)
    • Software needed (Tensorflow, Keras, sklearn, LightGBM, xgboost)
    • What is the metric being tested on?
    • Previous code relevant?

    Do some EDA
    • Plot histograms of variables. Check that a feature looks similar between train and test.
    • Plot features vs the target variable and vs time.
    • Consider univariate predictability metrics (IR, R, AUC).
    • Binning numerical features and correlation metrics.

    Decide CV strategy
    • The step is critical. Its success is a good indication for what is going to happen in the competition.
    • People have won by just selecting the right way to validate.
    • Is time important? Split by time. Time-based validation.
    • Different entities than the train. Stratified validation.
    • Is it completely random? Random validation (random K-fold).
    • Combination of all the above.
    • Use test LB to test.

    Feature engineering
    • Image classification: Scaling, shifting, rotations, CNNs. (Data Science Bowls)
    • Sound classification: Fourier, MFCC, specgrams, scaling. (Tensorflow speech recognition)
    • Text classification: TF-IDF, SVD, stemming, spell checking, stop word's removal, x-grams (StumbleUpon Evergreen Classification)
    • Time series: Lags, weighted averaging, exponential smoothing. (Walmart recruitment)
    • Categorial: Target encoding, frequency, one-hot, ordinal, label encoding. (Amazon employee)
    • Numerical: Scaling, binning, derivatives, outlier removals, dimensionality reduction. (Africa soil)
    • Interactions: Multiplications, divisions, group-by features, concatenations. (Homesite)
    • Recommenders: Features on transactional history, item popularity, frequency of purchase. (Acquire Valued Shoppers)

    Modeling
    • Image classification: CNNs (Resnet, VGG, DenseNet, ...)
    • Sound classification: CNNs (CRNN), LSTM
    • Text classification: GBMs, Linear, DL, Naive Bayes, kNNs, LibFM, LIBFFM
    • Time series: Autoregressive models, ARIMA, Linear, GBMs, DL, LSTM
    • Categorial: GBMs, Linear, DL, LibFM, LIBFFM
    • Numerical: GBMs, Linear, DL, SVMs
    • Interactions: GBMs, Linear, DL
    • Recommenders: CF, DL, LibFM, LIBFFM, GBMs

    Ensembling
    • All this time, predictions on internal validation and test are saved.
    • Different ways to combine from averaging to multilayer stacking.
    • Small data requires simpler ensemble techniques.
    • Help to average a few low-correlated predictions with good scores.
    • Stacking process repeats the modeling process.

    Tips on collaboration
    • More fun.
    • Learn more.
    • Better score.
    • Gain in at least 2 ways.
      • You can cover more ground.
      • Every person seizes the problem from different angles leading to more though solutions.
    • Start collaborating after getting some experience to understand the dynamics.
    • Start with people around your "rank".
    • Look for people that are likely to do different things well or that specialize in certain areas. 

    Selection final submissions
    • Normally select the best submission locally and best on LB.
    • It is good to monitor correlations. If submissions exist with high scores but significantly lower correlations, they could be considered too.

    Final tips
    • You never lose. You may not win prize money, but you always gain in terms of knowledge, experience, meeting/collaborating with talented people in the field, boost your CV.
    • The Kaggle community may be the most kind, helpful community I have ever experienced in any social context.
    • After the competition look for people sharing approaches. 
    • Create a notebook with useful method and update it.

    Additional Links:

    [competitive-data-science] Week 3



    Ranking

    Clustering

    [competitive-data-science] Week 2

    Exploratory Data Analysis (EDA): what and why?
    • Better understand the data
    • Build an intuition about the data
    • Generate hypothesizes
    • Find insights
    • Please, do not start with stacking...

    2018年5月24日 星期四

    [competitive-data-science] Week 1


    As in any competitive field, you need to work very hard to get a prize in a competition.


    Real World ML Pipeline:
    • Understanding of business problem
    • Problem formalization
    • Data collecting
    • Data preprocessing
    • Modelling
    • Way to evaluate model in real life
    • Way to deploy model

    Real World Aspect:
    • Competition Problem formalization
    • Choice of target metric
    • Deployment issues
    • Inference speed
    • Data collecting
    • Model complexity
    • Target metric value

    Competition Aspect:
    • Competition Problem formalization (N)
    • Choice of target metric (N)
    • Deployment issues (N)
    • Inference speed (N)
    • Data collecting (Y/N)
    • Model complexity (Y/N)
    • Target metric value (Y)

    Recap of main ML algorithms:

    Overview of ML methods:

    Additional Tools:

    Stack and packages:

    Feature preprocessing:

    Feature generation:

    Feature extraction from text:

    NLP Libraries:

    Feature extraction from images:

    2018年5月16日 星期三

    最近找工作的過程與心得


    繼續舊工作是個選擇,找新工作也是個選擇。

    先寫有結論的部分,沒結論的部分想寫也沒得寫(兩家公司,然後有些也想去看看)。


    1. Google、Microsoft

    結論:完全不理人,相當合理,仔細想想履歷也沒什麼亮點可說。

    試著想辦法讓自己變好,試著結合自己的興趣。很自然想到 Coursera 上找一些課程來加強學習,除此之外還想增加自己的曝光度,畢竟這個世界就很現實,你要有一些成績讓人家看見,人家才會對你感興趣。基於這樣的想法:

    只能不斷的跟自己戰鬥。



    2. Amazon

    結論:Software Development Engineer 感謝函 + Cloud Support Engineer 暫停面試流程。

    有簽 NDA 無法透露細節。只能就公開的工作內容討論。Cloud Support Engineer 工作內容跟我目前工作內容差異極大,我投錯了。不過我很喜歡 Amazon 的 leadership principles 裡面講的東西:

    然後也試著瞭解工作曾經遇過的困難,總要停下腳步才看得清過往的錯誤。粗略看許多 DevOps 的東西,發現 Google 對於 DevOps 的理解與眾不同:

    例如講到 the evolution of automation,他會介紹流程是怎麼進行:
    1. No automation
    2. Externally maintained system-specific automation
    3. Externally maintained generic automation
    4. Internally maintained system-specific automation
    5. Systems that don’t need any automation

    還有講到很多東西,本身才疏學淺,讀起來特別有收穫。Google 這麼做,或許我們可以做個參考,可是這終究是 Google 的經驗,有時候面試想要吹噓幾句還是無法駕輕就熟。



    3. One DevOps Startup

    結論:Offer get.

    想到這個點子,把點子變成賺錢機器,真的很強,台灣新創公司真的很厲害。透過面試再次理解 DevOps,新創公司眼中是寶的東西 (Jenkins、Ansible、Kubernetes),並不是理所當然的存在,只是自己沒有深入瞭解 DevOps 裡頭的東西。

    (有衝動想把這些 tech stacks 架起來玩,等我有空的時候)

    要說有什麼不足,可能是差強人意的薪水,雖然這產業的薪水相較於台商已經夠好了。面試過程沒有刁難的技術問題,這意味著許多事情。從出社會到現在是安安拔拔,就算是差強人意的薪水,自己也沒本事自己出來創業當老闆,也能發給員工那麼多薪水,所以還是要感謝公司願意給你那麼多薪水(非資方打手)。如果將來有新東家願意給你更多薪水,那就要非常感謝新東家。

    如果資本主義本質是貪婪,那我們就該如此貪婪。

    (沒啥溫度的真理)

    (幻想把勞動法修完湊學分,幻想自己可以認真唸書考律師。幻想翻開民訴口述講義不會想睡覺)

    (但一切都經不起貪婪真理的檢驗)



    每個時刻都有每個時刻的困惑,但總是想讓自己快樂點。



    希望沿莉寶貝放鬆一點,我也放鬆一點。

    2018年5月10日 星期四

    2018年4月27日 星期五

    [Note #4][Algorithm] Backtracking

    Backtracking: http://acm.nudt.edu.cn/~twcourse/Backtracking.html

    Example:
    • Problem: 
      • A ring is composed of n (even number) circles as shown in diagram. Put natural numbers into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
      • Note: the number of first circle should always be 1.
      • You are to write a program that completes above process.
    • AC: https://github.com/Meng-Gen/UVa/blob/master/UVa/acm_524.cc


    2018年4月24日 星期二

    [Note] TCP/IP State Transition

    TCP/IP State Transition Diagram:

    UNIX Network Programming (Volume1) 3rd:

    There are 11 different states defined for a connection and the rules of TCP dictate the transitions from one state to another, based on the current state and the segment received in that state. For example, if an application performs an active open in the CLOSED state, TCP sends a SYN and the new state is SYN_SENT. If TCP next receives a SYN with an ACK, it sends an ACK and the new state is ESTABLISHED. This final state is where most data transfer occurs.

    The two arrows leading from the ESTABLISHED state deal with the termination of a connection. If an application calls close before receiving a FIN (an active close), the transition is to the FIN_WAIT_1 state. But if an application receives a FIN while in the ESTABLISHED state (a passive close), the transition is to the CLOSE_WAIT state.

    We denote the normal client transitions with a darker solid line and the normal server transitions with a darker dashed line. We also note that there are two transitions that we have not talked about: a simultaneous open (when both ends send SYNs at about the same time and the SYNs cross in the network) and a simultaneous close (when both ends send FINs at the same time).



    Three-Way Handshake

    The following scenario occurs when a TCP connection is established:
    1. The server must be prepared to accept an incoming connection. This is normally done by calling socket, bind, and listen and is called a passive open. 
    2. The client issues an active open by calling connect. This causes the client TCP to send a "synchronize" (SYN) segment, which tells the server the client's initial sequence number for the data that the client will send on the connection. Normally, there is no data sent with the SYN; it just contains an IP header, a TCP header, and possible TCP options (which we will talk about shortly).
    3. The server must acknowledge (ACK) the client's SYN and the server must also send its own SYN containing the initial sequence number for the data that the server will send on the connection. The server sends its SYN and the ACK of the client's SYN in a single segment.
    4. The client must acknowledge the server's SYN.
    The minimum number of packets required for this exchange is three; hence, this is called TCP's three-way handshake.



    TCP Connection Termination

    While it takes three segments to establish a connection, it takes four to terminate a connection.
    1. One application calls close first, and we say that this end performs the active close. This end's TCP sends a FIN segment, which means it is finished sending data. 
    2. The other end that receives the FIN performs the passive close. The received FIN is acknowledged by TCP. The receipt of the FIN is also passed to the application as an end-of-file (after any data that may have already been queued for the application to receive), since the receipt of the FIN means the application will not receive any additional data on the connection.
    3. Sometime later, the application that received the end-of-file will close its socket. This causes its TCP to send a FIN.
    4. The TCP on the system that receives this final FIN (the end that did the active close) acknowledges the FIN.

    2018年4月23日 星期一

    我回來了。


    (中午休息阿比指我,殊不知另外四指指著自己 XD)

    我回來了。


    感謝大家願意等我回來。


    這陣子花很多時間偷懶,花很多時間調適,因為安安來我們家當我們的寶貝,有時候小哭包一直哭一直哭,忍不住洩氣抱怨你到底要怎樣,也有時候半夜四點起來鬧,抱著走來走去泡牛奶躺在地墊玩,直到早上九點沿莉把我從深淵拯救出來,更有時候婆婆幫忙照顧安安,讓沿莉和我出來透風發呆。


    可是想到自己可能比安安先走,又忍不住眼淚想哭。勞動法老師講課時告訴我們,他希望有生之年可以看到最低工資法過關,老師不是批評政府,而是期望自己長命百歲。這邊得到一個結論,盡量把身體弄健康點,就可以看久一點的沿莉和安安。


    感謝賓賓體恤民心,願意開散步路線讓大家散散步。很努力跟上大家腳步(鑽芒草很像螞蟻在草地上那邊鑽來鑽去),很努力跟著大家聊天話題回憶什麼東西,很久沒出來走早已沒貨可以講(掩面),比較糟的行為是亂指路,大量預設散步等級的路在腦海,接著剔除路底太差的小路,然後發現沒路可走(被龍頭揪錯)。磺嘴山火山口是漂亮,可惜螞蟻看不到上帝視角,在冰島的時候很想繞大的火山口走一圈,結果到台灣磺嘴山的火山口,又嫌太累沒去走一圈,整個就是偷懶的人。


    至少載三個人可以拿來說嘴。


    下山送人回家,原本車上打算聽陳聰富講民總,結果只是聽著廣播累著發呆,我想感冒在家顧安安的沿莉應該更累。


    感謝沿莉愛護安安,安安長大也會愛麻麻。

    2018年4月13日 星期五

    [Note] Some questions about threads & processes

    1. Singleton pattern: https://en.wikipedia.org/wiki/Singleton_pattern

    2. The difference between a process and a thread

    Processes
    • Concept
      • A process is an instance of a program in execution.
      • Modern systems allow a single process to have multiple threads of execution, which execute concurrently.
    • Process Scheduling
      • The two main objectives of the process scheduling system are to keep the CPU busy at all times and to deliver "acceptable" response times for all programs, particularly for interactive ones.
      • The process scheduler must meet these objectives by implementing suitable policies for swapping processes in and out of the CPU.

    (Quote from here)

    Threads
    • Overview
      • A thread is a basic unit of CPU utilization, consisting of a program counter, a stack, and a set of registers, (and a thread ID.)
      • Traditional (heavyweight) processes have a single thread of control - There is one program counter, and one sequence of instructions that can be carried out at any given time.
    • Motivation
      • Threads are very useful in modern programming whenever a process has multiple tasks to perform independently of the others.
      • This is particularly true when one of the tasks may block, and it is desired to allow the other tasks to proceed without blocking. For example in a word processor, a background thread may check spelling and grammar while a foreground thread processes user input (keystrokes), while yet a third thread loads images from the hard drive, and a fourth does periodic automatic backups of the file being edited. 
      • Another example is a web server - Multiple threads allow for multiple requests to be satisfied simultaneously, without having to service requests sequentially or to fork off separate processes for every incoming request.
    • Benefits
      • Responsiveness - One thread may provide rapid response while other threads are blocked or slowed down doing intensive calculations.
      • Resource sharing - By default threads share common code, data, and other resources, which allows multiple tasks to be performed simultaneously in a single address space. 
      • Economy - Creating and managing threads is much faster than performing the same tasks for processes. 
      • Scalability, i.e. Utilization of multiprocessor architectures - A single threaded process can only run on one CPU, no matter how many may be available, whereas the execution of a multi-threaded application may be split amongst available processors.

    Example: Chrome
    • Problem 
      • It's nearly impossible to build a rendering engine that never crashes or hangs. It's also nearly impossible to build a rendering engine that is perfectly secure. 
      • In some ways, the state of web browsers around 2006 was like that of the single-user, co-operatively multi-tasked operating systems of the past. As a misbehaving application in such an operating system could take down the entire system, so could a misbehaving web page in a web browser. All it took is one browser or plug-in bug to bring down the entire browser and all of the currently running tabs. 
      • Modern operating systems are more robust because they put applications into separate processes that are walled off from one another. A crash in one application generally does not impair other applications or the integrity of the operating system, and each user's access to other users' data is restricted.

    3. The producer-consumer problem: race condition
    • In this condition a piece of code may or may not work correctly, depending on which of two simultaneous processes executes first, and more importantly if one of the processes gets interrupted such that the other process runs between important steps of the first process.
    • A specific example of a more general situation known as the critical section problem. 
    • A solution to the critical section problem must satisfy the following three conditions:
      • Mutual Exclusion - Only one process at a time can be executing in their critical section.
      • Progress - If no process is currently executing in their critical section, and one or more processes want to execute their critical section, then only the processes not in their remainder sections can participate in the decision, and the decision cannot be postponed indefinitely.
      • Bounded Waiting - There exists a limit as to how many other processes can get into their critical sections after a process requests entry into their critical section and before that request is granted.
    • Peterson's Solution
      • Peterson's Solution is a classic software-based solution to the critical section problem. It is unfortunately not guaranteed to work on modern hardware, due to vagaries of load and store operations.
    • Synchronization Hardware
      • To generalize the solution expressed above, each process when entering their critical section must set some sort of lock, to prevent other processes from entering their critical sections simultaneously, and must release the lock when exiting their critical section, to allow other processes to proceed. Obviously it must be possible to attain the lock only when no other process has already set a lock. 
    • Mutex Locks
      • The hardware solutions presented above are often difficult for ordinary programmers to access, particularly on multi-processor machines, and particularly because they are often platform-dependent.
      • Therefore most systems offer a software API equivalent called mutex locks or simply mutexes.
      • The terminology when using mutexes is to acquire a lock prior to entering a critical section, and to release it when exiting.
      • One problem with the implementation shown here is the busy loop used to block processes in the acquire phase. These types of locks are referred to as spinlocks, because the CPU just sits and spins while blocking the process. 
      • Spinlocks are wasteful of cpu cycles, and are a really bad idea on single-cpu single-threaded machines, because the spinlock blocks the entire computer, and doesn't allow any other process to release the lock.
      • On the other hand, spinlocks do not incur the overhead of a context switch, so they are effectively used on multi-threaded machines when it is expected that the lock will be released after a short time.
    • Semaphores
      • A more robust alternative to simple mutexes is to use semaphores, which are integer variables for which only two atomic operations are defined, the wait and signal operations.
      • Note that not only must the variable-changing steps (S-- and S++) be indivisible, it is also necessary that for the wait operation when the test proves false that there be no interruptions before S gets decremented.

    4. Deadlocks
    • A set of processes is deadlocked when every process in the set is waiting for a resource that is currently allocated to another process in the set.
    • Necessary Conditions
      • Mutual Exclusion - At least one resource must be held in a non-sharable mode; If any other process requests this resource, then that process must wait for the resource to be released. 
      • Hold and Wait - A process must be simultaneously holding at least one resource and waiting for at least one resource that is currently being held by some other process. 
      • No preemption - Once a process is holding a resource, then that resource cannot be taken away from that process until the process voluntarily releases it. 
      • Circular Wait - A set of processes { P[0], P[1], P[2], ..., P[N] } must exist such that every P[i] is waiting for P[(i+1) % (N+1)]. 
    • Methods for Handling Deadlocks
      • Deadlock prevention or avoidance - Do not allow the system to get into a deadlocked state.
      • Deadlock detection and recovery - Abort a process or preempt some resources when deadlocks are detected.
      • Ignore the problem all together - If deadlocks only occur once a year or so, it may be better to simply let them happen and reboot as necessary than to incur the constant overhead and system performance penalties associated with deadlock prevention or detection.

    5. Classical Synchronization Problems

    References:

    2018年4月7日 星期六

    [Note] Competitive Programming Overview

    Category:
    • Ad Hoc
      • Straightforward
      • Simulation
    • Complete Search
      • Iterative
      • Backtracking
    • Divide & Conquer
    • Greedy
      • Classic
      • Original
    • Dynamic Programming
      • Classic
        • Kadane's algorithm
      • Original
    • Graph
    • Mathematics
      • Factorial
      • Fibonacci Q-Matrix
    • String Processing
    • Computational Geometry
    • Otherwise

    2018年3月31日 星期六

    [Note #3][Algorithm] Kadane’s algorithm


    Maximum subarray sum

    Given an array of n numbers, our task is to calculate the maximum subarray sum, i.e., the largest possible sum of a sequence of consecutive values in the array.

    1. Brute force: O(n^3) or O(n^2).

    2. Divide and Conquer: O(n log(n)).

    3. Kadane’s algorithm (Dynamic Programming): O(n)

    int best = 0, sum = 0;
    for (int k = 0; k < n; k++) {
        sum = max(array[k], sum + array[k]);
        best = max(best, sum);
    }
    cout << best << "\n";
    



    [FWD] Book: Competitive Programming


    First edition: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.457.3263&rep=rep1&type=pdf (The latest edition is the 3rd but not free in the Internet.)

    Related book: Antti Laaksonen, Competitive Programmer’s Handbook. [PDF]


    2018年3月9日 星期五

    王玉皇《刑罰與社會規訓》


    原本以為會講很多 Michel Foucault 理論的東西,不過這本書談幾個重要議題,相互印證 Michel Foucault 講的東西,突然覺得很有啟發性,畢竟理論還是要能夠結合現實發生的問題。以台灣來說問題大概就是:
    • 吸毒行為
    • 販賣毒品行為
    • 原住民犯罪

    簡單引幾段話:

    「社會大眾自己要求制定規範來管理自己、規訓自己,並要求國家行政體系大量進入原本應該屬於私人的生活領域。因此,任何足以使個人失去自我控制能力的行為,都有可能因為涉及到公眾福祉的損害,而成為公共討論的議題,或受到公共輿論的譴責與非難。」

    「我國森林法雖規定,森林以國有為原則。然而,對於世居於山區的原住民而言,這樣的規定無異是強迫他們放棄原本對山林自然資源的依賴,也是一種限制原住民傳統生活與習慣的刑事法規範。雖然這樣的刑事法規範,有其保護森林資源的重要意義存在,但同時也是一種企圖強迫原住民改變既有生活型態的規範。」


    再深入的問題,可能答案要往哲學方向找了,國家並不能幫你解決問題,我還是主張國家的本質就是邪惡。

    2018年3月2日 星期五

    薩米爾欽《我們》

    之前翻過傅柯《規訓與懲罰》,這本《我們》頗有呼應之勢。


    「世界上有兩個樂園,沒有自由的幸福,和沒有幸福的自由。」


    先簡單說明一下傅柯「全景敞視監獄」概念。在一個圓形裡面,圓周位置是一間又一間的全透明的玻璃囚室,圓心之處有一座塔上面裝滿監視器,在邊緣的囚犯無法得知自己是否被監視,長期處於不安之中,只得保持秩序。

    (老大哥正在看著你。)

    (如果沒有違法就不必擔心監聽。)


    不只是小說,比較貼近台灣生活的就是路上監視器及無所不在的監聽,我們早已踏上房子變透明的路上。這本小說由野人出版社出版,以下把有意思的片段寫在下面,供自己參考。


    「坐在那堆可笑的髒兮兮葉子上的黃眼睛傢伙,牠的生活根本不可能用數字加以計算,可要是這種生活竟然比我的更快樂,那可怎麼辦!」(P109)


    在國家面前,要說我有任何權利,這簡直就像在斷言一克在天平上可以與一噸抗衡!合乎情理的分配應該是這樣的:權利由噸享用,義務讓克承擔。想要從一無所有發展到偉大,最自然而然的辦法就是忘記一個人是一克,並牢記一個人只是一噸的百萬分之一!」(P131-132)


    「他們知道順從是美德,驕傲是邪惡。我們源自上帝,我源自魔鬼。」(P143)


    大家盼望多時的一致日慶祝活動於昨天舉行。曾無數次證明他的無上智慧不可動搖的無所不能者獲得一致通過,連續第四十八次全票當選。慶祝活動中出現了一點騷亂,騷亂份子都是幸福的敵人,所幸他們為數不多。這些人由於其行為,自然喪失了擔任聯眾國基石的資格。眾所周知,他們的選票全部作廢,因為如果不這麼處置,我們不就相當於把闖進音樂廳病人的一聲咳嗽聲也視為一場偉大交響樂的一部分了嗎?」(P165)

    (這跟二二八事件有很強的既視感。當我們認同潑漆事件,此時便順從了某個規訓。反對來說,當我們反對潑漆事件,我們又順從了另個規訓。只要我們在某件事訂個規則,自然就會產生犯規者,或者說,正因為我們要處罰那邊看不順眼的人,所以我們訂下了規則。撇開國家不談,我們是否對人類有足夠的同情心?)

    (別忘了,這跟勞基法通過也有很強的既視感,規訓技術不同罷了。)


    安安從小被放在理想型態下長大,台大醫院、台北市的月子中心、各式各樣的育兒知識、童書,以及長輩無微不至的愛護,此時安安是沒有自由的幸福,長大希望他能成為那時代的薩米爾欽、那時代的傅柯、那時代的班雅明、那時代的阿岡本、那時代自己的安安。


    2018年2月10日 星期六

    [Note] Bitcoin

    Bitcoin:
    • Book: Mastering Bitcoin, 2nd Edition Programming the Open Blockchain By Andreas Antonopoulos [Github]
    • Bitcoin: A Peer-to-Peer Electronic Cash System [PDF][簡中]

    Blockchain:

    Math:
    • The Group Structure on an Elliptic Curve [PDF]
      • Elliptic Curve Discrete Log Problem
      • Schoof, Elkies, and Atkin for computing #E(Z/pZ)
      • No known analogue of index calculus attacks on the discrete log problem.

    2018年1月7日 星期日

    [FWD]《法律的鬥爭》


    王澤鑑《民法總則》前頭這篇文章非常淺白。


    如果還想看更多:
    • Walter Benjamin, Critique of Violence.
    • Giorgio Agamben, Homo Sacer.

    後來我們會發現,講完「天日昭昭」兩遍照樣莫須有,如果把眼光移到對立面,宋高宗暴力才是真理。



    法律的鬥爭

    著作:魯道夫.馮.耶林
    翻譯:薩孟武



    法律的目的是和平,而達到和平的手段則為鬥爭。法律受到不法的侵害之時——這在世界上可能永遠存在——鬥爭是無法避免的。法律的生命是鬥爭,即民族的鬥爭,國家的鬥爭,階級的鬥爭,個人的鬥爭。

    世界上一切法律都是經過鬥爭而後得到的。法律的重要原則無一不是由反對者的手中奪來。法律的任務在於保護權利,不問民族的權利或個人的權利,凡想保全權利,事前須有準備。法律不是紙上的條文,而是含有生命的力量。正義之神,一手執衡器以權正義,一手執寶劍,以實現正義,寶劍而無衡器,不過暴力。衡器而無寶劍,只是有名無實的正義。二者相依相輔,運用寶劍的威力與運用衡器的技巧能夠協調,而後法律才完全見諸實行。

    世上有不少的人,一生均在和平的法律秩序之中,過其悠遊自在的生活。我們若對他們說:「法律是鬥爭」,他們將莫明其妙。因為他們只知道法律是保障和平與秩序。這也難怪他們,猶如豪門子弟繼承祖宗的遺產,不知稼穡艱難,從而不肯承認財產是勞動的成果。我們以為,法律也好,財產也好,都包含兩個要素,人們因其環境之不同,或只看到享樂與和平之一面,或只看到勞苦與鬥爭之一面。

    財產及法律猶如雙面神的耶奴斯的頭顱(Janus-head)一樣,對甲示其一面,對乙又示其另一面,於是各人所得的印象就完全不同。此種雙面的形象,不但個人,就是整個時代也是一樣。某一時代的生活是戰爭,另一時代的生活又是和平。各民族因其所處時代不同,常常發生一種錯覺。此種錯覺實和個人的錯覺相同,當和平繼續之時,人們均深信永久和平能夠實現,然而砲聲一響,美夢醒了。以前不勞而獲的和平時代已成陳跡,接著而來的則為面目全非的混亂時代。要衝破這個混亂時代,非經過艱苦的戰爭,絕不能恢復和平。沒有戰鬥的和平及沒有勤勞的收益,只存在於天堂。其在人間,則應是努力辛苦奮鬥的結果。

    德文Recht有客觀的(objective)及主觀的(subjective)兩種意義。客觀的意義是指法律,即指國家所維護的法律原則,也就是社會生活的法律秩序。主觀的意義是指權利,即將抽象的規則改為具體的權利。法律也好,權利也好,常常遇到障礙;要克服障礙,勢非採取鬥爭的方法不可。

    我們知道法律需要國家維持。任何時代必定有人想用不法的手段侵害法律。此際國家若袖手旁觀,不予鬥爭,則法律的尊嚴掃地,人民將輕蔑法律,視為一紙具文。然而我們須知法律又不是永久不變的,一方有擁護的人,同時又有反對的人,兩相對立,必引起一場鬥爭。在鬥爭中,勝負之數不是決定於理由的多少,而是決定於力量的大小。不過人世的事常不能循著直線進行,多採取中庸之道。擁護現行法律是一個力量,反對現行法律也是一個力量,兩個力量成為平行四邊形的兩邊垂直線,兩力互相牽制,終則新法律常趨向對角線的方向發展。一種制度老早就應廢止,而卒不能廢止者,並不是由於歷史的惰性,而是由於擁護者的抵抗力。

    是故在現行法律之下,要採用新的法律,必有鬥爭。這個鬥爭或可繼續數百年之久。兩派對立,都把自己的法律——權利視為神聖不可侵犯。其結果如何,只有聽歷史裁判。在過去法制史之上,如奴隸農奴的廢除,土地私有的確立,營業的自由,言論的自由,信教的自由等等,都是人民經過數世紀的鬥爭,才能得到的。法律所經過的路程不是香花鋪路,而是腥血塗地,吾人讀歐洲歷史,即可知之。

    總而言之,法律不是人民從容揖讓,坐待蒼天降落的。人民要取得法律,必須努力,必須鬥爭,必須流血。人民與法律的關係猶如母子一樣,母之生子須冒生命的危險,母於之間就發生了親愛感情。凡法律不由人民努力而獲得者,人民對之常無愛惜之情。母親失掉嬰兒,必傷心而痛哭;同樣,人民流血得到的法律亦必愛護備至,不易消滅。



    現在試來說明法律鬥爭。這個鬥爭是由一方要侵害法益,他方又欲保護法益而引起的。不問個人的權利或國家的權利,其對侵害,無不盡力防衛。蓋權利由權利人觀之,固然是他的利益,而由侵害人觀之,亦必以侵害權利為他的利益,所以鬥爭很難避免。上自國權,下至私權,莫不皆然。國際上有戰爭,國內有暴動與革命。在私權方面,中世有私刑及決鬥,今日除民事訴訟之外,尚有自助行為。此數者形式不同,目的亦異,而其為鬥爭則一。於是就發生一個問題:我們應該為權利而堅決反抗敵人乎,抑為避免鬥爭,不惜犧牲權利乎?前者是為法律而犧牲和平,後者則為和平而犧牲法律。固然任誰都不會因為一元銀幣落在水中,而願出兩元銀幣雇人撈取。這純粹出於計算。至於訴訟卻未必如此,當事人不會計較訴訟費用多少,也不想將訴訟費用歸諸對方負擔。勝訴的人雖知用費不貲,得不償失,而尚不肯中輕訴訟,此中理由固不能以常理測之。

    個人的糾紛姑且不談,今試討論兩國的紛爭。甲國侵略乙國,雖然不過荒地數里,而乙國往往不惜對之宣戰。為數里之荒地,而競犧牲數萬人之生命,數億元之鉅款,有時國家命運且因之發生危險。此種鬥爭有什麼意義?蓋乙國國民若沉默不作抗爭,則今天甲國可奪取數里荒地,明天將得寸進尺,奪取其他土地,弄到結果,乙國將失掉一切領土,而國家亦滅亡了。由此可知國家因數里荒地所以不惜流血,乃是為生存而作戰,為名譽而作戰,犧牲如何,結果如何,他們是不考慮的。

    國民須保護其領土,則農民土地若為豪強侵佔數丈,自可起來反抗,而提起訴訟。被害人提起訴訟,往往不是因為實際上的利益,而是基於權利感情(feeling of right),對於不法行為,精神上感覺痛苦。即不是單單要討還標的物,而是要主張自己應有的權利。他的心聲告訴他說:你不要退縮,這不是關係毫無價值的物,而是關係你的人格,你的自尊,你的權利感情。簡單言之,訴訟對你,不是單單利益問題,而是名譽問題,即人格問題。

    世上必有不少的人反對吾言。這個反對意見一旦流行,則法律本身就歸毀滅。法律能夠存在,乃依靠人們對於不法,肯作勇敢的反抗,若因畏懼而至逃避,這是世上最卑鄙的行為。我敢堅決主張,吾人遇到權利受到損害,應投身於鬥爭之個出來反抗。此種反抗乃是每個人的義務。



    權利鬥爭是權利人受到損害,對於自己應盡的義務。生存的保全是一切動物的最高原則。但是其他動物只依本能而保全肉體的生命,人類除肉體的生命之外,尚有精神上的生命。而此精神上的生命由法律觀之,則為權利。沒有法律,人類將與禽獸無別。一種法律都是集合許多片段而成,每個片段無不包括肉體上及精神上的生存要件。拋棄法律等於拋棄權利,這在法律上是不允許的,而且亦不可能。如其可能,必定受到別人侵害;抵抗侵害乃是權利人的義務。吾人的生存不是單由法律之抽象的保護,而是由於具體的堅決主張權利。堅決主張自己的權利,不是由於利益.而是出於權利感情的作用。

    那輩竊盜因他自己不是所有權人,故乃否認所有權的存在,更否認所有權為人格的要件。是則竊盜的行為不但侵害別人的財物,且又侵害別人的人格,受害人應為所有權而防衛自己的人格。因此竊盜的行為可以發生兩種結果:一是侵害別人的權益;二是侵害別人的人格。至於上述豪強侵佔農民的田地,情形更見嚴重。倘若該受害農民不敢抗爭,必為同輩所輕視。同輩認為其人可欺,雖不敢明日張膽,亦將偷偷摸摸,蠶食該農民的土地。所有權觀念愈發達,受害人愈難忍受侵害,從而反抗的意志亦愈益強烈。故凡提起訴訟而能得到勝訴,應對加害人要求雙重賠償,一是討還標的物;二是賠償權利感情的損傷。

    各種國家對於犯罪之會加害國家的生存者,多處以嚴刑。在神權國,凡慢瀆神祗的處嚴刑,而擅自改變田界的,只視為普通的犯罪(例如摩西法)。農業國則反是,擅自改變田界的處嚴刑,慢瀆神祗的處輕刑(古羅馬法)。商業國以偽造貨幣,陸軍國以妨害兵役,君主國以圖謀不軌,共和國以運動復辟,為最大的罪狀。要之,個人也好,國家也好,權利感情乃於生存要件受到損害之時,最為強烈。

    權利與人格結為一體之時,不問是那一種權利,均不能計算價值之多少。此種價值不是物質上的價值(material value),而是觀念上的價值(ideal value)。對於觀念上的價值,不論貧與富,不論野蠻人與文明人,評價都是一樣。至其發生的原因,不是由於知識的高低,而是由於苦痛感情的大小。也許野蠻人比之文明人,權利感情更見強烈。文明人往往無意之中,計算得失孰大孰小。野蠻人不憑理智,只依感情,故能勇往猛進,堅決反抗權利之受侵害。但是文明人若能認識權利受到侵害,不但對他自己,而且對整個社會,都可以發生影響,亦會拔劍而起,挺身而鬥,不計利害,不計得失。吾於歐洲許多民族之中,只知英國人民有此權利感情。英國人民旅行歐洲大陸,若受旅館主人或馬車馭者的欺騙,縱令急於出發,亦願延期啟行,向對方交涉,雖犧牲十倍的金錢,亦所不惜。這也許可以引人嗤笑,其實嗤笑乃是不知英國人民的性格,所以與其嗤笑英人,不如認識英人。



    為法律而鬥爭,是權利人的義務,已如上所言矣。茲再進一步,說明個人擁護自己的法律——即法律上的權利——又是對於社會的義務。

    法律與權利有何關係?我們深信法律乃是權利的前提,只有法律之抽象的原則存在,而後權利才會存在。權利由於法律,而後才有生命,才有氣力,同時又將生命與氣力歸還法律。法律的本質在於實行,法律不適於實行或失去實行的效力,則法律已經沒有資格稱為法律了;縱令予以撤廢,亦不會發生任何影響。這個原則可適用於一切國法,不問其為公法,其為刑法,其為私法。公法及刑法的實行,是看官署及官吏是否負起責任,私法的實行則看私人是否擁護自己的權利。私人放棄自己的權利,也許由於愚昧,不知權利之存在;也許由於懶惰或由於畏懼,不欲多事,其結果,法律常隨之喪失銳氣而等於具文。由此可知私法的權威乃懸於權利的行使,一方個人的生命由法律得到保障,他方個人又將生命給與法律,使法律有了生氣。法律與權利的關係猶如血液的迴圈,出自心臟,歸於心臟。

    個人堅決主張自己應有的權利,這是法律能夠發生效力的條件。少數人若有勇氣督促法律的實行,藉以保護自己的權利,雖然受到迫害,也無異於信徒為宗教而殉難。自己的權利受到侵害,而乃坐聽加喜人的橫行,不敢起來反抗,則法律將為之毀滅。故凡勸告被害人忍受侵害,無異於勸告被害人破壞法律。不法行為遇到權利人堅決反抗,往往會因之中止。是則法律的毀滅,責任不在於侵害法律的人,而在於被害人缺乏勇氣。我敢大膽主張:「勿為不法」 (Do no injustice)固然可嘉,「勿寬容不法」(Suffer no injustice)尤為可貴。蓋不法行為不問是出之於個人,或是出之於官署,被害人若能不撓不屈,與其抗爭,則加害人有所顧忌,必不敢輕舉妄動。由此可知我的權利受到侵犯,受到否認,就是人人權利受到侵犯,受到否認。反之,我能防護權利,主張權利,回復權利,就是人人權利均受防護,均有主張,均能回復。故凡為一己的權利而奮鬥,乃有極崇高的意義。

    在這個觀念之下,權利鬥爭同時就是法律鬥爭,當事人提起訴訟之時,成為問題的不限於權利主體的利益,即整個法律亦會因之發生問題。莎士比亞在其所著(威尼斯的商人) (Merchant of Venice)中,描寫猶太商人舍洛克(Shylock)貸款給安多紐(Anto-nio)的故事,中有舍洛克所說的一段話:

    我所要求一磅的肉,

    是我買來的,這屬於我,我必須得到;

    你們拒絕不予,就是唾棄你們的法律;

    這樣,威尼斯的法律又有什麼威力。

    ……我需要法律,

    ……我這裏有我的證件。

    「我要法律」一語,可以表示權利與法律的關係。又有人人應為維護法律而作鬥爭的意義。有了這一句話,事件便由舍洛克之要求權利,一變而為威尼斯的法律問題了。當他發出這個喊聲之時,他已經不是要求一磅肉的猶太人而是凜然不可侵犯的威尼斯法律的化身,他的權利與威尼斯的法律成為一體。他的權利消滅之時,威尼斯的法律也歸消滅。不幸得很,法官竟用詭計,拒絕舍洛克履行契約。契約內容苟有反於善良風俗,自得謂其無效。法官不根據這個理由,既承認契約為有效,而又附以割肉而不出血的條件。這猶如法官承認地役權人得行使權利,又不許地役權人留足印子地上。這種判決,舍洛克何能心服。當他悄然離開法庭之時,威尼斯的法律也俏然毀滅了。

    說到這裏,我又想起另一作家克萊斯特(Henrich von Kleist) 所寫的小說《米刻爾.科爾哈斯》(Michael Kohlass)了。舍洛克悄然走出,失去反抗之力而服從法院的判決。反之,科爾哈斯則不然了。他應得的權利受到侵害,法官曲解法律,不予保護,領主又左袒法官,不作正義的主張。他悲憤極了,說道:「為人而受蹂躪,不如為狗」,「禁止法律保護吾身,便是驅逐吾身於蠻人之中。他們是把棍子給我,叫我自己保護自己」。於是憤然而起,由正義的神那裏,奪得寶劍,揮之舞之,全國為之震駭,腐化的制度為之動搖,君主的地位為之戰慄。暴動的號角已經鳴了。權利感情受到侵害,無異於對人類全體宣戰。但是驅使科爾哈斯作此行動,並不是單單報仇而已,而是基於正義的觀念。即余當為自己目前所受的侮辱,恢復名譽;並為同胞將來所受的侵害,要求保護,這是余的義務。結果,他便對於從前宣告他為有罪的人——君主、領主及法官,科以2倍、3倍以上的私刑。世上不法之事莫過於執行法律的人自己破壞法律。法律的看守人變為法律的殺人犯,醫生毒死病人,監護人絞殺被監護人,這是天下最悖理的事。在古代羅馬,法官受賄,便處死刑。法官審判,不肯根據,而惟視金錢多少,勢力大小,法律消滅了,人民就由政治社會回歸到自然世界,各人均用自己的腕力以保護自己的權利,這是勢之必然。

    人類的權利感情不能得到滿足,往往採取非常手段。蓋國家權力乃所以保護人民的權利感情,而今人民的權利感情反為國家權力所侵害,則人民放棄法律途徑,用自助行為以求權利感情的滿足,不能不說是出於萬不得已。然此又不是毫無結果。教徒的殉難可使羅馬皇帝承認基督教,歐洲各國的民主憲政何一不是由流血得來。科爾哈斯揮動寶劍實是「法治」發生的基礎。



    國民只是個人的總和,個人之感覺如何,思想如何,行動如何,常表現為國民的感覺思想和行動。個人關於私權的主張,冷淡而又卑怯,受了惡法律和惡制度的壓迫,只有忍氣吞聲,不敢反抗,終必成為習慣,而喪失權利感情。一旦遇到政府破壞憲法或外國侵略領土,而希望他們奮然而起,為憲政而鬥爭,為祖國而鬥爭,爭所難能。凡沉於安樂,怯於抗鬥,不能勇敢保護自己權利的人,哪肯為國家的名譽,為民族的利益.犧牲自己的生命。至於名譽或人格也會因而受到損害,此輩是不瞭解的。此輩關於權利,只知其為物質上的利益,我們何能希望他們另用別的尺度以考慮國民的權利及名譽。所以國法上能夠爭取民權,國際法上能夠爭取主權的人,常是私權上勇敢善戰之士。前曾述過,英國人願為區區一便士之微而願付出十倍以上的金錢,與加害人從事鬥爭。有這鬥爭精神,故在國內能夠爭取民主政治,於國外能夠爭取國家聲望。

    對於國民施行政治教育的是私法,絕不是公法。國民在必要時,若能知道如何保護政治的權利,如何於各國之間,防衛國家的獨立.必須該國人民在私人生活方面,能夠知道如何主張他們自己的權利。自己權利受到侵害,不問來自何方,是來自個人乎,來自政治乎,來自外國乎,若對之毫無感覺,必是該國人民沒有權利情感。是故反抗侵害,不是因為侵害屬於那一種類,而是懸於權利感情之有無。

    依上所述,我們可以得到簡單的結論,即對國外要發揚國家的聲望,對國內要建立強國的基礎,莫貴於保護國民的權利感情;且應施以教育,使國民的權利感情能夠生長滋蔓。

    專制國家的門戶常開放給敵人進來。蓋專制政府無不蔑視私權,賦稅任意增加,沒有人反對;徭役任意延長,沒有人抗議。人民養成了盲從的習慣,一旦遇到外敵來侵,人民必萎靡不振,移其過去盲從專制政府者以盲從敵人政府。到了這個時候,政治家方才覺悟,要培養對外民氣,須先培養對內民氣,亦已晚矣。