以往百度电话面试题

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

<!--EndFragment-->