※ 引述《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). -- その乾いた哀愁の瞳に去來するものは何か？ 失ったもの 得たもの そして廣大なネットの狹間で彼が見たものとは？ 虛像と實存と記號の中に彼は今、何を想うのか？ ＜バトルプログラマーシラセ＞ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 173.228.125.35