以往的百度电话面试题目

elfin1007

贡献于2013-09-22

字数:4067 关键词: 面试题目 试题

1、一个概率题:54张扑克牌,除去两张大小王剩下52张扑克牌。问红桃A和黑桃A同时被一个人拿到的概率是多少?  C(4,1)*C(50,11)/C(52,13) ???假设分为四个人拿,每人拿13张。 2、给一组数,其中只有一个数是重复了奇数次,其余都重复了偶数次,如何找出奇数次的那个数 ans=0,for i in 1 to n , ans^=num[i] 最后qns为所求 把所有的数异或,最后剩下的就是那个数了 3、上千万条记录,统计出重复记录最多的前N条。  先统计每个记录出现的次数(hash),再求第N大元素(经典法) 4、一个N个整数的无序数组,给你一个数sum,求出数组中是否存在两个数,使他们的和为sum O(nlg(n)) 先排序,然后两个指针从数组的两端向中间靠拢 《编程之美》一书有讲 5、谈谈你对数据库中索引的理解 如果对于一个数据库表中的访问比较频繁,那么可以考虑建立索引,根据搜索语句的不同建立的索引也不相同,如果查询语句大多是=什么数据的话,或者是一个范围的话,那么可以建立b+树索引,如果所搜索的字段值的唯一性比较好,那么可以考虑建立位图索引,以节约空间,但是如果查询语句大多是搜索空值,那么没有必要建立索引了,因为空值是没有办法建立索引的。 在经常用在连接的列上,这些列主要是一些外键,可以加快连接的速度; 在经常需要排序的列上创建索引,因为索引已经排序,这样查询可以利用索引的排序,加快排序查询时间 不应该建立索引的地方:访问比较少,值得范围很少(例如性别,年龄),经常进行修改的。 如果表的行数比较小的话,没有必要建立索引。 6、现在普通关系数据库用得数据结构是什么类型的数据结构 B+树?bitmap 7、索引的优点和缺点 优点: 第一, 可以大大加快数据的检索速度,这也是创建索引的最主要的原因。 第二, 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。 第三, 可以加速表和表之间的连接,特别是在实现数据的参考完整性方面特别有意义。例如,有些搜索语句经常需要对两个表同时进行join,对于这两个表进行join后的索引,可以大大加快访问这两个表的速度。 第四, 如果索引是有序的,那么在搜索一个范围时,可以很快给出结果。而不用进行排序。 缺点: 第一, 时间:创建索引和维护索引要耗费时间,这种时间随着数据量的增加而增加。 第二, 空间:索引需要占物理空间,除了数据表占数据空间之外,每一个索引还要占一定的物理空间,如果要建立聚簇索引,那么需要的空间就会更大。 第三, 维护难度:当对表中的数据进行增加、删除和修改的时候,索引也要动态的维护,这样就降低了数据的维护速度。 8、session和cache的区别是什么 Session 是单用户的会话状态。 当用户访问网站时,产生一个 SESSIONID。并存在于 COOKIES 中。每次向服务器请求时,发送这个 COOKIES ,再从服务器中检索是否有这个 SESSIONID 保存的数据。。。 而 CACHE ,则是服务器端的缓存,是所有用户都可以访问和共享的。 9、如果有几千个session,怎么提高效率 分子目录存放session提高效率 10、session是存储在什么地方,以什么形式存储的。 session是存在服务器的内存中 每个会话对应一个sessionId 通过sessionId开区分是那个会话的session,是以键值对的形式存储 hashtable Tomcat 中的 Session 是放在 org.apache.catalina.session.ManagerBase 类中, 以 HashMap 格式存放,key 为 sessionId, value 为 org.apache.catalina.Session 接口, 这个接口由 org.apache.catalina.session.StandardSession 类实现,这个类同时实现了 HttpSession 接口。 实际上 Tomcat 中所使用的 HttpSession 实现并不把 StandardSession 拿来直接使用的, 而是为这个类做了个 org.apache.catalina.session.StandardSessionFacade 的门面,这个 门面什么事情都没做过,只是委托其内部属性的 StandardSession 去做。 另外,StandardSession,也就是 HttpSession 在 Tomcat 中实现的根源,其中的数据,也就 是我们采用 session.setAttribute(key, value); 设置进去的值是采用一个 Hashtable 来存放的。 11、程序的调试 看错误报告,alert,print,设置断点,messagebox, 12、ASP.NET的Application、Session、Cookie、ViewState和Cache等变量的区别是什么? Application是公共的,所有人都能看到,所以可以用来做聊天室, session是私有的,每个客户端都存在一个不同的session 生存期正常是20分钟,也可以自己设定为1分钟或2个小时 cookie是保存在本机的文件,记录短小的信息,除非你让cookie过期,否则会一直存在 viewstate类似于asp中的hidden控件,用来记录页面中的控件的状态的,主要在页面间信息传递时用, cache是缓存,用来记录已经执行过的一些数据,比如读取数据库,目的是加速显示,减少服务器的负担,过期时间也是可以自己设定的, 13、对给定的上亿条无序的url,请按照domain、site以及path分别排序,并请指出排序过程中可能会遇到的哪些问题?如何提高效率? 例如:http://www.baidu.com/path/about.html,domain、site以及path的定义分别如下: Domain:baidu.com Site:www.baidu.com Path: www.baidu.com/path 14、内存中有一个长数组,条目数为10万,数组单元为结构体struct array,sizeof(struct array)为512字节。结构有一int型成员变量weight。现需要取得按weight值从大到小排序的前500个数组单元,请实现算法,要求效率尽可能高。 思路:这题属于排序的内容,题目要求只排序前500个数组单元,则在所有常用算法中,堆排序不仅能实现要求,还能达到n*lg(n)的时间复杂度,相对较快。因此,用堆排序解决。 算法如下: 1,将长数组按照变量weight调整为最大堆 2,取第一个元素和最后一个元素交换 3,再执行1,2 总共循环500次 4,取数组的最后500个元素,就是排序的前500个单元 看http://lanphaday.bokee.com/5145376.html 15、如何用两个指针检测一个链表是否为带回路(也就是循环链表) 用两个步长相差1的指针在链表中移动,如果有回路,肯定两个指针会相遇的 16、有一百个人,其中有一个是明星。明星不认识任何人,其他人都认识明星以及若干个其他人。你可以找任意两个人,问他们互相是否认识。 问:如何以最快的方式找出明星。 答案是:找第一个人,问是否认识第二个。如果认识,说明第一个人不是明星,排除;如果不认识,说明第二个人不是明星,排除。以此类推,每次都可以排除一个人,最多99次。 17、如何用两个队列模拟栈。 假设queuea和queueb。 入栈:由queuea入队列 出栈: 1.如果queuea.size>1,queuea元素出队列到queueb,但queuea保留一个元素,并出队列 2.如果queuea.size=1,queuea出队列 3.如果queuea.size=0,且queueb.size>0,queueb所有元素出队列到queuea,且queuea再导出元素到queueb,但queuea保留一个元素,并出队列 4.如果queuea.size=0& queueb.size=0,没有元素可出栈 18、如何用两个堆栈模拟队列 假设instack和outstack。 入队列:由instack入栈 出队列: 1.如果outstack为空,instack所有元素出栈到outstack 2.如果outstack不为空,outstack出栈 3.如果outstack为空,没有元素可出队列 19、如何找到链表的中间元素呢? 1. 如果是双向链表,那么设置两个指针,一个指向头 一个指向尾,指向头的指针和指向尾的指针同时向后向前移动, a.当他们的next为对方的时候,这两个指针指向中间的两个元素 b.上面的情况时偶数个元素的情况,如果是奇数个元素呢? 这个时候需要判断他们指向的是不是同一个元素,如果是, 那么这个元素就是中间的元素 所以,双向链表需要判断两种情况, 当他们的next为对方的时候或者同一个元素的时候, 这个时候就找到了中间的元素 2.如果是单链表,情况稍微复杂点。 这个时候还是需要设置两个指针,都指向链表头,但是移动的速度不一样 其中一个指针的移动速度是另外一个的两倍。 当速度快的指针没有next和next的next的时候,循环结束 a.当单链表只有一个元素的时候,直接结束 b.当有两个元素的时候,直接结束 当有三个或以上元素的时候,循环即可。循环结束时, 速度慢的指针指向的就是中间的元素。 但是当单链表元素有偶数个的时候,上面的办法只能找出来一个 中间元素。所以在指针移动的时候记录元素的个数,如果是偶数个元素, 那么速度慢的指针指向的元素和这个元素的next都是中间元素。 20、多个线程访问共享内存时应该怎么办 21、智力题目 一个小猴子边上有100根香蕉,它要走过50米才能到家,每次它最多只能搬50根香蕉,它每走1米就要吃掉一根,请问它最多能把多少根香蕉搬到家里? 设Y为要求的香蕉最大剩余数,X为要求的那个点(X米),可以列出方程式: 1. Y=(100-3X) - (50-X) =50-2X 所以x越小y越大 2. (100-3X)<=50 剩余的香蕉数小于等于50,否则拿不了,x>=16又2/3 因此x=17 Y=16 很容易求出Y=16

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享文档获得金币 ]
1 人已下载

下载文档

相关文档