0705近况

    实习的日子显得比在实验室繁忙了许多，也更加有压力，每天早上8点起床，坐两站的公交，三站的地铁才能到达公司，期间还要走个十来分钟的路，路上就耗掉了40-50分钟，这就是北京吧，太大了，到处都是忙碌的人，公交上是操着浓重北京音的售票员，地铁上是形形色色的it民工，租房子的地方则大都是外来的打工者。
    最开始的两天比较不适应，首先是生活，包括，食，住，行， 在三哥的宿舍窝了几天，然后就是公司的编程技术之类和我以前的差别不小，还好业务上不是差别很大。所幸的是，刚到公司就赶上了公司一季度的building，去南戴河玩了一下，跟同事们熟悉了不少，还有辉帮忙找到了房子，虽然没有想象中的好，也还满意，价格也不错。
    工作的详细内容不方面透露，但是总之百度里面的项目跟进的相当不错，文档做的也好，而且讨论的时候非常热烈，对于我来说最好的就是周围有很多牛人可以去请教，学习东西啦。百度大厦里面的服务非常周到，包括休息室，茶饮，健身房，球场，图书馆，健康中心，淋浴室等等，可惜我还没怎么转过，准备明天去图书馆和健身房cc。
    当前需要对自己提出更高的要求，这个节奏显然是上学期间不可以比的，不会给你单独学的机会，只能自己挤出来时间，边学边用，也算是一种非常好的锻炼吧，总之加油干吧，开始的时候可能会困难点，但是一切都会好起来的。

百度实习offer之路

    从这学期开学就在想着实习的事情，到现在终于拿到了百度的offer，对于我自己来说，是个莫大的惊喜，总觉得自己是运气不错，基础不扎实，进去之后一定要加倍努力，修炼自己。
由于我是内推的，所有简历就直接过了，没有参加后来统一的笔试，之间进行了三轮面试。简单说说我的这个流程吧。
    第一次电面，0526百度电面感觉非常之不好，因为我觉得问题回答的都是零零碎碎的，哪知道稀里糊涂就过去了。
    然后居然接到了二面通知，于是开始准备二面，基本就看看算法导论，别的搜索相关的东西一时也准备不来，0603 百度二面虽然问的问题比较多，而且更加棘手，但是我的感觉还不错，可能我的想法比动手能力更加突出的原因吧，当时问我有什么优势的时候，我就说的是想法，晕，其实这个不靠谱，感觉，但是没别的说的了。
    面试完了还没自己想呢，第二天晚上就收到了百度的三面通知，说是下周一，于是突然就紧张起来，因为二面其实感觉是运气，但是进了三面就感觉自己非常接近，而且不能大意了，于是自己的压力就大了起来。很担心自己被咔嚓掉了，于是周末两天的准备也不怎么太好，周一（6.7）早上焦急等待电话，到了快10点打来，差点以为不打了。三面没有想象中可怕，让我虚惊一场，和算法等关系很小了，主要是谈做过的项目，体会，经验等等，估计就是之前面经上说的rp不差就会pass的吧。但是面完了依然担心。
    三面的面试gg说两周内hr会联系我，准备慢慢等待的，结果，昨天（6.9）hr mm给我打电话了，说我被录取了，激动了下，然后让我确定了实习时间，今天和她联系。刚才电话确定了，可以去实习，然后邮箱收到了百度的正式实习offer，至此繁忙的找实习告一段落。
    下一步，交接实验室工作，杀向百度大厦。
    ps：祝福各位朋友，同学在找实习的路上，好运相伴。

0603 百度二面

    来电话之前很担心，但是电话来了，说了一会，就感觉心情平静下来了，面试的gg问我关于我自己的强项，我说在于头脑风暴方面吧，大概对一个新事物的想法和 策略等。其实我感觉自己别的方面貌似是不是很突出，算法可以，搜索方面懂点，但是只写过爬虫，没有写过倒排表，以及排序算法等，主要是因为做的面广，但是 不够深入吧。以后有机会要加强一下吧，另外今天遇到了不少和概率和统计有关的问题，以后需要加强。面试持续了一个小时，比上次的要长。
    期间问得都是和百度商务搜索遇到的问题相关的，可能会涉及技术细节，我就不详细说明了，给排序和评估各种算法有关。面了很长时间，大约有4个问题要我去解决的，回答得感觉不错。
    面试到此为止，然后他让我问几个问题，我问了是否有师傅带（有），以及进去是做工程呢（锻炼机会不少），还是能接触 更多算法，策略，还有就是是否通过是不是都有通知（有），回答的都很热心，以及满意，感觉面试过程比较happy，bless能进入下一轮。

6.8阿里云二面

声明：无保密协议

    这次面试的gg比较直接，上来就问了我做过的digO系统,问了下这个系统使用，想法，语义Web的一些问题，这个忽悠能力我还是有的。然后如何聚类的问题，之前我负责调查聚类算法的特点，因此还是了解点。聚类是我师兄实现的，我只是知道如何去做，基于什么想法，所以就简单的说了下想法，现在想起来忘了和他说不是我实现的了。。。不会说我不忽悠他吧，下次遇到类似情况记得说明。期间着重问了时间复杂度，这个我还是知道的。期间过程比较长，不赘述。
    完了就开始问如何找到第k个大小的数，貌似以前看过，但是感觉今天没有热身，面试没有感觉，一时没有太好解决办法，说最基本的是O(kn)，然后说了个k=2的时候的解决办法，貌似也不是很好，然后他又问了最好情况的复杂度，要具体数字。后来在老曹drizzlecrj的第 (前)k大数问题看到比较了这个题目的解法：

     所谓“第（前）k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第（前）k个数的问题。
解法1： 我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(n*logn + k)。
解法2： 利用选择排序或交互排序，K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)
解法3： 利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分S_a和S_b。S_a中 的元素大于等于X，S_b中元素小于X。这时有两种情况：
1. S_a中元素的个数小于k，则S_b中 的第k-|S_a|个元素即为第k大数；
2. S_a中元素的个数大于等于k，则返回S_a中 的第k大数。时间复杂度近似为O(n)
解法4： 二分[S_min,S_max]查找结果X，统计X在 数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)
解法5：用O(4*n)的方法对原数组 建最大堆，然后pop出k次即可。时间复杂度为O(4*n + k*logn)
解法6：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆 顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)
解法7：利用hash保存数组中元素S_i出 现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)

详细内容参考老曹blog。
    然后就是问我有什么问题，我就问了他们做的东西面向的用户，阿里云的氛围和文化，然后是对实习生的要求以及是否安排师傅等等。

0529 微软笔试

声明：笔试有密保，因此内容不透露，谈一谈总体的感觉。

1. 纯英文考题，分客观题和主观题两部分。
   
2. 知识面覆盖广，包含计算机系统，数据库，网络，c++编程等
3. 题目比较看重细节，需要扎实的编程基础，靠看面试宝典和编程之美等基本歇菜，要靠积累，泪飘，积累不够
4. 纸上写代码能力，代码量不小
5. 深入理解题目，不能只看表面，首先分析透彻，再开始。我被一个例子给忽悠了，其实只是个特例，而不是普遍，要抓住本质。
   

0526支付宝电面

    今天收到好几个面试相关的电话，最终又面了个支付宝。ps：无保密协议
    话说，自从我面了百度，别的面试哥们就不怕了，即使是挂了，也是笑着而死。今天的支付宝面试很happy，面试gg还让我先去解决了下个人问题。
    上来是例行的自我介绍（这个我居然没有准备过，建议准备），然后开始面试我笔试的情况，其中一个是我当时没有理解的题目，然后在他的解释下，我才明白，面试过程和他交流还是蛮重要，结果我提出了一种解决方案，而且也考虑到了部分细节，感觉还行。中途杂的滤过，还有一个就是跟一个选择题有关的，说假如我对这个不知道，该怎么去解决，我说了，google，请教周围人，然后自己写程序验证（这点貌似他没预料到），最后想不起来了，他说看源代码，我，我，我把它算到google里面了，哈。还有其他的印象不深。
    然后是谈兴趣，我用什么语言，都学了哪些东西，如实说，不敢吹牛，交谈比较愉快。问了我能不能接受朝9am晚6am，。。。最后又是例行的有没有问题问他，这个必须问啊，主要问了具体的工作内容，以及实习相关的东西。基本这样，再见的时候还客气了一会。总之这个面试官给人感觉很好，过程很愉快。说一周内会给结果，我喜欢给通知的公司，即使被咔嚓了，也喜欢。

0526百度电面

    结局应该是挂了，很惨痛。没有保密协议，于是我就分享了吧。

    11：00打来，一个gg，也是很客气和和蔼。

    一上来是说一下自己的编程开发，经历，bla bla，然后就开始进入主题了。先是问我做过的那个系统的问题，问得很细，有的部分已经忘了，而且有部分是师兄做的（不过我和他说了），不过核心的东西算是说出来了，具体的算法思想也有。

    接着他问我的专业课，说了算法设计，机器学习，数据库，网络等等，于是问我对什么感兴趣和擅长，我想了想说搜索，其实我的搜索是网页的那种搜索，但是他理解的貌似是搜索算法，后来师兄和我说这种情况我应该说检索，哎，学术不精。于是杯具就开始了，问的都是搜索和最优化的算法等等。其一是某人从A到B，可以步行，坐公交，打的，代价是等待时间和金钱，建模求最优策略。我问是不是比如，走一段，坐一段打一段这种类似的策略，他说，就简化吧，采取一种策略，然后我就给了个线性的方程，a1 * t + a2 * m，说求最小值即可，他又说了如何表达我的最优化方法，我说就用这个式子吧，然后我又问题此类问题是不是一般都是线性规划，他说是的，然后完了，期间细节略。

    然后是那个经典的拾麦穗故事，不能回头，也不能看到下面的，如何确保自己找到比较大的麦穗，100米。呃，我又深思了，yy了一种序列（他说我的不叫分布，分布是根据大小的很坐标，不是我的一步一步）的方法，前30米，观察，中间30米验证，最后40米应用，然后中间他问的很细很细，遇到某种情况如何如何，不要用通俗语言描述，用具体算法，代码来描述，很严格，最后终于挣扎完了。然后我问他如何解决，他说只要拿出一个比较说得通的算法，完整，严格即可，最优化的有，但是很难。

    接着让我提问的，我问的商务搜索的东西，不泄露了。

    感觉面的过程很严谨，对答案要求很严格，要建模，然后详细，完备的算法。因此对自己的一个想法一定要有一个比较好的框架，首先要基于什么想法或者模型，然后详细，完整地解决一个问题的流程，如何达到最终目标。


    基本这样，中间有略过，面完感觉就是歇菜。。。

5.21阿里云电面

    话说这是我第一次面试，献给了阿里云，不过没有面对面感觉就是不一样，我感觉电话让我更舒服点。
    面试官很亲切，听声音是个小伙子，交流过程比较轻松。
    上来就问我关于爬虫的事情，因为我在简历上写，曾经实现过一个爬虫，说了下基本的实现流程，注意点，遇到的问题，如何解决等等，假如他不是搜索方向我想应该足够了。
    接着问我数据结构和算法如何，我说还行，然后就问了快排，这个不能不会，不然肯定被鄙视。
    然后问我如何比较两个函数的相似程度（之前貌似还有一个问题，忘了。。。），我说应该从功能上，以及从文本上来两方面分析。功能上就是输入输出的比较。文本上我先是想了个虚拟文档的做法，这个是自然语言处理还有网页搜索方面的，他问我效果会如何，我说可能会不太好，因为丧失了位置信息和结构信息。然后又提出了，从声明的变量数目，分支结构的数目等方面的比较算法，都是不太有完整思路的。然后他让我比较两个字符串的相似度，我首选还是虚拟文档，汗，我只会这个了；因为我感觉最长子串可能不好用，然后他建议了一种方法，先找最大公共子串，然后其次，等等，我没太明白。
    然后问我用过的语言，我说java，c++，让我对比下，bla bla bla，Java的知识都没怎么问，直接问我c++了，可能是因为是c++岗位吧，我都忘了投什么岗位了。。。问了c++有什么默认的函数，构造，析构，然后问子类new的时候是什么过程，我说了半天最后想起来，可能也没说清楚，我google了个清晰的说法：转载自http://fafeng.blogbus.com/logs/17747724.html
/********************************************************************

C++构造函数调用顺序

1.     如果类里面有成员类，成员类的构造函数优先被调用；

2.     创建派生类的对象，基类的构造函数优先被调用（也优先于派生类里的成员类）；

3.     基类构造函数如果有多个基类，则构造函数的调用顺序是某类在类派生表中出现的顺序而不是它们在成员初始化表中的顺 序；

4.     成员类对象构造函数如果有多个成员类对象，则构造函数的调用顺序 是对象在类中被声明的顺序而不是它们出现在成员初始化表中的顺序；

5.     派生类构造函数，作为一般规则派生类构造函数应该不能直接向一 个基类数据成员赋值而是把值传递给适当的基类构造函数,否则两个类的实现变成紧耦合的（tightly coupled）将更加难于正确地修改或扩展基类的实现。（基类设计者的责任是提供一组适当的基类构造函数）

#include      #include      class A{ public:A{…} ~A{…} } class B{ public:B{…} ~B{…} } class D{ public:D{…} ~D{…} } class E{ public:E{…} ~E{…} } class C :public A,public B{ public:C{…} private:D objD_; E objE_; ~C{…} } int   main(void){     C   test;     return   0;   }

运 行结果是

A{…}//派生表中的顺序 B{…} D{…}//成员类的构造函数优先被调用 E{…} C{…} ~C{…} ~E{…} ~D{…} ~B{…} ~A{…}

对于全局对象（global object）,VC下是先定 义先初始化，但C++标准没做规定。全局对象默认是静态的，全局静态(static)对象必须在main()函 数前已经被构造，告知编译器将变量存储在程序的静态存储区，由C++ 编译器startup代码实 现。startup代码是更早于程序进入点（main 或WinMain） 执行起来的代码，它能做些像函数库初始化、进程信息设立、I/O stream产生等等动作，以及对static对 象的初始化动作（也就是调用其构造函数）；在main()函数结束后调用它的析构函数。

********************************************************************/
    说完这个就开始聊别的了，我对分布式算法的兴趣，我表示没有怎么接触过，不是很了解，兴趣还可以吧，然后说了发展前途不错，好多地方要用到。等等。接着我我谈假如能实习，实习时间怎么样，我说看老板之类的。最后让我问问题，我问了他们云计算的具体情况，还有实习期间能否间断去找工作- -。
    然后，然后就没有然后了，说过一段时间再打电话给我。
    我只好在这里bless了，bless啊！

阿里巴巴5.20日南大笔试

转自我的javaEye ： http://xusulong.javaeye.com/blog/672424
晚上18：30开始的宣讲会，我在18：10分的时候才知道，因为看见JLH的同学赶过来，硕士阿里有实习生招聘，于是匆匆赶往实验室，扫了下实习的岗位，更新了简历，迅速准备好，杀到就业指导中心（南园西侧）。

居然还拿了个奖品，期间发现自己简历职位有个错误，又回去修改了下。

宣讲会到20：20才结束，开始笔试，技术开发类的一套卷子，分公共题目部分以及java，c&c++，测试和系统分部分。我选择的是java，次选c&c++。

1. 公共选择题有一道比较有意思，是问5个平面最多能把空间划分成几个部分，和我之前遇到的10条直线能把平面最多划分成多少个部分。
2. 直线分平面这个问题我推导出来了，每增加一条线，最多可以被n-1条线分割，从而多出了n个平面。平面分空间的问题没有推导出来，但是让我猜对了，26。回来Google了一下，没太理解。
3. 其他选择题不太清楚了，还有一个merge sort的问题，我是理解的，但是代码写的不好，算法和复杂度给出来了。
4. 还有一道题，给n个数，以及一个数t，求出和为t的所有组合，如何5个数【1，1，2，2，4】，t=4，则组合为【[1，1，2]， [2，2]，[4]】，对n和t，给出个算法。我的做法是DP，首先找出一个，然后是两个a和b的组合，然后对n-1，和t-a以及n-1和t-b进行迭代，直至得到所有结果。
5. cache问题，淘宝用户数据比较多，每次用户来访问，需要从数据库取得用户信息，为了提高速度，在内存中缓存用户数据，设计算法，cache满的时候需要删除很久没有使用的数据：我的策略，采用LRU（Least Recently Used）思想来进行，用linkhashset，对每个用户有计数，记录没有有多久没有访问，新用户为0，其他用户每来一个用户+1，现有用户被访问的时候清0。
6. 淘宝数据存在不同服务器上，当用户访问不同商品时，需要从不同的服务器取得用户信息，设计策略来解决访问代价问题。这个不太懂。
7. 其他的忘了。。。等其他人补充