Home

一晃十一长假就要结束了，校园招聘也将进入宣讲和笔试密集的时段。经过一个月的笔试和面试，终于有找工作的状态了，少了些急躁和不安。一方面，应聘过程中的提问可以了解自己的能力，对问题的思考深度和掌握程度。另一方面，一次次的职位选择使自己的方向定位更清楚些，然而，还是不能明确自己今后可能从事的方向。隐约觉得这已不是重点，做好手头的工作不就OK了，No matter what it is. Just do it as well as you can.

如果机房马上要关门了，或者你急着要和MM约会，请直接跳到第六个自然段。

我们这里说的KMP不是拿来放电影的（虽然我很喜欢这个软件），而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A= I’m matrix67 ，字符串B= matrix ，我们就说B是A的子串。你可以委婉地问你的MM：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？”

两天的北京之行结束了，感谢在百度的师兄们(xx，hj，wzg)和几位新老朋友的热情接待！整个行程很顺利，玩得很HIGH，印象深刻！本来想去 ym 下以前在Linux版时发现的一个大牛 lnzju，xx 师兄说就坐在他旁边，我就是看了他的帖，才开始使用 Arch Linux 的。后来因为两兄师兄连续有小组交流，晚上聚餐时间居然拖到了八点，百度人工作都很奋啊！太晚了，没有时间去见大牛 lnzju ，如果以后有机再去 ym 下。

中午和 wzg 师兄一起去公司食堂就餐，然后在他工作的地方呆了会儿，晚上也是在他那睡觉，早上一起吃早餐，可以说比较完整地体验了一把“北漂”生活~

第二天去清华和北大转了下，没有去其它地方。主要考虑下午7点的火车，可能时间比较紧。中午 wzg 师兄请客，去北大旁的“一木”烤肉吃自助，三个北方人、一个在北京呆了五年的南方人，还有我一个南方人，这就是一个北方风格的聚餐。吃得很给力！（再次感谢 wzg 师兄的热情款待）

通过师兄们的介绍，对百度、对技术、对工作有了更深入的理解和新的认识。在实习面试中，也发现了自己的一些基础知识还不够扎实，需要努力。接下来就要准备九、十月份的校园招聘，这次面试是一个不错的开始。

大二下学期时，在徐老师的提议下，负责创建了校内的数学系论坛。因讨论数学的人本不多，更何况是在线讨论，所以论坛的人气一直很低。后来因一些老师的宣传和参与，及一些热心同学的加入，论坛也讨论气氛有所提升，十分感谢他们的支持！现在自己能呆在学校的时间不多了，又没找到可以接班的人，同时校内新创建了一个 quot学习网 ，提议合并数学论坛，数学系论坛就此关闭。快三年了吧，兴奋、失落、感动、遗憾，还有回忆~

最近在准备面试，遇到了一些概率题，所以重新思考bbs上的一道概率题。

题目

两个人甲和乙竞选，统计结果是甲p票，乙q票（p q）。问在计票过程中甲的得票数始终大于乙的得票数的概率是多少？（由原校内数学系bbs的ZXY同学分享）

两个回帖

第一个没看明白，先记录着，第二个解答比较巧妙易懂，第三个是网友google到的

ZXY：

结果是(p-q)/(p+q)
由这道题可以引申出一个比较深刻的问题，具体我也说不清楚，反正就是这种题在历史上的意义比较的大。
我想了一种解法，不知是否重复了前人的。
显然这个概率是p,q的函数，不妨设为P(p,q),容易知道p<=q时,P(p,q)=0
易知这是古典概型，所以P(p,q)=r(p,q)/C(p+q,p)（我用C(p+q,p)表示组合数，p+q是下标）
下面考虑r(p,q).显然p<=q时r(p,q)=0.
可以证明r(p,q)=r(p-1,q)+r(p,q-1)
由此可以得出P(p,q)与P(p-1,q)和P(p,q-1)的关系。
下面对p,q使用跷跷板数学归纳法，就可以得出上述结论。

席Andy：

这个是典型的xxx折线问题啊（忘了叫啥了）。。我记得在高中老师的组合分析里面看过
那个题是卖5块钱的票2n张有n个有10块的和n个有5块的人要买 问卖的过程中不缺零钱的概率
一个坐标系，开始计票，如果甲得票，就画一条(0，0)到(1，1)的折线如果然后乙的票再画下来斜率是-1到(2，0)
以此类推。所有的情况就是从(0，0)到(p+q，p-q)的折线。所求情况是这条折线始终在y=0之上。
所求情况的补集就是折线会碰到y=0的情况。先假定第一张票就是甲的，而第一张票是甲的的概率是p/(p+q)
然后这个方法的精髓就在这里，把所有这种会碰到y=0的折线都在第一次碰到y=0之后的部分关于直线y=0对称过来，
就唯一对应于一种从(1,1)到 (p+q,q-p)的折线。
这种情况共有 C(p+q-1,p)。总情况有 C(p+q-1,p-1)
所求概率就是 p=[1-C(p+q-1,p) * C(p+q-1,p-1) ] * p / (p+q) = (p-q)/(p+q)
注：这里C(x,y)表示组合数，从x中取y的组合。

就是说首先必然到(1,1)点这个概率是 p/(p+q)
然后事件总数是从(1,1)到(p+q,p-q)
所有满足接触y=0的折线都是不满足题设情况的
将这些折线第一次接触y=0后面的部分 关于y=0对称
则终点就变成了(p+q,q-p)然后计算从(1,1)到(p+q,q-p)的走法数 需要总共走p+q-1次 向上走的-向下走的=q-p-1
得到向下走了p步 于是C(p+q-1,p)
同理总数是 C(p+q-1,p-1)

因为票都是无差别的，取票过程也是随机的，所以这个问题也就是甲得票一直领先的概率，但是一个一个列举出来确实会累出人命的。我们不妨来简化一下，假设有6个人投票，甲4票，丙2票。甲的票我们记做A，乙的票我们记做C，现在我们看其中的一种排列，AAAACC，按这个顺序出票的话，甲是一直领先的，那如果我们把这个直线顺序弯起来，做成一个环形顺时针走，1号是第一个A，那么从一号开始出票就是AAAACC，从2号开始到1号结束就是AAACCA，接下来还有AACCAA，ACCAAA，CCAAAA，CAAAAC，一共六种不同的出票顺序，这其中只有AAAACC，AAACCA两种情形，也就是从1号和2号票开始，甲才能一直保持领先。这个数据有没有通过计算得到呢，我们不妨在这个圈子中把相连的AC划掉，因为这其中第一个A不起作用，刚加上就被C又超过，对甲一直保持领先没有贡献，同样第二个C也是没意义的，因为如果在此之前甲领先，那么与他同时出现且在前面的A也抵消了C的作用，C对甲无法一直领先也没有贡献，所以同时消除不影响结果，于是这个圈子里（AAAACC）的4号和5号两张票消失了，圈子简化成AAAXXC，XX代表原来那个AC的空位，这时候3号票和6号票也相连了，于是再次消除3号，6号，于是圈子变成AAXXXX，那么从1号和2号开始的两种顺序就是甲的得票一直领先，也就是A的总数一直大于C的总数的情况，不难得知这个可能的情况总是A-C那么多。

不过很可惜，AAAACC以及衍生出的另外5种情况并不是全部的可能情况，我们还可以排出AAACAC这样一个圈子，并且可以分别从2号，3号一直到 6号票开始顺时针转，找到另外不同的五种排列情况：AACACA，ACACAA，CACAAA，ACAAAC，CAAACA，不过采用第一个圈子里的消除法，我们同样可以找到仍然是只有两种情况，也就是从1号和2号开始的两种情况能够保证A一直大于C，甲一直领先乙。这两个圈子里所有可能的情况都是6，也就是总的票数，所有甲领先的可能情形都是2种，也就是A-C的差。

当然，也许会注意到另外一种情况，就是AACAAC，这样的圈子实际上只有三种不同情况，从1号开始和从4号开始是一样的，从2号和从5号也是，3号和6号也是，这个先放一边，我们还是用消除法，变成了AXXAXX，也就是说能够保证甲一直领先的开票方式是从1号票开始，或者从4号票，但是实际上1号票和4号票的顺序是一样的，是同一种情况AACAAC，所以这个圈子里保证A C的情况只有一种，那么这个圈子里甲领先的概率就是1/3，其实跟2 /6是一样的。现在实际上我们已经枚举了所有的情况，三种圈子，6+6+3种排列方式，其中有，2+2+1种甲领先的情况，不管这个圈子变得多么的大，也不管会出现多少不同的圈子，情况都和这6个人构成的三个圈子类似，可能的概率就是(A-C)/(A+C)。

如果有过生日，在家时生日是按农历的，在同学之间又按公历的，但户口上的时间也不对，所以成了没有明确的生日时间。既然没明确时间，本可能安排在前天的生日聚会，因老弟的到来而推迟过今天的了，就当给老弟接风，同学小聚吧。

实习的公司蛮贴心，赠送本月过生日的员工蛋糕消费券，丹比出品，挺精致。比较难忘的是，老弟给我点了份“长寿面”和朋友们的祝福和班长的给力。在蜡烛灭的那刻，我许下了一个愿望，呵呵，有些缥缈，愿能实现。（信春哥，得。。。）

开心，同时想起了大学过的第一个生日，一个意外的生日~ 而这次则是一个印象深刻的生日！

有一段时间没写技术相关的日志了，倒不是这段时间接触的技术没了，反倒是在狂补一些技术知识。俞学俞是发觉有更多东西需要学习，有些心得，但没有时间整理，就先整理下旧工作吧，也算总结下。今天给出的是非真实感图形学（NPR）课的作业，一篇PG09的关于图像视频风格化的文章—— Image and Video Abstraction by Anisotropic Kuwahara Filtering 。整个算法实现比较简单，理解时可能得花些时间好好学习下什么是结构张量(structure tensor)，主要参考引文中的一篇博士论文—— Nonlinear Structure Tensors 。

附源代码 ，放在bitbucket上：这里

说明 ：1. 整个算法没整理成一个类，有些分散。 2. 原论文提到可以用Shader（GLSL）实现，速度可以实时，因时间紧了些，我只简单用CPU实现，慢了N倍。。。因算法本身具有良好的并行性，改写难度应该不大，如有人要实现可以试试。3. 整个算法是由C++接口的OpenCV写的，因C++相对C复杂些，特别是泛型编程相关的。

大一时在图书馆的“新生推荐丛书”中找到了《富兰克林自传》，读后摘抄了一段他的“一个达到完美品德的大胆而费力的计划”到记事小册本中。摘抄它可能是由于高中时摘抄习惯，而摘到随身带的记事本上则可能是觉得这个“计划”有一定的可行性，也比较符合我的价值观。像其它“三分钟热度”的宏伟计划一样，很快我就把它忘得干净了。直到今年（研一）寒假回家，我在弟弟的旧钱包中发现了那张纸，应该是老弟把它撕下来了放到了自己的钱包中。我怀着像看到小学课本一样的心情（怀旧、回忆、反省、有趣）重新阅读了它，一些条款可能与时下的流行“计划”相左了，不过总体一致。同时，它还是符合我的价值观，所以重新摘抄了一份（老弟的那份就给他留着吧，虽然可能他也已经遗忘了）。下面是“计划”的内容，解释部分不全，只写下我记录的部分：

一个达到完美品德的大胆而费力的计划：

一、节制。食不过饱；饮酒不醉。

二、沉默寡言。言必于人于已有益。

三、生活有秩序。每样东西应有一定安放地方；每件日常事务有一定的时间。

四、决心。当做必做；决心要做的事应坚持不懈。

五、俭朴。用钱于人或于已有益，切戒浪费。

六、勤勉。不浪费时间；每时每刻做有用的事。

七、诚恳。不欺骗人；思想纯洁公正；说话也一样。

八、公正。不做不利于人的事，不忘履行于人有益而又应尽的义务。

九、中庸适度。避免极端；应得处罚当容忍。

十、清洁。身体衣服和住所力求清洁。

十一、镇静。勿因小事或普通的不可避免的事故而惊慌失措。

十二、贞节。不常兴房事。

十三、谦虚。

反省大学的这几年，对比下来，自己几乎没有进步，反而在一些方面倒退了，比如诚恳，比如谦虚。对人对事诚恳自不必说，对自己诚恳应该也很重要吧。随心不容易，难在自知，难在细心观察体会生活。

附：

《富兰克林自传》 *

最近在准备工作面试相关的东西，还有实习。一直以来总觉得一些东西距离自己比较遥远，可以心安理得地过着自己的学生生活。现在，就像是自己被推到了一个路口，一定得做出一些选择。我想是时候做一些准备和一些决定了。

昨天，百无聊赖，在人人做了个EQ测试，果然比较低，分析也很中肯。虽说有点算命老先生的解说，总能从中找到一些模糊的“命中点”，但是还是反映了一些问题。分析走过来的这些年，形成我现在这个性格的关键时期应该是从高中开始的吧。初中时和很多同学关系都很好，个个都是铁哥们、好朋友，然而到了高中，可能因为学习压力大了，几乎把所有的时间都花在学习上，与他们的交往少了，突然感觉与他们有了陌生的感觉。

高二时认识了好友，才，他当时是一个电脑迷，每天都在滔滔不绝电脑种种、网络种种，使我也疯狂地喜欢上了电脑。由于平淡的学习生活添加了一个新的项目，去书店看《电脑爱好者》《大众软件》《电脑报》，同时还有科幻小说、小四韩少等的书（也是受才的影响）。加之对理科的喜爱，我把更多的精力放在了对技术的追寻上，而忽视了生活中的很多东西。使这个问题变得更剧烈的是，大学误选了一个貌似计算机方向的数学专业——信息与计算科学，从大一到大三过着与高中无异的生活，来回自习室与寝室之间，基本保持着高中的生活状态。直到大四进入实验室，在这里，我从师兄师姐及同学那体会并学习到了很多东西，既有学业上的，也有生活上的，两者都使我快速成长。

之前就听到一个说法：太GEEK了不好，我当时不以为然。我就爱GEEK，GEEK有什么不好。

There is no fault about the geek, it’s a fault to be a geek of my kind.

一直觉得技术可以给使自己更强，更自信，后来才渐渐发觉，成长不仅仅需要技术。也许GEEK的EQ普通不高吧，不过这不应该是GEEK的属性，而应该把它看成是GEEK们容易遇到的问题。快乐GEEK，健康生活！（有一位成功人士的EQ很高，想成为他的校友吗？请 点击这里 ）

关于工作面试准备。暑期开始时给自己制定了一个复习计划，现在也实施了一部分了。完成进度如下：

• More Effective C++ (60%)
• 数据结构与算法分析C语言版（50%，代替算法导论） 并行编程，看了Introduction to Parallel Computing ，准备看POSIX Threads Programming *
• 看了一些搜索相关的基本知识及一些面试题

接下来准备先把实习的项目完成，期间继续原来的复习计划。因在实习和准备面试，实验室这边的课题基本停止了，准备几些天和老大商量下，开始看Paper。

现在我对自己的要求就是，决定做的事，尽可能着手去做，不要犹豫！