新鲜出炉的腾讯后台开发三面面试题！

okocha-jay

随便写的

1)tcp三次握手的过程，accept发生在三次握手哪个阶段？

如果是accept阻塞在那里，根本就没有客户，三次握手也许正在进行；
如果是accept返回的时候，三次握手早完成了；

2）Tcp流， udp的数据报，之间有什么区别，为什么TCP要叫做数据流？
。。有点多。字节流吧，多个send发的数据可能会整合在一起发送。

3)const的含义及实现机制，比如：const int i,是怎么做到i只可读的？
直接用的立即数

4) volatile的含义
每次都从内存读取数据，不信任缓存；

5）OFFSETOF(s, m)的宏定义，s是结构类型，m是s的成员，求m在s中的偏移量。
&(（(struct s *)0）->m)
优先级漏了

6)100亿个数，求最大的1万个数，并说出算法的时间复杂度。
建立大小为1万的小根堆。。。

7）设计一个洗牌的算法，并说出算法的时间复杂度。
貌似哪里介绍有线性算法；先顺序赋值，后随机交换。

8 socket在什么情况下可读?
新数据到达；
收到FIN报文好像也是可读；也就是对方要求断开连接
新连接可读，比如收到了ACK+SYN，connect完成
其它情况不清楚


9）流量控制与拥塞控制的区别，节点计算机怎样感知网络拥塞了？
流量控制：控制连接的两端发送数据不要太快；
拥塞控制：控制连接所经过的路由器别超负荷；
感知拥塞应该是受到了ICMP抑制报文

okocha-jay

怎么找第1000 个大的k? 1000一个数字里面 怎么知道它是第1000个大？
benjiam 发表于 2010-03-24 09:25

    编程珠玑上介绍了一种quickselect,求第1000个大的数，那么最终数组的前1000个就是最小的那1000个；
书上是递归实现，最好转为非递归；
据上面介绍，KNUTH证明这种方法是线性的，3.4n