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

我只是想來解謎的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;
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
缺點是存取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...

: 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分鐘內弄出來吧...

: 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分鐘過關的，打字或線上考試的速度一定超快 = =

--