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

windfaddy

{:3_200:}  都是高手

千年沉寂

很不解
你这个算法，能达到o（n）？
找出第10000大的数，不是找出第二大第三大的数吧。而且我觉 ...
ztz0223 发表于 2010-03-23 22:00

可以的，平均时间达到O(n)

类似于二分法：
1.每次随机选取一个数 n，扫描一遍，使n 的左边都比 n小(l个元素)，右边都比 n 大(r 个元素)。
2.
    A:若满足条件，则返回n;
    B:若k>l,只对n右边的元素返回第一步执行;
    C:若k>r,只对n左边的元素返回第一步执行;

B,C每次只需执行一项，因此平均复杂度大概为：O(n+n/2+n/4...)=O(2n)=O(n)

千年沉寂

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

见113楼

9ailiao

老大学识广博，受教受教

dozec

可以的，平均时间达到O(n)

类似于二分法：
1.每次随机选取一个数 n，扫描一遍，使n 的左边都比 n ...
千年沉寂 发表于 2010-03-25 15:13

能讲详细点嘛，说实话，没太看明白。快速排序和折半排序都我都明白，但你这个真没看明白，希望能展开详细讲讲，谢谢。
腾迅三面回来了，二笔的水平其实和这篇题的水平差不太多，只要这个你能做出来，基本上没问题。三面是技术总监面，看运气了，说实话，我有点摸不透技术总监面的要点，感觉应该更侧重你思考问题的方法吧，有技术总监面这方面经验的朋友不妨多说说。

lxjlan

1) 连接完成后， 这个在UNP里有说


2）TCP的有序性决定的吧。


3)const 常量标示符， 如何做到的不知道


4) valitale直接从内存读取数据，防止cache造成数据不一致


5）OFFSETOF(s, m)     (&s-&(s.m))


6)100亿个数，求最大的1万个数，并说出算法的时间复杂度。 （不懂）


7）设计一个洗牌的算法，并说出算法的时间复杂度。 （这个不懂。。）


socket 大于 低潮 指定的阀值，或有带外数据，unp上有说明


9）流量控制与拥塞控制的区别，节点计算机怎样感知网络拥塞了？
流量控制侧重流量的大小控制， 拥塞的控制不单是控制流量，应该也有流向。 感知拥塞？（测试响应时间？）


我要是了，也是被拒的料了。。。 汗。

千年沉寂

能讲详细点嘛，说实话，没太看明白。快速排序和折半排序都我都明白，但你这个真没看明白，希望能展开详 ...
dozec 发表于 2010-03-25 23:43

实际上是模仿快速排序算法设计的，其基本思想也是对输入数组进行划分。不同的是，它只对划分出的子数组之一进行处理。
过程大致如下：

1. int RandomSelect(int a[], int left, int right, int k)
   
2. {
   
3.         int i,j,p;
   
4.         if (right <= 1) return a[right];
   
5.         i = RandomPartition(a[], left, right);
   
6.         /************************************************
   
7.         * RandomPartition,把a[left:right]随机划分为:
   
8.         * a[left : i-1] <= a[i] <= a[i+1 : right].
   
9.         *************************************************/
   
10.         j = right - i + 1;
    
11.         /* j 为 a[i : right] 的元素个数*/
    
12.         if (j == k) return a[i];
    
13.         if (j > k)
    
14.             /* 第k大的数在右子数组 */
    
15.             return RandomSelect(a, i+1, right, k);
    
16.         else
    
17.             /* 第k大的数在左子数组 */
    
18.             return RandomSelect(a, left, i-1 , k-j);
    
19. }

复制代码

cocat00

学习

GodPig

顶~~~

同病相怜。。。

googlefans_wang

挺贴，读读。