[UVA] 10137 The Trip

基本想法如下：由於允許最後分帳差距在1 cent內，所以全部人出的金額只可能有兩種：X跟 X+0.01，所有金額的加總S等於重分配之前的總合。假設有N人，X = floor(S / N)，而多少人出X+0.01 ? N' = (S * 100 ) % N。知道X及N'後，求transaction總合就簡單了。

input雖然長得很像double，但是考慮到之後的運算其其都是整數運算 (以cent為單位)，最好的作法還是把全部金額都看成int。只要把value * 100 即可。機車的地方在於，如果你用 cout >> aDoubleNumber 那你就吃屎了，因為乘100之後的整數位數是不準的，會有one cent offset。比較蠢但是穩的作法便是讀字串進來然後parse成int。output 也不要依賴 cout float_precision，自己印小數點吧!

[UVA] 10003 Cutting sticks

本來以為是單純的Huffman Encoding, WA! 因為Huffman Encoding只考慮棒子的長度，而題目有要求每根棒棒的起點需符合要求。這個陷阱搞了我三十分鍾，算是聰明反被聰明誤。

正確的作法是DP。想法如下：線段(x, y)的min cost可以表達成:
cost(x, y) = len(x, y) + min ( cost(x, z) + cost(z, y) ), where x < z < y。接下來，用2D array 建表即可 。唯一要注意的是diagonal DP的迴圈比較麻煩，第一次寫的時候犯了很多蠢錯。

[UVA] 10405 Longest Common Subsequence

可以說是DP的基本題了，無奈我還是繳了一個WA的過路費。Input不可以使用cin，否則space不能parse。請愛用getline

[UVA] 105 Skyline

經典的一題，搞了我整整一天。原本以為是很簡單的scan line題，結果發現充滿了陷阱。

[TODO]

Skyline有多種解法。最容易implement的方法是暴力建1D array,因為X軸是int 最大才10000，所以建個int[10001]，讀每個building update 每格田度，最後iterate array畫出輪廓即可。

另一種是方法是scan line，可以應付任意X軸範 圍，而且不限定於int。簡單來說，就是在每次遇到新建築時才畫輪廓。我們可以maintain一個heap，記出到目前為止，還沒遇到右端點的buildings。然後在遇到新building時，把heap中其右端點位於新building左端點左邊的building pop掉，然後畫輪廓即可。

這題的陷阱是複數building可能會有同樣的左端點，於是這樣一來必需要要用多餘的一個heap記住目前還沒被丟到heap的buildings, 而在遇到不一樣左端點的building時，把暫時heap的東西pop出灌到normal heap中。

[UVA] 10346 Peter Smokes

題目大義如下：

    Peter愛抽煙，他發現每抽K根煙，抽剩的K個煙屁股可以再捲成一根煙。今天有N根 煙，請問Peter總共可以抽幾次？

    這一題用simulation解非常簡單，原則上就是:
ANS = N + floor(N / K) + floor( N / K^2) + floor( N / K^3) + ....

   的數列和，而floor()是取round down的整數部份。O(logN)的效率還是不錯，不過經CL提點這題有O(1)解法，花了幾個小時狂試，發現居然真的有formula解:

ANS = N + floor( (N - 1) / (K - 1))

   我是作弊先把函數圖畫出來，再歸納出公式，所以並不是正統的邏輯推導得出的答案。我自己對這個公式的解釋是:

    N的部份就是原祖煙。而多出來的部份可以這樣想：抽完的N個煙屁股中，每K個煙屁股可以集中產生一支煙，然後丟棄K-1個煙屁股。這個集中 -- 回收 -- 丟棄的process可以移除 K - 1個煙屁股。這樣可以解釋分母 K - 1的由來，不過N - 1的部份我無法說明。後來經CL解答，才知道可以想成：把第一個煙屁股當做煙 斗，然後每 K - 1 根煙屁股可以跟煙斗合體再抽一次，抽完後剩下煙斗自己 ( K = >  1 )，所以總共有 1個煙斗，N - 1個煙屁股，每 K - 1個煙屁股可以再抽一次，而多抽的次數就是 (N - 1) / (K -1)。非常優雅的證明，也讓我見視到人跟神的差距。

[UVA] 108 Maximum Sum

寫了一堆I/O題後，在108就卡住了。O(n^4)雖然可能會過，不過一看就知道不是正解。

一維的maximum subarray是有線性解的(Kadane)，但是我推不出二維的線性解。原本想法是用DP，讓ary[i][j] 記住從它開始往右往下 展開最大的矩形，然後想辦法湊出ary[i+1][j+1] = function(ary[i-1][j-1], ary[i-1][j], ary[i][j-1])的形式，結果發現似乎不可能有O(n^2)的解><

投降後上網查了一下，發現可以用暴力+Kadane做到O(n^3)解。簡單來說，就是想辦法把2D array compact成一維，然後再找一維的最大值。實作就是把所有的列組合 i ~ j, i < j 列舉，然後累加，例如 Rowi ~ Rowj的累加一維矩陣就是就是 compact[k] =  array[i][k] + array[i+1][k] + .. + array[j][k]。接著把compact丟近Kadane，求最大值，收工。

教訓就是當1D變成多維時，可以使用暴力列舉製作出所有1D的組合再套用1D的DP解。

Square phone interview

3 Rounds phone interview...

#1. Given array A[], find A[j] - A[i] which is max and j < i
A: DP

#2. String reverse
#3. Implement a hash table

#4 Prefix calcuator

prefix calculator

(+ (/ 4 2) 3)

5

giving a string, compute the expression using prefix notation

feel free to make simplifying assumptions about the expression or helper methods available to you

we'll relax some of these assumptions as we go

Palantir Phone Interview

/**
 * Write a function that is given an array of integers. It should return true if
 * and only if there are two integers in the array a[i] and a[j] with the same
 * value such that the difference between i and j is at most k.
 */

boolean containsDuplicateWithinK(int[] arr, int k) {
    // 1. build Map<Integer, Integer>  (key, value) = (number, pos)
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    // 2. Iterate through arr, for each elem, we need to compute the max diff
    int cur = 0;
    for (int ele : arr) {
       if (map.constainsKey(ele)) {
          int diff = cur - map.get(ele);
          if (diff <= k) {
            return true;
          }
       }
       map.set(ele, cur);          
       cur++;
    }
    return false;
}

/**
 * Write a function that is given an array of integers. It should return true if
 * and only if there are two integers in the array with the same value.
 */

boolean containsDuplicate(int[] arr) {
    // 1. build Set
    Set<Integer> set = new HashSet<Integer>();
    // 2. scan the arr, check every element in HashTable or not, if not, push to table
    for (int ele : arr) {
      if (set.contains(ele)) {
        return true;
      }
      set.push(ele);
    }
    // 3. if we reach here, return false
    return false;
}


/**
 * The Fibonacci sequence is defined as
 * F_0 = 0
 * F_1 = 1
 * For each n > 1, F_n = F_(n-1) + F_(n-2)
 *
 * Write a function inverseFibonacci that is given a number fib. If fib is a
 * Fibonacci number, the function should return the index of that Fibonacci
 * number (e.g. if fib is F_8, then the function should return 8). Otherwise,
 * the function should return -1.
 */

int inverseFibonacci(long fib) {
    // Write code here
    int index = 2;
    long value_0 = 0, value_1 = 1;
    long value = value_0 + value_1;
    // 1. Handle corner case first
    if (fib == 0) {
      return 0;
    } else if (fib == 1) {
      return 1;
    } else {
        // fib > 1, we can start index from 2
        while (value < fib) {
            value = value_0 + value_1;
            value_0 = value_1;
            value_1 = value;
            index++;
        }
        // when function comes to here, value is either > or == to fib
          return (value == fib) ? index : -1;    
    }
}

Quora phone interview

都是white board coding, 也就是說只要interviewer沒找出bug 你就pass 了
1. 給一個Reverse polish notation數學運算式, 所有的operand都是整數, operator只有+, -, *, / 。 算出結果
    都已經給reverse polish了, 也不需要做parse ，只要用stack穩穩的算result即可

2. 給一個binary tree (不是binary search tree),  每個node存int, 會有duplicate, 給出第二大 distinct值 (此處簡稱DSM, Distinct Second Maximum) . Eg. 如果tree 裡面是 3, 3, 1, 2, 2, 2  output會是2 ,因為3重複了

    遞迴即可. ex:   DSM(P) = DSM {P, MAX(L), DSM(L), MAX(R), DSM(R)}. done.

        P
      /    \
    L     R

Twitter phone interview (damn I screw up)

Given a class named Stream which represents a math statement, there are only two elements in Stream:

1. operand: only integer

2. operator: only "+" and "*"

the stream has three methods:

boolean hasNext();  // return true if the Stream has operand or operator left, false if cursor reaches end

int getNum(); // return the next operand, increase cursor in stream

char getOp(); // return the next operator, increase cursor in stream

You need to write a method:

int getValue();

which compute the correct value of the given Stream. Remember "*" has higher priority than "+". You can only use constant space.

Its guaranteed that the Stream is always well-formatted, which means, there wont be Stream like 1 ++ 2 or 12 * 3 +* 4. You dont't need to worry about parsing, just use the above three methods. 

算是四則運算的簡化版。不過我居然沒在interview時寫出來，真是太弱了。之後從頭想了一下花了半小時寫玩並在eclipse上簡單驗證:

public class Stream {

    public String[] equation;
    public int index;
    public int length;
    
    public Stream(String eq) {
        this.equation = eq.split(" ");
        this.index = 0;
        this.length = equation.length;
    }
    
    public int getNum() {
        if (index < length) {
            
            return Integer.valueOf(equation[index++]);
        }
        return -9999999;
    }

    public String getOP() {
        if (index < length) {
            return equation[index++];
        }
        return null;
    }
    
    public boolean hasNext() {
        return index < length;
    }
    
    
    public int getValue() {
        this.index = 0;
        int value = 0;
        int num = getNum();
        
        while (hasNext()) {
            String op = getOP();
            if (op.equals("+")) {
                value = value + num;
                num = getNum();
            } else {    
                // op == "*"
                num = num * getNum();
            }  
        }
        value = value + num; 
        return value;
    }
    
    public static void main(String[] args) {
        Stream stream = new Stream("4 * 5 * 2 + 3");
        System.out.print("value = " + stream.getValue());
    }
}

[開卷]高盛陰謀

    趁回台灣休假的期間把這本書看完了。我非常建議在看這本書前先看一下這幾部短片：錢是債、 聯準會、摧毀世界的銀行等等。我們必需要先了解財富是什麼，而銀行又如何的與政府掛勾來任意控制我們財富的價值。然後，你就可以欣當全世界最偉大最聰明也最無恥的銀行一連串掠奪全世界的陰謀了。看完你會醒悟，為什麼杜拜和希臘從風光到完蛋，為什麼油價可以在兩年內瘋狂振蕩，為什麼美國的主人不在白宮，而在華爾街裡面。
    我看完的感想不是高盛如何如何邪惡，政府應該趕快勒令停業。而是高盛這種惡性組織(原諒我，我認為高盛為社會創造的價值遠小於其製造的金融泡沫的傷害)，是否是現行市場機制必然下的產物。我們所奉行的資本主義、自由市場、民主政治、信用經濟，恰恰製造了高盛這種結合政商，不斷壟斷、遞迴增大自己經濟與權力的癌細胞。如果是，那麼就算我們消滅了這個高盛，也還會有千千萬萬個高盛的繼任者長出來。或許，我們需要反思現在的制度，是否真的會創造出無法被解決的bug。