行者无疆 始于足下 - 行走,思考,在路上

创新工厂电面小记

其实我一直对这些明星公司抱有一种仰望的态度,像前几天的百度,已经很让我惊喜,给了我很大的信心。昨天的创新工厂电面,虽然自己被虐的比较惨,但是还是进一步明确了自己的方向,了解了自己的差距。

对开复老师,除了仰慕,更多的是一种敬重。老实说我并不觉得开复老师是个天才,我认为他能成功,有一部分原因是在正确的时间正确的地点遇到了正确的人。我从来就不相信“穷人的孩子早当家”,更多时候,良好的家庭背景条件,有眼光的父母亲情教育,宽容大度自由的义务教育和高等教育,是一个人成长成才的助推器。敬重开复,是因为这么多年他为帮助中国青年成长所倾注的心血。当然,少部分人在他背后说三道四,说他虚伪做作,对此,我只能说,这些小人连“虚伪做作”的资本都没有。

好了,废话少说,说说本次面试吧。面试的过程很简单,就是给你一套题,一个小时的时间,然后在根据你答题情况刨根问底。答题的网站是collabedit。大概是由于世界杯的原因,网络比较拥塞,刷了5分钟才刷出题目来。题目总共有22道,考的范围非常广泛,很能反应一个人平时的积累。由于不方便,所以我暂时不能把所有题目原数贴出。大概概述一下题目分布情况吧:

  1. c\c++基础题
  2. 双向链表插入
  3. 二叉树遍历(三种方式)
  4. 栈的基本操作
  5. 概率问题
  6. tcp和udp区别联系
  7. sql基础语法问题
  8. 概率问题
  9. 图论问题(好像是“三角形无关图”,就是求一个8个顶点的无向图中,不含三角形,那么最多的边有多少)
  10. 函数递归问题
  11. 编程序题目:给定一条直线(L: x=5)和一个定点序列a[n],组成一条折线a[0]a[1]...a[n],求这条折线与直线(L: x=5)有多少个交点。
  12. 设计模式(什么是Singleton模式,PHP如何实现)
  13. PHP和MySQL
  14. PHP中的_POST数组
  15. PHP中"==="和"=="两个操作符的差别
  16. 还是PHP
  17. 还是PHP
  18. 还是PHP
  19. JavaScript和iframe
  20. MySql: datetime和timestamp差别
  21. JavaScript和iframe
  22. 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,可能需要多轮面试。我又问如果最后没有通知是不是就挂了,他说是的。我说好的,谢谢,辛苦了。

就这样结束了……总之,差距尤在,暑假需要实习,在算法,网络,数据库三方面加强训练。嗯。




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee