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

agaric

楼上做法也是可以滴。 要看具体的要求乐。

cjaizss

原帖由 hll 于 2008-3-26 10:18 发表
第一题遍历一遍就可以了，
#define M 1000000
int a[M];
从第一个开始遍历数组每次取0，1之间的随机数，根据是0或者1把数组分为两部分，取个数不小于500000的那部分的前500000个就可以了

这个这个..........分布改变的太离谱了点...........

benjiam

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

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

这个算法是正确的.

其实可以用2个数组来做
a[100]
b[50]
for (int i = 0; i < 50;i +) {
    int v = rand() % (100-i);
    b = a[v];
    switch( a[100-i], a[v]);   
}

benjiam

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

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


很明显是用字符串联模拟大数运行.  有一些低效. 但是高效算法 不知道怎么做.

jigloo

答案来了:
1. 自己用循环取余法自己用实现随机算法，可以保证不重复。
2. 用int[]来模拟大数，当然你需要实现一个tostring方法。

python的话, 这两题只要import random和import gmpy就可以秒杀了。

painkiller0513

横向链表结点｛
    10的整数陪，用于检索；
    纵向链表中结点个数；
    指向纵向链表的指针；
    指向横向链表的下一个结点；
｝

纵向链表结点 ｛
    存放数值；
    指向纵向链表的下一个结点;
}

存入数据时保证横纵链表有序，这样可以用二分查找法；
if (横向链表第2字段>=10) 放弃存入此数；

UCfree

可以用洗扑克牌算法

#define MAX      1000000
#define HALF    MAX / 2

int a[MAX];

for (j = 0; j < HALF; j++){
        val = j + rand() % (MAX -j);
       
        tmp = a[j];
        a[j] = val;
        a[val] = tmp;
}

a[0] -> a[HALF -1]                前50万个数
或
a[HALF] -> a[MAX - 1]          后50万个数
都可作为结果   ^_^

[ 本帖最后由 UCfree 于 2008-3-26 17:26 编辑 ]

emacsnw

原帖由 linuxcici 于 2008-3-25 07:10 发表
面试主要看看题目而已.

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



记住喔. 是高效的方法. 今天的笔试题目. 大约要用10分钟完成. 游戏python职位. 我做偏了今天. 因为没听清楚是五十万个不 ...

第一题感觉这样做比较好：
假设题意是n个数字里抽取m个不同的数字，并且每个数字抽到的概率相等。

1. 
   
2. // choose m distinct numbers from A[1..n], and return the numbers as a list.
   
3. function choose(A, n, m) {
   
4.   if (m == n) return A[1..n];
   
5.   sample u ~ [0, 1);
   
6.   if (u < m/n) return {choose(A, n-1, m-1), A[n]} // accept A[n]
   
7.   else return {choose(A, n-1, m)} // reject A[n]
   
8. }
   

复制代码

这样可以保证抽到的m个数概率都是m/n.

[ 本帖最后由 emacsnw 于 2008-3-26 09:46 编辑 ]

sasc

吼一下。。
太混。。
下次遇到这样的题。。
我直接回家。。

yuanchengjun

1，
100万个数，放内存啊，好像不到4兆吧，依次1，2，3，......
取过一个数以后，把最后一个数拿到当前的位置。
每次最大值一次递减1。

第一次，随机（1 ~ 100w），假设随到位置33，把 第100w个数，放到33。
第二次，随机（1 ～ 100w-1），假设随到位置66，吧第(100w - 1)个数，放到66。
第三次，随机（1 ～ 100w-2），假设随到位置88，吧第(100w - 2)个数，放到88。
……

2，
让他看小学课本去，一定能找到答案。

[ 本帖最后由 yuanchengjun 于 2008-3-27 16:21 编辑 ]