我只是想来解谜的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