《程序员 笔试面试八十题.pdf》由会员分享,可在线阅读,更多相关《程序员 笔试面试八十题.pdf(82页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 九月十月百度人搜,阿里巴巴,腾讯华为小米搜狗笔试面试八十题九月十月百度人搜,阿里巴巴,腾讯华为小米搜狗笔试面试八十题 引言引言 自发表上一篇文章至今 (事实上,上篇文章更新了近 3 个月之久) , blog 已经停了 3 个多月, 而在那之前,自开博以来的 21 个月每月都不曾断过。正如上一篇文章支持向量机通俗导论(理 解 SVM 的三层境界)末尾所述:”额,blog 许久未有更新了,因为最近实在忙,无暇顾及 blog。“与此 同时,工作之余,也一直在闲心研究数据挖掘:神经网络将可能作为 Top 10 Algorithms in Data Mining 之番外篇第 1 篇,同时,k-最近邻法
2、(k-nearest neighbor,kNN)算法谈到 kd 树将可能作为本系列 第三篇。这是此系列接下来要写的两个算法,刚好项目中也要用到 KD 树“。 但很显然,若要等到下一篇数据挖掘系列的文章时(更新:下一篇 kd 树目前已经完成: 月、10 月,正是各种 校招/笔试/面试火热进行的时节,自己则希望能帮助到这些找工作的朋友,故此,怎能无动 于衷,于是,3 个多月后,blog 今天更新了。 再者,虽然 blog 自 10 年 10 月开通至 11 年 10 月,一年的时间内整理了 300 多道面试 题(这 300 道题全部集锦在此文中第一部分: 但毕竟那些题已经是前年或去年的了, 笔试面
3、试题虽然每年类型变化不大, 但毕竟它年年推 陈出新,存着就有其合理性。 OK,以下是整理自 8 月下旬至 10 月份内的各大公司的笔试面试三十题(注:所有题目基 本上全部为软件开发方向,题目来源:网络收集),相信一定能给正在参加各种校招的诸多朋友多 少帮助,学习参考或借鉴(如果你手头上有好的笔试/面试题,欢迎通过微博私信: 发给我,或者干脆直接评论在本文下; 同时,若你对以下任何一题有任何看法.想法.思路或建议,欢迎留言评论,大家一起讨论,共同享受思考的 乐趣,谢谢)。 九月十月百度人搜,阿里巴巴,腾讯华为小米搜狗笔试面试八十题九月十月百度人搜,阿里巴巴,腾讯华为小米搜狗笔试面试八十题 我正在
4、一点一点做.整理下面的笔试面试题,欢迎读者朋友们跟我一起做,你可以把你的答案或代码 直接评论在本文之下,也可以通过私信或邮件发给我,感谢诸位。同时,以下所有任何题目所给的点评里 的答案,尤其是所给的外部链接若有任何问题,欢迎在本文评论下留言指正,谢谢。答题除了让你感受到 思考的乐趣以外,还有奖哦,请君自看。July、二零一二年十月十一日 1. 9 月 11 日, 京东: 谈谈你对面向对象编程的认识 2. 8 月 20 日,金山面试,题目如下: 数据库 1 中存放着 a 类数据,数据库 2 中存放着以天为单位划分的表 30 张(比 如 table_20110909,table_20110910,
5、table_20110911),总共是一个月的数据。表 1 中的 a 类数据中有一个字段 userid 来唯一判别用户身份,表 2 中的 30 张表(每张 表结构相同)也有一个字段 userid 来唯一识别用户身份。如何判定 a 类数据库的多 少用户在数据库 2 中出现过? 来源: 3. 百度实习笔试题(2012.5.6) 1、一个单词单词字母交换,可得另一个单词,如 army-mary,成为兄弟单词。提 供一个单词,在字典中找到它的兄弟。描述数据结构和查询过程。评点:同去年 9 月份的一道题, 见此文第3题: 2、线程和进程区别和联系。什么是“线程安全” 3、C 和 C+怎样分配和释放内存,
6、区别是什么 4、算法题 1 一个 url 指向的页面里面有另一个 url,最终有一个 url 指向之前出现过的 url 或空, 这 两种情形都定义为 null。这样构成一个单链表。给两条这样单链表,判断里面是否 存在同样的 url。url 以亿级计,资源不足以 hash。 5、算法题 2 数组al0,mid-1 和 almid,num-1, 都分别有序。 将其merge成有序数组al0,num-1, 要求空间复杂度 O(1) 6、系统设计题 百度搜索框的 suggestion,比如输入“北京”,搜索框下面会以北京为前缀,展示“北 京爱情故事”、“北京公交”、“北京医院”等等搜索词,输入“结构之
7、”,会提示“结构之 法”,“结构之法 算法之道”等搜索词。 请问,如何设计此系统,使得空间和时间复杂度尽量低。 评点:老题,直接上 Trie 树树Trie 树的介绍见:从 Trie 树(字典树)谈到后缀树+TOP Khashmap+堆,hashmap+堆 统计出如 10 个近似的热词,也就是说,只存与关键词近似的比 如 10 个热词? or Double-array trie tree?同时,StackOverflow 上也有两个 讨论帖子: gorithm-datastructure-c-c。此外,这里有一篇关于“拼写错误检查”问题的介绍,或许 对你有所启示: 4. 人搜笔试 1. 快排每次
8、以第一个作为主元,问时间复杂度是多少?(O(N*logN)) 2. T(N) = N + T(N/2)+T(2N), 问 T(N)的时间复杂度是多少? 点评:O(N*logN) or O(N)? 3. 从(0,1)中平均随机出几次才能使得和超过 1?(e) 4.编程题: 一棵树的节点定义格式如下: struct Node Node* parent; Node* firstChild; / 孩子节点 Node* sibling; / 兄弟节点 要求非递归遍历该树。 思路:采用队列存储,来遍历节点。 5. 算法题: 有 N 个节点,每两个节点相邻,每个节点只与 2 个节点相邻,因此,N 个顶点有
9、N-1 条边。每一条边上都有权值 wi,定义节点 i 到节点 i+1 的边为 wi。 求:不相邻的权值和最大的边的集合。 5. 人搜面试,所投职位:搜索研发工程师:面试题回忆 1、删除字符串开始及末尾的空白符,并且把数组中间的多个空格(如果有)符 转化为 1 个。 2、求数组(元素可为正数、负数、0)的最大子序列和。 3、链表相邻元素翻转,如 a-b-c-d-e-f-g,翻转后变为: b-a-d-c-f-e-g 4、链表克隆。链表的结构为: typedef struct list int data; /数据字段 list *middle; /指向链表中某任意位置元素(可指向自己)的指针 lis
10、t *next;/指向链表下一元素 list; 5、100 万条数据的数据库查询速度优化问题,解决关键点是:根据主表元素特 点,把主表拆分并新建副表,并且利用存储过程保证主副表的数据一致性。(不用 写代码) 6、 求正整数 n 所有可能的和式的组合 (如; 4=1+1+1+1、 1+1+2、 1+3、 2+1+1、 2+2)。点评:这里有一参考答案: 7、求旋转数组的最小元素(把一个数组最开始的若干个元素搬到数组的末尾, 我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小 元素。例如数组3, 4, 5, 1, 2为1, 2, 3, 4, 5的一个旋转,该数组的最小值为 1
11、) 8、找出两个单链表里交叉的第一个元素 9、 字符串移动 (字符串为*号和 26 个字母的任意组合, 把*号都移动到最左侧, 把字母移到最右侧并保持相对顺序不变),要求时间和空间复杂度最小 10、时间复杂度为 O(1),怎么找出一个栈里的最大元素 11、线程、进程区别 12、static 在 C 和 C+里各代表什么含义 13、const 在 C/C+里什么意思 14、常用 linux 命令 15、解释 Select/Poll 模型 6. 网易有道二面: 判断一个数字序列是 BST 后序遍历的结果,现场写代码。 来源: 7. 8 月 30 日,网易有道面试题 var tt = aa; fun
12、ction test() alert(tt); var tt = dd; alert(tt); test(); 8. 8 月 31 日,百度面试题:不使用随机数的洗牌算法,详情: 9. 9 月 6 日,阿里笔试题:平面上有很多点,点与点之间有可能有连线,求这个图里 环的数目。 10. 9 月 7 日,一道华为上机题: 题目描述: 选秀节目打分, 分为专家评委和大众评委, score 数组里面存储每个评 委打的分数,judge_type 里存储与 score 数组对应的评委类别,judge_type = 1,表示专家评委,judge_type = 2,表示大众评委,n 表示评委总数。打分规 则如
13、下:专家评委和大众评委的分数先分别取一个平均分(平均分取整),然后, 总分 = 专家评委平均分 * 0.6 + 大众评委 * 0.4,总分取整。如果没有大众评委, 则 总分 = 专家评委平均分,总分取整。函数最终返回选手得分。 函数接口 int cal_score(int score, int judge_type, int n) 上机题目需要将函数验证,但是题目中默认专家评委的个数不能为零,但是如何将 这种专家数目为 0 的情形排除出去。 来源: 11. 9 月 8 日,腾讯面试题: 假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配, 比如:abcda 和 adabc,由于出
14、现的字符个数都是相同,只是顺序不同, 所以这两个字符串是匹配的。要求高效! 又是跟上述第 3 题中简单题一的兄弟节点类似的一道题,我想,你们能想到的,这 篇 blog 里: 12. 阿里云,搜索引擎中 5 亿个 url 怎么高效存储; 13. 一道 C+笔试题,求矩形交集的面积: 在一个平面坐标系上,有两个矩形,它们的边分别平行于 X 和 Y 轴。 其中,矩形 A 已知, ax1(左边), ax2(右边), ay1(top 的纵坐标), ay2(bottom 纵坐标). 矩形 B,类似,就是 bx1, bx2, by1, by2。这些值都是整数就 OK 了。 要求是,如果矩形没有交集,返回-1
15、, 有交集,返回交集的面积。 int area(rect const 6. double y 2; 7. ; 8. 9. template T const 10. template T const 11. 12. / return type changed to handle non-integer rects 13. double area (rect const 17. double const dy = min(a.y1,b.y1) - max(a.y0,b.y0); 18. return dx=0 19. 下面是一个简短的证明。 对于平行于坐标轴的矩形 r,假设其左下角点坐标为 (rx
16、0,ry0),右上角点坐标为 (rx1,ry1),那么 由 r 定义的无限有界点集为:(x,y)|x in rx0,rx1 5. Comparable maxProduct = 1; 6. Comparable minProduct = 1; 7. Comparable maxCurrent = 1; 8. Comparable minCurrent = 1; 9. /Comparable t; 10. 11. for( i=0; i maxProduct) 16. maxProduct = maxCurrent; 17. if(minCurrent maxProduct) 18. maxPr
17、oduct = minCurrent; 19. if(maxCurrent minProduct) 20. minProduct = maxCurrent; 21. if(minCurrent maxCurrent) 24. swap(maxCurrent,minCurrent); 25. if(maxCurrent1) 28. / minCurrent =1; 29. 30. return maxProduct; 31. 解法二、 本题除了上述类似最大子数组和的解法,也可以直接用动态规划求解(其实,上 述的解法一本质上也是动态规划,只是解题所表现出来的具体形式与接下来的解法二不同罢了。 这个
18、不同就在于下面的解法二会写出动态规划问题中经典常见的状态转移方程,而解法一是直接 求解)。具体解法如下: 假设数组为 a, 直接利用动归来求解, 考虑到可能存在负数的情况, 我们用 Maxi 来表示以 ai结尾的最大连续子序列的乘积值,用 Mini表示以 ai结尾的最小的连 续子序列的乘积值,那么状态转移方程为: Maxi=maxai, Maxi-1*ai, Mini-1*ai; Mini=minai, Maxi-1*ai, Mini-1*ai; 初始状态为 Max1=Min1=a1。代码如下: 1. /* 2. 给定一个整数数组,有正有负数,0,正数组成,数组下标从 1 算起 3. 求最大连
19、续子序列乘积,并输出这个序列,如果最大子序列乘积为负数,那么就输出-1 4. 用 Maxi表示以 ai结尾乘积最大的连续子序列 5. 用 Mini表示以 ai结尾乘积最小的连续子序列 因为有复数,所以保存这个是必须的 6. */ 7. void longest_multiple(int *a,int n) 8. int *Min=new intn+1(); 9. int *Max=new intn+1(); 10. int *p=new intn+1(); 11. /初始化 12. for(int i=0;i=n;i+) 13. pi=-1; 14. 15. Min1=a1; 16. Max1
20、=a1; 17. int max_val=Max1; 18. for(int i=2;i=n;i+) 19. Maxi=max(Maxi-1*ai,Mini-1*ai,ai); 20. Mini=min(Maxi-1*ai,Mini-1*ai,ai); 21. if(max_valMaxi) 22. max_val=Maxi; 23. 24. if(max_val0) 25. printf(%d,-1); 26. else 27. printf(%d,max_val); 28. /内存释放 29. delete Max; 30. delete Min; 31. 变种 此外,此题还有另外的一个变
21、种形式,即给定一个长度为 N 的整数数组,只允许 用乘法,不能用除法,计算任意(N-1)个数的组合中乘积最大的一组,并写出算法 的时间复杂度。 我们可以把所有可能的(N-1)个数的组合找出来,分别计算它们的乘积,并比 较大小。由于总共有 N 个(N-1)个数的组合,总的时间复杂度为 O(N2),显然这 不是最好的解法。 OK,以下解答来自编程之美 解法 1 解法 2 此外,还可以通过分析,进一步减少解答问题的计算量。假设 N 个整数的乘积为 P,针对 P 的正负性进行如下分析(其中,AN-1 表示 N-1 个数的组合,PN-1 表示 N-1 个数的组合的乘积)。 1.P为 0 那么,数组中至少
22、包含有一个 0。假设除去一个 0 之外,其他 N-1 个数的乘积为 Q,根 据 Q 的正负性进行讨论: Q 为 0 说明数组中至少有两个 0,那么 N-1 个数的乘积只能为 0,返回 0; Q 为正数 返回 Q,因为如果以 0 替换此时 AN-1中的任一个数,所得到的 PN-1为 0,必然小于 Q; Q 为负数 如果以 0 替换此时 AN-1中的任一个数,所得到的 PN-1为 0,大于 Q,乘积最大值为 0。 2. P 为负数 根据“负负得正”的乘法性质, 自然想到从N个整数中去掉一个负数, 使得PN-1为一个正数。 而要使这个正数最大,这个被去掉的负数的绝对值必须是数组中最小的。我们只需要扫
23、描 一遍数组,把绝对值最小的负数给去掉就可以了。 3. P 为正数 类似地,如果数组中存在正数值,那么应该去掉最小的正数值,否则去掉绝 对值最大的负数值。 上面的解法采用了直接求 N 个整数的乘积 P,进而判断 P 的正负性的办法,但 是直接求乘积在编译环境下往往会有溢出的危险(这也就是本题要求不使用除法的 潜在用意),事实上可做一个小的转变,不需要直接求乘积,而是求出数组中正数 (+)、负数(-)和 0 的个数,从而判断 P 的正负性,其余部分与以上面的解法相 同。 在时间复杂度方面, 由于只需要遍历数组一次, 在遍历数组的同时就可得到数组 中正数(+)、负数(-)和 0 的个数,以及数组中
24、绝对值最小的正数和负数,时间 复杂度为 O(N)。 18. 9 月 15 日,中兴面试: 小端系统 1. union 2. int i; 3. unsigned char ch2; 4. Student; 5. 6. 7. int main() 8. 9. Student student; 10. student.i=0 x1420; 11. printf(%d %d,student.ch0,student.ch1); 12. return 0; 13. 输出结果为?(答案:32 20) 19. 一道有趣的 Facebook 面试题: 给一个二叉树,每个节点都是正或负整数,如何找到一个子树,它
25、所有节点的和最 大? 点评: 某猛将兄:后序遍历,每一个节点保存左右子树的和加上自己的值。额外一个空间存放最大值。 陈利人:同学们,如果你面试的是软件工程师的职位,一般面试官会要求你在短时间内写出一 个比较整洁的,最好是高效的,没有什么 bug 的程序。所以,光有算法不够,还得多实践。 写完后序遍历,面试官可能接着与你讨论,a). 如果要求找出只含正数的最大子树,程序该如何修 改来实现?b). 假设我们将子树定义为它和它的部分后代,那该如何解决?c). 对于 b,加上正数 的限制,方案又该如何?总之,一道看似简单的面试题,可能能变换成各种花样。 比如,面试管可能还会再提两个要求:第一,不能用全
26、局变量;第一,有个参数控制是否要只含 正数的子树。其它的,随意,当然,编程风格也很重要。 20. 谷歌面试题: 有几百亿的整数,分布的存储到几百台通过网络连接的计算机上,你能否开发出一 个算法和系统,找出这几百亿数据的中值?就是在一组排序好的数据中居于中间的 数。显然,一台机器是装不下所有的数据。也尽量少用网络带宽。 21. 小米,南京站笔试(原第 20 题): 一个数组里,数都是两两出现的,但是有三个数是唯一出现的,找出这三个数。 点评: 3 个数唯一出现,各不相同。由于 x 与 a、b、c 都各不相同,因此 xa、xb、xc 都不等于 0。具体答案请参看这两篇文章:1、 22. 9 月 1
27、9 日,IGT 面试:你走到一个分叉路口,有两条路,每个路口有一个人,一个 说假话, 一个说真话, 你只能问其中一个人仅一个问题, 如何问才能得到正确答案? 点评:答案是,问其中一个人:另一个人会说你的路口是通往正确的道路么? 23. 9 月 19 日,创新工厂笔试题: 给定一整型数组, 若数组中某个下标值大的元素值小于某个下标值比它小的元素值, 称这是一个反序。 即:数组 a; 对于 i aj,则称这是一个反序。 给定一个数组,要求写一个函数,计算出这个数组里所有反序的个数。 点评: 归并排序,至于有的人说是否有 O(N)的时间复杂度,我认为答案是否定的,正 如老梦所说,下限就是 nlgn,
28、n 个元素的数组的排列共有的排列是 nlgn,n!(算 法导论里面也用递归树证明了: O(n*logn)是最优的解法, 具体可以看下这个链接: ) 。 然后,我再给一个链接,这里有那天笔试的两道题目: 24. 9 月 20 日,创新工厂南京站笔试: 已知字符串里的字符是互不相同的,现在任意组合,比如 ab,则输出 aa,ab,ba, bb,编程按照字典序输出所有的组合。 点评:非简单的全排列问题(跟全排列的形式不同,abc 全排列的话,只有个不同的输出: 一个变量表示已输出的个数,然后当个数达到字符串长度时,就输出。 1. /假设 str 已经有序,from 一直很安静 2. void per
29、m(char *str, int size, int resPos) 3. 4. if(resPos = size) 5. print(result); 6. else 7. 8. for(int i = 0; i 0) 7. 8. a = a + b; 9. c+; 10. 11. printf(%d, c); 12. 问:最后程序输出是多少?点评:此题有陷阱,答题需谨慎! 点评: 针对上述第 3 题朋友圈的问题,读者互联网的飞虫提供的解法及代码如下(有任何 问题,欢迎指正,多谢): 1. #include 2. #include 3. 4. 5. int Friends(int n, in
30、t m , int* r); 6. 7. int main(int argc,char* argv) 8. 9. int r52 = 1,2,4,3,6,5,7,8,7,9; 10. 11. printf(有%d 个朋友圈。n,Friends(0,5,(int*)r); 12. return 0; 13. 14. 15. int Friends(int n, int m, int* r) / 注意这里的参数很奇葩 16. 17. 18. int *p = (int*)malloc(sizeof(int)*m*3); 19. 20. memset(p,0,sizeof(int)*m*3); 21
31、. int i = 0; 22. 23. int iCount = 0; 24. 25. int j = 0; 26. 27. int * q = (int*)r; / 这里很巧妙 将二维指针 强转为一维指针 28. 29. for (i=0;im;+i) 30. 31. for (j=0;j2;+j) 32. 33. pi*3+j=qi*2+j; / 注意这里二维数组向一维数组的转换 34. 35. 36. pi*3+j = 0; 37. 38. 39. bool bFlag = false; 40. 41. for (i=0;im;+i) 42. 43. bFlag = false; 44
32、. if (pi*3+2=1) 45. 46. bFlag = true; 47. 48. pi*3+2 = 1; 49. for (j=0;jm;+j) 50. 51. if (i=j) 52. 53. continue; 54. 55. 56. 57. if (pi*3=pj*3 | 58. pi*3 = pj*3+1 | 59. pi*3+1 = pj*3+0 | 60. pi*3+1 = pj*3+1) 61. 62. if (pj*3+2=1) 63. 64. bFlag = true; 65. 66. pj*3+2 = 1; 67. 68. 69. 70. if (!bFlag)
33、71. 72. +iCount; 73. 74. 75. 76. free(p); 77. 78. return iCount; 79. 26. 9 月 21 日晚,海豚浏览器笔试题: 1、有两个序列 A 和 B,A=(a1,a2,.,ak),B=(b1,b2,.,bk),A 和 B 都按升序排列,对于 1=i,j=k,求 k 个最小的(ai+bj),要求算法尽量高效。 2、输入: L:“shit”“fuck”“you” S:“shitmeshitfuckyou” 输出: S 中包含的 L 一个单词, 要求这个单词只出现一次, 如果有多个出现一次的, 输出第一个这样的单词 怎么做? 27. 9
34、 月 22 日上午,百度西安站全套笔试题如下: 点评:上述的系统设计题简单来讲,是建立起按键号码数字到人名(手机号)的映射关 系,具体讲,步骤解法如下图所示: 3.算法与程序设计 第一题: 某个公司举行一场羽毛球赛, 有 1001 个人参加, 现在为了评比出“最厉害的那个人”, 进行淘汰赛,请问至少需要进行多少次比赛。 第二题 有 100 个灯泡,第一轮把所有灯泡都开启,第二轮把奇数位的灯泡灭掉,第三轮每 隔两个灯泡,灭一个,开一个,依此类推。求 100 轮后还亮的灯泡。 点评:完全平方数,本人去 58 面试时,也遇到过与此类似的题。 第三题 有 20 个数组,每个数组里面有 500 个数组,
35、降序排列,每个数字是 32 位的 unit, 求出这 10000 个数字中最大的 500 个。 点评: 4.系统设计题 类似做一个手机键盘,上面有 1 到 9 个数字,每个数字都代表几个字母(比如 1 代 表 abc 三个字母,z 代表 wxyz 等等),现在要求设计当输入某几个数字的组合时, 查找出通讯录中的人名及电话号码。 其它的还有三道简答题, 比如线程的死锁, 内存的管理等等。 最后, 附一讨论帖子: 28. 9 月 22 日,微软笔试: T(n)=1(n=1),T(n) = 25*T(n/5) + n2,求算法的时间复杂度。更多题目请参见: 29. 9 月 23 日,腾讯校招部分笔试
36、题(特别提醒:下述试卷上的答案只是一考生的解答,非代表正 确答案.如下面第 11 题答案选 D,第 12 题答案选 C,至于解释可看这 里: 点评:根号九说,不过最后两道大的附加题,全是秒杀 99%海量数据处理面试题里 的: July 了。 30. 9 月 23 日,搜狗校招武汉站笔试题: 一、已知计算机有以下原子操作 1、 赋值操作:b = a; 2、 +a 和 a+1; 3、for( ) *有限循环; 4、操作数只能为 0 或者正整数; 5、定义函数 实现加减乘操作 二、对一个链表进行排序,效率越高越好,LinkedList. 附:9 月 15 日,搜弧校招笔试题: 31. 搜狗校招笔试题
37、: 100 个任务,100 个工人每人可做一项任务,每个任务每个人做的的费用为 t100100,求一个分配任务的方案使得总费用最少。 点评:匈牙利算法,可以看看这篇文章: 个链接: 32. 9 月 24 日,Google 南京等站全套笔试题如下: 点评: 谷歌的笔试从易到难,基础到复杂,涵盖操作系统 网络 数据结构 语言 数学思维 编程能力 算法能力,基本上能把一个人的能力全面考察出来。 至于上述 2.1 寻找 3 个数的中位数,请看读者 sos-phoenix 给出的思路及代码: 1. 2.1 / 采用两两比较的思路(目前没想到更好的) 2. if (a = b) 3. if (b = c)
38、 4. return b; 5. else 6. if (a =c) 7. return c; 8. else 9. return a; 10. 11. 12. else 13. if (a = c) 14. return a; 15. else 16. if (b = c) 17. return c; 18. else 19. return b; 20. 21. 最坏情况下的比较次数:3 (次) 平均情况下的比较次数:(22 + 4*3)/6 = 8/3 (次) 此外这题,微博上的左耳朵耗子后来也给出了一个链 接: e-of-a-triple,最后是微博上的梁斌 penny 的解答: 93
39、楼。 33. 读者来信,提供的几个 hulu 面试题: 9 月 19 号,hulu 电面: 问题 1 两个骰子, 两个人轮流投, 直到点数和大于 6 就停止, 最终投的那个人获胜。 问先投那个人获胜概率? 问题 2 平面上 n 个圆,任意两个都相交,是否有一条直线和所有的圆都有交点。 9 月 22 号,上午 hulu 面试 问题 1 100 个人,每人头上戴一顶帽子,写有 0.99 的一个数,数可能重复,每个 人都只能看到除自己以外其他人的帽子。每个人需要说出自己的帽子的数,一个人 说对就算赢。点评:参考答案请看这个链接: 问题 2 n 台机器,每台有负载,以和负载成正比的概率,随机选择一台机
40、器。原 题是希望设计 O(1)的算法(预处理 O(n)不可少,要算出每台机器的比例),因为非 O(1)的话, 就 trivial 了: 可以产生随机数例如0,1)然后, 根据负载比例, 2 分或者直接循环检查落入哪个区间, 决定机器。 面试官想问, 有没更好的办法, 避免那种查找。 即能否多次 (常数次) 调用随机函数, 拟合出一个概率分布 问题 3 行列都递增的矩阵,求中位数。点评: 34. 西安百度软件研发工程师: 一面(2012.9.24): 问的比较广,涉及操作系统、网络、数据结构。比较难的就 2 道题。 (1)10 亿个 int 型整数,如何找出重复出现的数字; (2)有 2G 的一
41、个文本文档, 文件每行存储的是一个句子, 每个单词是用空格隔开的。 问: 输入一个句子, 如何找到和它最相似的前 10 个句子。 (提示: 可用倒排文档) 。 二面(2012.9.25): (1)一个处理器最多能处理 m 个任务。现在有 n 个任务需要完成,每个任务都有自己 完成所需的时间。此外每个任务之间有依赖性,比如任务开始执行的前提是任务 必须完成。设计一个调度算法,使得这 n 这任务的完成时间最小; (2)有一个排序二叉树,数据类型是 int 型,如何找出中间大的元素; (3)一个 N 个元素的整形数组,如何找出前 K 个最大的元素。 (4)给定一个凸四边形,如何判断一个点在这个平面上
42、。 点评:本题的讨论及参考答案请见这: 运维部(2012.9.27): (1)堆和栈的区别; (2)问如何数出自己头上的头发。 35. 9 月 25 日,人人网笔试题: 点评:参考答案请见, 36. 9 月 25 日晚,创新工场校园招聘北邮站笔试: 37. 9 月 25 日,小米大连站笔试题: 1 一共有 100 万,抽中的 2 万,每月增加 4 万,问 20 个月能抽中的概率为:? 2 for(int i=0;istrlen(s);i+)n+=I;时间复杂度 O(n) 3 手机 wifi(A).wifi ap.局域网(B).路由器ADSL(C).互联网. 服务器 断掉上述 ABC 哪些点 T
43、CP 链接会立刻断掉? 4 12345 入栈,出栈结果 21543 31245 43215 12534 可能的为?(第一个和第三个) 5 xn+a1xn-1+an-1x+an,最少要做乘法?题目中 a1,a2,an 为常数。 38. 9 月 26 日,百度一二面: 1、给定一数组,输出满足 2a=b(a,b 代表数组中的数)的数对,要求时间复杂度 尽量低。 2、 搜索引擎多线程中每个线程占用多少内存?如果搜索引擎存储网页内存占用太大 怎么解决? 3、有很多 url,例如*,* . 现在给你一个 快速匹配出是*。点评:老题,此前 blog 内曾整理过。 4、找出字符串的编辑距离,即把一个字符串
44、s1 最少经过多少步操作变成编程字符 串 s2,操作有三种,添加一个字符,删除一个字符,修改一个字符(只要听过编辑 距离,知道往动态规划上想,很快就可以找到解法)。 点评:请看链接: 5、编程实现 memcopy,注意考虑目标内存空间和源空间重叠的时候。 6、实现简单的一个查找二叉树的深度的函数。 39. 9 月 26 日晚,优酷土豆笔试题一道: 优酷是一家视频网站,每天有上亿的视频被观看,现在公司要请研发人员找出最热 门的视频。 该问题的输入可以简化为一个字符串文件,每一行都表示一个视频 id,然后要找出 出现次数最多的前 100 个视频 id,将其输出,同时输出该视频的出现次数。 1.假设
45、每天的视频播放次数为 3 亿次,被观看的视频数量为一百万个,每个视频 ID 的长度为 20 字节,限定使用的内存为 1G。请简述做法,再写代码。 2.假设每个月的视频播放次数为 100 亿次,被观看的视频数量为 1 亿,每个视频 ID 的长度为 20 字节,一台机器被限定使用的内存为 1G。 点评:有关海量数据处理的题目,请到此文中找方法(无论题目形式怎么变,基本方法不 变,当然,最最常用的方法是:分而治之/Hash 映射 + Hash 统计 + 堆/快速/归并排序): 可如模 1000,把整个大文件映射为 1000 个小文件再处理 . 40. 9 月 26 日,baidu 面试题: 1.进程和线程的区别 2.一个有序数组(从小到大排列),数组中的数据有正有负,求这个数组中的最小 绝对值 3.链表倒数第 n 个元素 4.有一个函数 fun 能返回 0 和 1 两个值,返回 0 和 1 的概率都是 1/2,问怎么利用 这个函数得到另一个函数 fun2, 使 fun2 也只能返回 0 和 1, 且返回 0 的概率为 1/4, 返回 1 的概率为 3/4。(如果返回 0 的概率为 0
限制150内