2011各大IT公司笔试面试题-经典.docVIP

窗体顶端 必威体育精装版面试十一题 十月百度：一个数组保存了N个结构，每个结构保存了一个坐标，结构间的坐标都不相同，请问如何找到指定坐标的结构（除了遍历整个数组，是否有更好的办法）？ 百度必威体育精装版面试题：现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。 Alibaba笔试题：给定一段产品的英文描述，包含M个英文字母，每个英文单词以空格分隔，无其他标点符号；再给定N个英文单词关键字，请说明思路并编程实现方法??? String extractSummary(String description,String[] key words)目标是找出此产品描述中包含N个关键字（每个关键词至少出现一次）的长度最短的子串，作为产品简介输出。（不限编程语言）20分。 搜狗：有N个正实数(注意是实数，大小升序排列) x1 , x2 ... xN，另有一个实数M。 需要选出若干个x，使这几个x的和与 M 最接近。 请描述实现算法，并指出算法复杂度（参考：第五章、寻找满足条件的两个或多个数）。 迅雷：给你10台机器，每个机器2个cpu，2g内存，现在已知在10亿条记录的数据库里执行一次查询需要5秒，问用什么方法能让90%的查询能在100毫秒以内返回结果。 给定一个函数rand()能产生0到n-1之间的等概率随机数，问如何产生0到m-1之间等概率的随机数？ 腾讯：五笔的编码范围是a ~ y的25个字母，从1位到4位的编码，如果我们把五笔的编码按字典序排序，形成一个数组如下：??? a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy其中a的Index为0，aa的Index为1，aaa的Index为2，以此类推。1）编写一个函数，输入是任意一个编码，比如baca，输出这个编码对应的Index；2）编写一个函数，输入是任意一个Index，比如12345，输出这个Index对应的编码。 2011.10.09百度笔试题（下述第8-12题）：linux/unix远程登陆都用到了ssh服务，当网络出现错误时服务会中断，linux/unix端的程序会停止。为什么会这样？说下ssh的原理，解释中断的原理。 一个最小堆，也是完全二叉树，用按层遍历数组表示。? 1.? 求节点a[n]的子节点的访问方式? 2.? 插入一节点的程序void add_element(int *a,int size,int val);? 3.? 删除最小节点的程序。 a）求一个全排列函数：如p([1,2,3])?，输出：? [123],[132],[213],[231],[321],[323]。b）求一个组合函数：??? 如p([1,2,3])?，输出：[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3]。这两问可以用伪代码（全排列请参考这里的第67题：微软、Google等公司非常好的面试题及解答[第61-70题]?）。 对一个数比如N=020，有一个和他位数相同，每一位上的数相加和相同的且是比N大的最小的数，如M=101，记M=f（N），s1=N,s=f(N)，s3=f(s2)。求当N的位数小于1000，M的大小小于10^500的序列。example:N=134 , M=143,? // 1+3+4=1+4+3N=020, M = 101, //2=1+1 有1000万条URL，每条URL　50字节，只包含主机前缀，要求实现URL提示系统：（１）要求实时更新匹配用户输入的地址，每输出一个字符，输出必威体育精装版匹配URL（2）每次只匹配主机前缀，例如对和，用户输入www.b时只提示（3）每次提供10条匹配的URL（4）以用户需求为主。 海量记录，记录形式如下： TERMID URLNOCOUNT urlno1 urlno2?? ..., urlnon?怎么考虑资源和时间这两个因素，实现快速查询任意两个记录的交集，并集等，设计相关的数据结构和算法。 百度必威体育精装版笔试题（感谢xiongyangwan提供的题目）：利用互斥量和条件变量设计一个消息队列，具有以下功能：? ?1 创建消息队列（消息中所含的元素）? ?2 消息队列中插入消息? ?3?取出一个消息（阻塞方式）? ?4 取出第一消息（非阻塞方式） 百度移动终端研发笔试：系统设计题（40分）对已排好序的数组A，一般来说可用二分查找可以很快找到。现有一特殊数组A[]，它是循环递增的，如A[]={ 17 19 20 25 1 4 7 9}，试在这样的数组中找一元素x，看看是否存在。请写出你的算法，必要时可写伪代码，并分析