※ 引述《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