今天是参加最后一场面试了. 题目很搞啊. 看看

linuxcici

面试主要看看题目而已.

从1----1百万个数字里面随机抽取五十万个不同的数字.



记住喔. 是高效的方法. 今天的笔试题目. 大约要用10分钟完成. 游戏python职位. 我做偏了今天. 因为没听清楚是五十万个不同的.
不过最后考官告诉我怎么做. 但他自己又说是个低效率的方法. 哎...我真是汗....还说这是个必做题目. 而且他的做法是错误的. 我都不说了.

他说,如:

例如简单点说5个数吧

创建一个A链表.有1,2,3,4,5
一个数组B.

int number=random(A表的长度)
把number放到B里保存.
A的表长度减少1.
A表对应的数据删除.

考官说这样可以避免随机到重复的数. 我心想. 不是吧. 要是1,2,3,4,5长度是5. 第一次抽2,长度减1只有4了, 第二次抽2. 还不是一个样重复.
我佩服他了.



还有个题目:如:非常长的数字: 32478914098230948234 +101 是怎么写这加法涵数
                            32478914098230948234 *101呢?

我说加法就那高位不用理会. 低位和低位加. 看有进位就进位. 用寄存器保存这些数据. 如果不够就在内存里做为临时保存点.
乘法就移位,他摇头啊. 我问他怎么做. 他不说.


公司在动漫产业基地. 10楼.名字就不说了

scutan

说说我的愚见。
第一个题我觉得应该用位运算来做，在编程珠玑第一章有讲解。
第二个题就是用字符串来保存很长的数来进行加和乘，在ACM的题中也有。

linuxcici

原帖由 scutan 于 2008-3-25 23:16 发表
说说我的愚见。
第一个题我觉得应该用位运算来做，在编程珠玑第一章有讲解。
第二个题就是用字符串来保存很长的数来进行加和乘，在ACM的题中也有。

小公司出这些题目啊. 哎....佩服啊

cjaizss

第一道，o(m*(2n-m))时间级别的？（n是1000000，m是500000）（纯属个人猜测，实在想不出高效的算法）
第二道，如同小学生做算术那样，数字电路也是这么实现的，只是多了少许优化而已。

cjaizss

另外考官的意思是
1->2->3->4->5
抽取1-5中随机数2,
则链表为1->3->4->5
再抽取1-4中随机数2,
则是取3了。

linuxcici

原帖由 cjaizss 于 2008-3-26 00:10 发表
另外考官的意思是
1->2->3->4->5
抽取1-5中随机数2,
则链表为1->3->4->5
再抽取1-4中随机数2,
则是取3了。

喔..原来这个意思. 他那时候用python写的. 还有他说那高效方法是必做题目.

cjaizss

原帖由 scutan 于 2008-3-25 23:16 发表
说说我的愚见。
第一个题我觉得应该用位运算来做，在编程珠玑第一章有讲解。
第二个题就是用字符串来保存很长的数来进行加和乘，在ACM的题中也有。

用位来做，类似于编译器里常用的“循环展开”，利用硬件的性质达到提速的目的，但是不降低算法复杂度级别（时间、空间）

linuxcici

自己想的一种方法. 不知道行不行得通

1. 
   
2. 要是碰巧
   
3. 第1次=1
   
4. 第2次=2
   
5. 第3次=3
   
6. 现在就随机3次了.
   
7. 第1次和第3次加就=4.
   
8. 第2次和第3次加就=5.    结论: 抽3次随机数.可以得5次结果. 所以.
   
9. 
   
10. 1-10抽5个是常数级.
    
11. 1-100抽50个是循环10次.
    
12. 1-1百万抽五十万 循环10万次
    
13. 
    
14. 
    
15. int tmp[100万];//用来保存临时的数据
    
16. int b=1;
    
17. int n1;
    
18. int n2;
    
19. int n3;
    
20. int n4;
    
21. int n5;
    
22. int 搞不定=0;
    
23. int result[50万];
    
24. int count=0;
    
25. 
    
26. 
    
27. 
    
28.    tmp清0;
    
29. 
    
30. for(;b<10万次;b++)
    
31. {
    
32. 
    
33.    one:
    
34.        n1=random(100万);
    
35.        if(tmp[n1]是空)
    
36.        tmp[n1]=n1;  //随机的数字放到临时对应的下标
    
37.        else
    
38.          goto one;      
    
39.    two:
    
40.        n2=random(100万);
    
41.        if(tmp[n2]是空)
    
42.        tmp[n2]=n2;               
    
43.        else
    
44.          goto two;
    
45. 
    
46.    three:
    
47.        n3=random(100万);
    
48.        if(tmp[n3]是空)
    
49.        tmp[n3]=n3;               
    
50.        else
    
51.          goto three;
    
52.               
    
53.      if(tmp[one+three]是空)
    
54.        n4=tmp[one+three]=one+three;
    
55.      else if(tmp[one+tow]是空)
    
56.        n4=tmp[one+tow]=one+tow;
    
57.      else
    
58.          搞不定=1;
    
59. 
    
60.      if(tmp[tow+three]是空)
    
61.        n5=tmp[tow+three]=tow+three;
    
62.      else
    
63.          搞不定=1;  
    
64.                
    
65.       if(搞不定==1)
    
66.       {
    
67.            tmp[n1]=tmp[n2]=tmp[n3]=tmp[one+three]=tmp[one+tow]=tmp[tow+three]=0;
    
68.            b--;//当本次循环不成功
    
69.            continue;
    
70.       }
    
71.       else  //满足了,代表一次循环可以有5个不同的随机数
    
72.       {
    
73.            result[count]=n1;
    
74.            count++;
    
75.            result[count]=n2;
    
76.            count++;
    
77.            result[count]=n3;
    
78.            count++;
    
79.            result[count]=n4;       
    
80.            count++;
    
81.            result[count]=n5;
    
82.            count++;
    
83. 
    
84.       }  
    
85.         
    
86.               
    
87.                  
    
88. }
    
89. 
    
90. 
    

复制代码

[ 本帖最后由 linuxcici 于 2008-3-26 01:00 编辑 ]

linuxcici

那考官给我十分钟左右叫我想优化算法啊. 到最后他两写了个自己也说是个效率低的方法. 真是无奈. 然后直接out了我

linuxcici

哈. 那考官说我. 2个随机数加起来不是随机数. 就好象说两个堆沙子加起来不是堆沙子...哎...真给人BS了