Re: [北美] 美國拿第二個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分鐘過關的，打字或線上考試的速度一定超快 = =
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.45.171.118
→
12/12 00:54, , 1F
12/12 00:54, 1F
→
12/12 02:24, , 2F
12/12 02:24, 2F
→
12/12 02:27, , 3F
12/12 02:27, 3F
推
12/12 04:23, , 4F
12/12 04:23, 4F
→
12/12 04:24, , 5F
12/12 04:24, 5F
→
12/12 07:22, , 6F
12/12 07:22, 6F
→
12/12 07:22, , 7F
12/12 07:22, 7F
→
12/12 07:23, , 8F
12/12 07:23, 8F
→
12/12 07:24, , 9F
12/12 07:24, 9F
→
12/12 07:27, , 10F
12/12 07:27, 10F
→
12/12 08:01, , 11F
12/12 08:01, 11F
→
12/12 08:02, , 12F
12/12 08:02, 12F
→
12/12 08:07, , 13F
12/12 08:07, 13F
→
12/12 08:08, , 14F
12/12 08:08, 14F
→
12/12 08:28, , 15F
12/12 08:28, 15F
討論串 (同標題文章)