美國拿第二個CS碩士or台灣碩士硬上 - 面試

※ 引述《dryman (dryman)》之銘言：
: 我只是想來解謎的XD
: : 1. Sereialize and deserialize a b-tree
: 我第一個想到的是偷吃步做法：
: b-tree存的不是指標，而是index to memory pool
: unsigned char* const pool = (unsigned char*)malloc(BIG_N);
: typedef struct node {
: size_t left_node_idx;
: size_t right_node_idx;
: size_t data_idx;
: size_t data_size;
: } Node;

這是 binary tree 不是 b-tree...

: Node* const nodes = (Node*)malloc(N*sizeof(Node));
: Node* node_iter = nodes;
: unsigned char* pool_iter = pool;
: // Assume we have input: unsigned char * input_data
: // here's how we store the data into a node
: Node* node_1 = node_iter++;
: size_t size = sizeof(*input_data);
: memcpy(pool_iter, input_data, size);
: node_1->data_idx = pool_iter - pool;
: node_1->data_size = size;
: pool_iter += size;
: 由於資料都是存在pool以及nodes裡面，所以serialize很簡單，直接輸出index就行了
: 使用pool的好處是，可以realloc，直接擴充長度
: free的時候也可以整個pool一起處理，不需要遞迴一個一個free

樹是活的, 它有可能會長葉子或掉樹枝,
請問你要怎麼解決 fragmentation 的問題?
請不要重新發明輪子, memory allocator 是無數 computer scientist 的心血結晶,
沒有特別理由請不要重新設計 memory allocator.

註: 少數的例外是當你在執行時期需要大量配置固定長度的小物件時,
你可能會想要用特別的 allocator. Linux 的 SLAB 與 WebKit 的 Arena 都是例子.

: 缺點是存取node資料時，syntax比較不方便
: 不過如果node資料是固定的值，例如只是一個int，那倒還好
: 以上使用長度不一的unsigned char是比較麻煩的case
: 如果不是用這種形式來存b-tree
: 那我想..直接輸出lisp form 最直接吧
: (((1 2 3) 4 nil) 5 ((nil 7 8) 6 9))
: 等價於
: 5
: / \
: 4 6
: / / \
: 2 7 9
: / \ \
: 1 3 8
: 畢竟lisp本來就是一種很適合處理遞迴結構的語言，用這種方式輸出很自然
: 也很好parse: 碰到左括號就推到stack，右括號就pop...

這沒有解決任何問題... 表示方式千千種, 要怎麼寫成 code 才是重點.
你說的碰到左括號就 push 右括號就 pop 這是有學名的,
它叫做 LR grammar, push 應該稱作 shift, pop 稱作 reduce.

是我的話寫個遞迴就搞定啦(同等於 recursive descent parser),
除非你的樹會到數百層那麼深,
不過 b-tree 能長到上百層的話那一定是 balance 寫錯啦.

: : 2. 3 sum: find x+y+z=A in an integer array (at least O(n^2) solution)
: 碰到array題目，不求最速解，先從算起來不會太慢的方式來做，就是先sort
: O(nlogn) 得到sort過的array
: 從頭開始找 x O(n)
: 然後從array裡找所有的y O(n^2)
: 最後是z，可用binary search O(n^2 logn)
: 要能算出O(n^2)以內的...
: 我會想試著用鎖定一個，另外兩個用兩個指針從前後包夾去算
: 但詳細算法要慢慢試才弄得出來，不是解面試題玩家很難在15分鐘內弄出來吧...

先 sort, 然後鎖定一個, 另外兩個用包夾去算這個方法是對的.
程式其實不難寫, 大致就這樣吧(五分鐘足矣):

// input
int *v;
size_t n;
int a;

for (size_t x = 2; x < n; x++)
for (size_t y = 0, z = x-1; y < z;){
int sum = v[x] + v[y] + v[z];
if (sum < a)
y++;
else if (sum > a)
z--;
else {
printf ("%d %d %d\n", v[x], v[y], v[z]);
return;
}
}

: : 3. find the medium in an integer array (O(n) solution)
: 這題如果array內容沒先sort過，那也是玩家等級才有辦法在15分鐘內給出演算法+程式
: 不求最速解，那還是一樣先sort --> O(nlogn)
: 看奇偶直接給解n/2+1 or n/2 --> O(1)
: 不求玩家等級的話，這樣就是標準解了，很好想
: 身為面試官倒是可以看看這人對基本的程式語言操作熟不熟悉
: 例如呼叫c q_sort
: 我給的解法都蠻直觀的，也沒有達到效能的要求，可是光打完就遠不只15分鐘啦
: 能夠真的在15分鐘過關的，打字或線上考試的速度一定超快 = =

Linear time selection 是演算法課幾乎一定會教的...
方法不用硬背, 記得概念很容易就想得出來.
(所以不要看 ItoA 那本邪書, 它的證明很完整但是想法講不清楚.
拿來當參考資料很不錯, 但不是好的教科書. 要讀書就去讀 Knuth 全集.)

核心想法很簡單, 如果你能夠在 O(n) 的時間下把 n 縮小一定比例,
那整個演算法也可以在 O(n) 做完. (等比級數)

第二個重點是, selection 跟 sorting 關係密切, 你可以做一個單邊的 quick sort,
方法一樣是隨機選一個 pivot, 用 pivot 把 array 分兩邊,
這個時候你只要往其中一邊(看你要選的 index 落在那一邊)遞迴就好了.
這個方法的複雜度平均是 O(n), 證明是看兩兩個別元素被比較到的機率,
再整個積分起來, 這邊數學有點複雜, 要詳細證明請去查書.
當然, 這跟 quick sort 一樣, 有 worst case 複雜度是 O(n^2) 的問題,
解決這個問題的辦法, 就是要避開 worst case pivot.

這個時候就到第三個重點, 也就是 median of medians 法.
首先你先把 n 個元素 5 個 5 個一組, 每一組個別找到 median,
接下來將這 n/5 個 median 遞迴下去, 找到它的 median, 選作 pivot.
不難證明, 這個 pivot 必然大於 n/4 個元素, 也小於 n/4 個元素.

綜合以上幾點, 我們得到一個 selection algorithm 其複雜度是:
f(n) = f(3n/4) + f(n/5) + O(n)
--> f(n) = O(n)
同理, 此法亦可用於 quick sort 來保證複雜度不差於 O(nlogn).

--
その乾いた哀愁の瞳に去來するものは何か？
失ったもの 得たもの
そして廣大なネットの狹間で彼が見たものとは？
虛像と實存と記號の中に彼は今、何を想うのか？

＜バトルプログラマーシラセ＞

--