Siyang的小尾羊圈

处女面结束了，总结如下：

没有展现出自己的problem solving，coding skills

也许题目太简单是一个原因，更重要的是确实有心理因素的影响，放在平时，我肯定会把方方面面都想到，再下笔写code。今天面试的时候急了，第一个behavior问题只回答了准备的一半，想省些时间来多做一些题；看见了简单题目就想立马写完做下一道，结果有些case没有handle到，尽管我做的快，可是也就只有那么一道题，剩下的时间都在聊天。。。。。。

一定要吸取教训！再简单的题目，做前一定要多问interview把spec搞清楚，先预见有哪些cases要handle，包括预见要handle的错误，然后再开写！还有就是，最后还是时间的时候，完全可以再要一道题来做，光是聊天没意思啊。。。

其实我事先准备的时候这些都知道，怎么真实的面试的时候就忘了呢。。。还是心理因素。。。按照我事先的准备正常发挥的话，应该说是可以做到perfect的。。。而现在，只有希望运气好了。。。

sigh，要认真吸取这个教训，下星期一的面试肯定也不会有很多题目，每个题目时间绝对够，在电脑上写code也很适合我，一定要做到perfect！

唉，还是很郁闷。。。

仿佛和两三个朋友一伙，莫名其妙的遭到一个黑社会的追杀，记得有一片森林，冲出森林便是片海滩，激浪中登上只小船，但又担心黑社会的人乘快艇追上来，有人说黑社会的人追不上来，继续往前划船，又有人说肯定会被追上，必须马上回岸跑进丛林躲避。船就在两股意见中不停的原地旋转，即没法前进，又没法后退，心里急得要死。这情形像是不里丹的毛驴，在两堆稻草中犹豫不知道吃哪堆最后饿死掉。

忘了说，场景是在漆黑的夜里，真的是漆黑，除了感受到海里的浪，什么都看不见。最终还是划回了岸上，沿着沙滩飞奔。突然察觉到，后面不远的地方，黑社会的人已经冲出丛林了并且也发现了我们的踪迹！没法，唯一的办法就是钻进漆黑的丛林，歇斯底里的跑，期望着黑夜能给我们打点遮掩。可是跑进丛林才发现，那真是纯黑一片的深手不见五指的黑，连自己的同伴，前面的路都看不见，后面又有追兵，那种漆黑中的慌乱和无助惊恐，实在是没法感同身受的描述出来。

无奈只能继续在那片森林里飞奔，不顾一切的飞奔，要知道，不跑的话就是等死，跑的不够快的话，脚步声就成了敌人追踪的最好引路标。就这样在恐惧的驱使下不知道跑了多久，恐惧完全把疲劳压下去了，幸运的是还没跟自己的队友跑散，不幸的是，始终隐隐约约的感觉到，黑社会的人还在身后跟着。

最终跑出来森林，跑进一个大体育馆，又像是个大健身房，还像一个大仓库，简而言之就是电影里单挑枪战的最佳场所。我们在不同的遮蔽物之间穿梭来穿梭去，竭尽全力的在隐蔽自己的同时想摆脱追捕。在快要跑出房间的最后几个遮挡物的位置，我跟同伴跑散了，而且，黑社会的头子追上来了！也许是在恐惧中憋了太久，我猛地爆发了，狗的黑社会，老子怕你索！举起身边的椅子朝黑社会大佬砸过去！暴怒之下必有勇夫啊，黑老大很轻易的就给打晕了，而我才又陷入了心理的纠结中，我要是留下黑老大活口，就算这会儿跑了出去，以后那是肯定终生被黑社会追杀，终生活在恐惧和担心之中！而我又没法下狠手去残忍的结束一个生命，如果了结了黑老大，我自己内心也是一辈子的痛苦。。。

我都记不得最后是怎么处理的了，总之跑出来了房间，遇上的同伴，幸好梦里的场景开始转换到另外的情节了，最后醒来，清晰记得的只剩被追杀的恐惧。

根据玛雅人的预言上表示，现在我们所生存的地球，已经是在第5太阳纪，并将终结
于西元2012年12月22日，到目前为止，地球已经过了四个太阳纪，而在每一纪结束时，
都会伴随一出惊天动地的毁灭。

* 第一个太阳纪——马特拉克堤利MATLACTIL ART（根达亚文明），最后为一场洪
水所灭，有一说法是诺亚洪水。
* 第二个太阳纪——伊厄科特尔Ehecatl（米索不达亚文明），被风蛇吹的四散零
落而毁灭。
* 第三个太阳纪——奎雅维洛Tleyquiyahuillo（穆里亚文明），则是因为天降火
雨而步向毁灭之路，乃为古代核子战争。
* 第四个太阳纪——宗德里里克 Tzontlilic（亚特兰蒂斯文明），也是在火雨的
肆虐下引发大地的第四次灭亡。

玛雅人的预言的最后一章，大多是年代的纪录，而且这些年代的纪录如同串通好
的，全部都在“第五太阳纪”时宣告终结，因此，玛雅人预言地球将在第五太阳纪迎向
完全灭亡的结局。当第五太阳纪结束时，必定会发生太阳消失，地球开始摇晃的大剧变
，根据预言所说，太阳纪只有五个循环，一但太阳经历过5次死亡，地球就要毁灭，而
第五太阳纪始于纪元3113年，历经玛雅大周期5125年后，迎向最终。而已现今西历对照
这个终结日子，就在西元2012年12月22日前后。

前面都是引子。我这里要提出的，是一种科幻的思路：

先从各类宗教民族传说的神灵奇迹说起——为什么世界的各个民族各个地区都有如此类似的传说神话神迹？难道纯粹是凭着人对超自然能力的幻想？各种的史记证据遗迹，汇总起来，都指向一个极大的可能性，人类文明确实经历过若干的超自然力量事件。

假设某一些神迹传说真实的话，按照剃刀原理，更简单的推断就是，不仅仅是某一些，而是大量的神迹传说确实是真实的。于是，暂且不管根源，就问一个问题，为什么总是地球？如果还没有回答这个问题的思路的话，回想一下地球文明的发展，在已知的40亿年的历史中，就只有很短的一点点，才是我们已知的人类文明。40亿，几千年，仔细想想，人类文明完全就是一下子蹦出来的！你也许继而会想到，好像也有传说，atlantis文明，好像的确也有过很多的局部的人类文明突然一下子消失了。另外一个事实是，考古资料里，关于人和古人的断层，在几万到几百万年之间，似乎也太大了。你不由得只能推测，似乎人类的文明，就是一层层的片段!

想想，中国神话里，有女娲造人。基督教里怎么说人类的诞生呢，“上帝按照自己的模样造人”。一个星期内，世界万物就诞生了。人类文明是如何终结的呢，大审判，终结日。为什么上帝要创造人类文明而又要终结它，不合理啊。为什么上帝的样子也是人？如果上帝的样子也是人，难道上帝本身不也就是人吗？如果上帝本身就是人，而又被普通的人认为是上帝，只有两个可能：上帝是未来的人类，或者是平行世界某一族的人类。

首先考虑族论，假设人有多族，分布在不同的平行世界。当我们这个世界的人类文明毁灭后，另一个平行世界的人类文明遣使者来重新点燃着一个旁族的火种。而他们又知道，最终这一族也是会终结的。既然如此，为什么，他们要这么麻烦的穿越过来，重新创造另外一个人类文明？还不明显吗？因为他们也知道，他们所在的世界，文明最终也会终结，为了延续文明的火种，他们能做的，就是穿越到另外的时空(平行世界)去创造新文明的火种。这样一来，上帝在创造我们这个世界的时候，也其他的无数时空中，创造了无数的人类文明的火种，指望着，其中的某一族文明能在终结之前进化到极高的地步，去新的时空撒播新的火种。

既然认为了，上帝就是来自更高的人类文明，该文明至少需要满足一个条件：在时空科学技术上，已经能够随意的掌控时间和N维的空间。也许你会想到，其实你说他们是来自未来也好，来自和我们平行的世界也好，其实都没有区别。也许对他们来说，时间尺度上的前后穿越，本身就只是在平行世界的时空体系中跳跃的一个特例而已。而我们历史上所记录的之如玛雅文明，atlantis文明，极可能是当我们这个空间中，先进文明在我们之前播的几次种。

现在有一个逻辑上的疑惑了，既然更高级的人类文明练时空科学都已经如此炉火纯青， 为什么无法避免自身被终结的命运？非得要跑到别的时空去留下火种？先来想想这个终结是怎么个终结法？地球被摧毁？对于一个掌握了时空技术的文明来说，地球被毁灭，实在是比1+1更简单不过的问题。完全可以很坚定的推断，这个大终结的方式，必然是时空性的！诸如时空坍塌。你可能要问了，他们那么厉害，大不了集体移民到另外一个时空(平行世界)，他们既然能去播种，还不能集体移民吗？也许，关键就在于，一个我们这个文明永远无法弄明白的奥秘，生命。在他们的文明中，必然意识到了，生命是于时空所联系的，不光是生命，你要知道，如果从纠缠的角度描述生命，所有的有意识生命都是纠缠在一起的，所以，更可能的，整个的文明的生命都是一个和时空命运关联的 -- 即便他们移民来我们的空间生儿育女，而他们的子女却也是和他们整个文明整个时空所关联的 -- 当他们的时空走向终点，整个文明彻底终结。

那么，为什么基督教的记录中，并没有像玛雅的预言一样，明确告知了我们终结的时间。上帝是一个人，还是一些人？从各个地区的不同宗教民族种族等情况看，各种不同的神的传说，极可能的，造物主不止一个。为什么一个高级文明来的造物主还不够？为什么上帝告诉了基督徒世界终有大审判而不告诉具体时间，但是玛雅人却能预言到2012年12月22日？这说明的，曾经有多个高级文明来到我们这个时空，一些文明的造物主，试图别的造物主的做品，进行一定程度的修改或者添加！留下圣经的上帝所来自的文明，也许尚未能进化到能够准确计算时空命运的方程的地步！另外一个更高的文明路过我们的时空，他们也许足够的进化能够判断出毁灭的时间，告知他们觉得当时处于文明顶峰的擅长天文数学的玛雅人，对玛雅人寄以希望，希望他们最终会发展到足够高的地方，在2012年之前能够掌握时空穿越。

最后一个大疑惑就是，WHY？为什么人类文明的延续要通过时空穿越的形式，为什么每一次都只能从头开始，为什么非得这么错综复杂？为什么再高度发展的文明，也无法逃过时空终结？为什么人类文明就不能连续，必须要终结/重生/终结/重生的无限轮回？

最后的答案就只有一个了，一个有序的宇宙，因为人类文明在掌握时空穿越后，造成的时空悖论，最终在整个宇宙尺度上造成了灾难(这个尺度包含了所有可能存在的平行世界)，最终宇宙演化为混沌的状态。。。

之前做了一些回溯的题，比如打印permutation，打印任意n对括号等等，都是瞎蒙的。

还真凑巧，上午做了打印n括号的题，下午就看见有人说到回溯法，想想自己还没系统学过这个，找了本基础的中文算法书来看了看，虽然书上讲的很浅显，发现自己貌似瞎蒙还蒙对了思路，呵呵。正好凑巧的是，刚刚看了一点点，网上就有个人问怎么做Vertex Cover的问题，正好让我来做做练习。

1. 打印任意合法的n对括号：

void printParenthes(int N, int left, int right, stack<char> &stk){
    if(left == N && right == N){
        printStack(stk);
        return;
    }
    if(left>right){
        stk.push(')');
        printParenthes(N, left,right+1, stk);
        stk.pop();
    }
    if(left < N){
        stk.push('(');
        printParenthes(N, left+1, right, stk);
        stk.pop();
    }   
}

2. Vertex Cover（NPC问题），图G中找一个顶点的最小子集，覆盖图的所有边。

int current_k = N; //global

void VC(int k, int start_v){
    if(all_edge_covered(G) && k<current_k){
        current_k = k;
        return;
    }
    if(k == current_k - 1) return; //剪枝
    for(; start_v<=N; start_v++){
        if(!edge_list[start_v].empty()){ //剪枝
            list<int> temp_edge_list = edge_list[start_v];
            clear_edge(start_v,G);
            VC(k+1, start_v+1);
            if(curent_k == k+1) return; //剪枝
            reset_edge(start_v,temp_edge_list,G);
        }//endif
    }//endfor
}//endVC

想了想，其中的for循环其实是不必的，对于解空间树是子集树的问题，只需要考虑《当前顶点“选”“不选”》两个情况

改进后的算法是：

void VC2(int k, int start_v){
    if(k<current_k && all_edge_covered(G)){
        current_k = k;
        return;
    }

    if(k >= current_k - 1) return; //剪枝
    if(start_v == N) return;    //没有下一个顶点了

    if(!edge_list[start_v].empty()){ //如果
        list<int> temp_edge_list = edge_list[start_v];
        clear_edge(start_v,G);
        VC2(k+1, start_v+1);
        if(curent_k == k+1) return; //剪枝
        reset_edge(start_v,temp_edge_list,G);
    }//endif
    VC2(k, start_v+1);    //不选start_v这个顶点
}//endVC

第一题。给一个数组a[1]到a[n] : 例如 1，2，3，4，5，6

现在随机生成a的一个permutation: b[1]到b[n] （例如：3 1 5 2 4 6）

问, a和b数组在每一位上都不相同的概率是多少？假设a本身没有重复的数

我的解法：

主问题：F(n) = 给定长度为n的a数组，b数组有多少种取法

辅助问题：结果用f(n)表示。 b数组是{1….i-1,x,i+1…n}的一个排列，其中x!=i，满足a，b在每一位上都不相同，有多少种b？例如，a = 1,2,3,4; b是{1,2,5,4}的一个排列。换句话说，组成b的元素中，有且只有一个数不在a中。

这样定义了F(n),f(n)后，很显然有递推关系：

F(n) = (n-1) * f(n-1)    //解释：第一位有n-1种选择，任意一种选择后，问题变为一个 n-1规模的辅助问题

f(n) = F(n-1) + (n-1)*f(n-1)   //情况一，在b数组的第i位置填入x，考虑剩下的n-1个位置，即是一个n-1规模的主问题；情况二，i位置填入非x的数，考虑剩下的n-1个位置，即是一个n-1规模的辅助问题。

简化一下表达式就是:

F(n) = (n-1)(F(n-1)+F(n-2))

第二题，一个binary tree，逆序打印BFS序列。不能同时用两段存储空间（不同时用queue和stack）

解法，用一个vector（array)模拟queue+stack。queue的push操作即vector的push_back，等效于q.pop()+stack.push()的操作则是，vector的index往前走一步！最后把vector从尾到头打印一遍即可。

第三题，网上看的答案，超级巧妙，生成一个0-255 二进制数有多少位是1的查询表

static int BitSetCount256[256] =

{

#define B2(n) n, n+1, n+1, n+2,

#define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2),

#define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2),

B6(0), B6(1), B6(1), B6(2)

}

不得不说，这个宏递归的方法用的太妙了！！！

附带赞一个巧妙度略低一些的计算二进制数有多少位1的方法

int bitSetCount(unsigned int i){
int c=0;

while(i){

c++;

i &= (i-1);  //这一步很赞，每次保证清除最低一位1；

}

return c;

}