行者无疆 始于足下 - 行走，思考，在路上
创新工厂电面小记
其实我一直对这些明星公司抱有一种仰望的态度，像前几天的百度，已经很让我惊喜，给了我很大的信心。昨天的创新工厂电面，虽然自己被虐的比较惨，但是还是进一步明确了自己的方向，了解了自己的差距。
对开复老师，除了仰慕，更多的是一种敬重。老实说我并不觉得开复老师是个天才，我认为他能成功，有一部分原因是在正确的时间正确的地点遇到了正确的人。我从来就不相信“穷人的孩子早当家”，更多时候，良好的家庭背景条件，有眼光的父母亲情教育，宽容大度自由的义务教育和高等教育，是一个人成长成才的助推器。敬重开复，是因为这么多年他为帮助中国青年成长所倾注的心血。当然，少部分人在他背后说三道四，说他虚伪做作，对此，我只能说，这些小人连“虚伪做作”的资本都没有。
好了，废话少说，说说本次面试吧。面试的过程很简单，就是给你一套题，一个小时的时间，然后在根据你答题情况刨根问底。答题的网站是collabedit。大概是由于世界杯的原因，网络比较拥塞，刷了5分钟才刷出题目来。题目总共有22道，考的范围非常广泛，很能反应一个人平时的积累。由于不方便，所以我暂时不能把所有题目原数贴出。大概概述一下题目分布情况吧：
- c\c++基础题
- 双向链表插入
- 二叉树遍历（三种方式）
- 栈的基本操作
- 概率问题
- tcp和udp区别联系
- sql基础语法问题
- 概率问题
- 图论问题（好像是“三角形无关图”，就是求一个8个顶点的无向图中，不含三角形，那么最多的边有多少）
- 函数递归问题
- 编程序题目：给定一条直线(L: x=5)和一个定点序列a[n]，组成一条折线a[0]a[1]...a[n]，求这条折线与直线(L: x=5)有多少个交点。
- 设计模式(什么是Singleton模式，PHP如何实现)
- PHP和MySQL
- PHP中的_POST数组
- PHP中"==="和"=="两个操作符的差别
- 还是PHP
- 还是PHP
- 还是PHP
- JavaScript和iframe
- MySql: datetime和timestamp差别
- JavaScript和iframe
- jQuery: onload()和document.ready()
前面十道题目，除了两道概率问题，答得还算不错；第11道编程题目，我想到的是计算几何中判断线段相交的方法和问题，于是就用内积的方法写了个程序糊弄了上去。结果面试官告诉我说这道题目我只拿到了30%的分数。我一诧异，忙问个中缘由。他说这道题目考的不是线段相交。线段(L: x=5)是给定的，所以不用考虑的那么复杂，根本用不到内积这些东西，我说那就看a[n].x和5相比究竟震动了几次。然后面试官说如果两个交点相同，那么这两个点是算作一个点的。我一想，是啊是啊，是这个样子的。然后他说用怎样的方法可以去掉这些重复的点呢？我说简单啊，算出所有的点后直接排序不就好了。他说时间复杂度太高，让我优化一下。我想了半天也不知道怎么回答，他又提示我说哈希表怎么样？我哈希表用的不熟，转念一想，用哈希表的话，相同的点经过哈希函数映射确实可以“合并”。于是我慌忙补充下时间是线性的云云。
后面的题目我就束手无策了。对javascript和php，我只是听说，很早之前看过一些入门的章节，早忘光了。除了"=="和"==="是查了下手头的一本书简单写了下，其余的题目基本是空白，很是尴尬。面试官表示说你前面的十道题目答的都不错，编程题目不甚理想，灵活度不够，"=="和"==="是不是百度出来的？我说不是不是，也没有别人帮忙，寝室同学都不是计算机学院的。
最后他问我对这套题目有什么缺陷，或者自己有什么优点没有表现出来。我就说自己对linux还算了解，他随机给我出了一道题目：找出一个目录中文件名中包含hello, world的文件。我说用find就行，find . -name "hello, world"， 他说不对，我想起来还得加一个recursive的参数。然后我又讲到了自己实验室的项目，他听了下又给我出了道题目：如何在iphone上面写一个帮助用户挑西瓜的程序。我犹豫了下问“iphone有没有办法称出一个物体的重量”——好蠢的问题……然后面试官提醒说“你平时是怎么挑西瓜的”。我说先看成色，再听声音，再看重量。然后我灵机一动说先挑出一部分好的西瓜，听他们的声音，然后将这些声音作成一个样本库，提取初相应的特征。然后去挑西瓜，用iphone录下用户敲西瓜的声音，与样本库里面的样本比对，看看相似度。嗯。大概这样。面试官表示这个答案还行。最后又问了我个排序的问题：给你若干个人，让你按照他们的年龄排序，有什么方法。显然这道题目是有陷阱的。但是我一时想不通，就随口说快排归并。他说不对，问我有没有听过桶排序，我说听说过不了解，他说就是做按照年龄1-100岁做100个桶，然后把扫描这些用户，按照年龄将用户排到桶里就可以了。我一想这么一来，时间复杂度只有[tex]O(n)[/tex]。是，是这么回事，基于比较的排序时间复杂度下限是[tex]O(\lg n)[/tex]，突破这个极限的方法就是不采用比较，另寻他法进行排序。这就是“线性排序“。可是我对“线性排序“又不甚了解，导致现在的悲剧。综合而言还是自己的算法功底不够。
临结束时，他问我又没有什么问题要问他。我还是说“想听一下你对我的评价“，他说你的情况比较复杂，需要对我有一个评分，上报HR，可能需要多轮面试。我又问如果最后没有通知是不是就挂了，他说是的。我说好的，谢谢，辛苦了。
就这样结束了……总之，差距尤在，暑假需要实习，在算法，网络，数据库三方面加强训练。嗯。