1，有一个文件中存储了40个亿个uc账号ID，每个uc账号ID长度为四个字节整数，内存为1GB，写出一个算法：求出这个文件里的账号ID整数里不包含的一个整数，并描述算法设计主要思路。

2，在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行，同一列或同一斜线上，问有多少种摆法。若使用递归算法，最高可得2/3分，非递归算法最高可得满分。

我是来学东西的

第1题主要是大数处理吧，16GB的数据，用1GB怎么算。其实关键是这个数据文件是怎么储存出来的，如果它写入时已被排序，则不存在问题；如果没有排序，则变成排序问题。关键是排序算法。在数据库系统中，排序是不需你自己处理的事情。

我有个算法，

做bit hash.

内存里面维护一个hash表，4字节表示的范围是2^32个数据， 能cover 40亿个ID各不一样。

从文件里面读数据,并建立hash表.

然后从i iterator to 2^32找第一个在hash表里没有 key-value对的值。

全部抑或

也有另外办法的，像电话号码一样，分区投放UC号。在相对小的范围内检索数据比总在全集中检索容易一些，当某一区段全满之后，这个区域就可以从全集中排除出去了。又或者，一开始就用排除法，从可用数据集中往外取数，留下的都是可用的，这个在申请号码时反应最快。

根本不可行，你根本不可能把40亿个数一次读入内存。 40亿 约为2^28.5, 40亿个int 约为2^30.5byte.
你也不能创建一个全集，因为1G内存只有2^30byte.
全集是2^32 byte

大家有没有更加好的见解啊