笔试题集锦

    数据库1中存放着a类数据，数据库2中存放着以天为单位划分的表30张（比如 table_20110909,table_20110910,table_20110911）,总共是一个月的数据。表1中的a类数据中有一个字段 userid来唯一判别用户身份，表2中的30张表（每张表结构相同）也有一个字段userid来唯一识别用户身份。如何判定a类数据库的多少用户在数据 库2中出现过？
思路：在网上找到的一个比较好的回复答案是这样的。
建立一张用户表，UserInMonth（userid）表里面只放不重复的用户Id，把 （table_20110909,table_20110910,table_20110911）的用户Id放到一张User表里面userid都统一放 到这个表里面去。判断的时候select count(1) from user u inner join UserInMonth um on u.userid=um.userid.

已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10。
（参考答案：这题主要考的是对概率的理解。程序关键是要算出rand10，1到10，十个数字出现的考虑都为10%.根据排列组合，连续算两次rand7出现的组合数是7*7=49，这49种组合每一种出现考虑是相同的。怎么从49平均概率的转换为1到10呢？下面是网上给出的一中方法：
1.rand7执行两次，出来的数为a1.a2.
2.如果a1*7+a2<40,b=(a1*7+a2)/10+1,如果a1*7*a2>=40,重复第一步）。参考代码如下所示：

int rand7()
{
  return rand()%7+1;
}

int rand10()
{
  int a71,a72,a10;
  do
  {
    a71= rand7()-1;
    a72 = rand7()-1;
    a10 = a71 *7 + a72;
  } while (a10>= 40);
  return (a71*7+a72)/4+1;
}

  两个数组a[N]，b[N]，其中A[N]的各个元素值已知，现给b[i]赋值，b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i]；
要求：
1.不准用除法运算
2.除了循环计数值，a[N],b[N]外，不准再用其他任何变量（包括局部变量，全局变量等）
3.满足时间复杂度O（n），空间复杂度O（1）。

    说白了，你要我求b=a[0]*a*...a[i-1]*a*a[i+1]..*a[N-1]/a ，就是求：a[0]*a[1]*...a[i-1]*a[i+1]..*a[N-1]。只是我把a[i]左边部分标示为left[i]，b[i]右边部分 标示为right[i]，而实际上完全不申请left[i]，与right[i]变量，之所以那样标示，无非就是为了说明：除掉当前元素a[i]，其他所 有元素(a[i]左边部分，和a[i]右边部分)的积。读者你明白了么?

    下面是此TX笔试题的两段参考代码，如下：

//ncicc
b[0] = 1;
for (int i = 1; i < N; i++)
{
  b[0] *= a[i-1];
  b[i] = b[0];
}
b[0] = 1;
for (i = N-2; i > 0; i--)
{
  b[0] *= a[i+1];
  b[i] *= b[0];
}
b[0] *= a[1];

上面第二段代码最后一行的意义是：我们看第二个循环，从N-2到 1；再看for循环中b[0]的赋值，从N-1到2，而根据题目要求b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i]，b[0]应等于a[1]*a[2]* ....a[N-1],所以这里手动添加a[1]。

如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，问如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）。

思路：1 判断各自素数乘积是否相等。

2 建立hash索引，字符一样的字符串索引是一样的。

求根号n的值  

如何求根号2的值，并且按照我的需要列出指定小数位，比如根号2是1.141 我要列出1位小数就是1.1 2位就是1.14， 3位就是1.141...... 等。
思路： 二分。2位的话，应该精确到0.001，这样可以保证小数点后的第二位是稳定的。这里是用的right-left
double sqrtn(int n, int m)
{
    double ln = n*1.0;
    double left  = 0;
    double right = ln;
    double err = 0.1, mid;
    for(int i=0;i    {
        err *= 0.1;
    }
    printf("err:%lf\n", err);
    while(true)
    {
        mid = (left + right) / 2;
        printf("mid: %lf\n",mid);
        if(mid*mid > ln)
        {
            right = mid;
        }
        else if(mid*mid < ln)
        {
            left = mid;
        }
        else
        {
            return mid;
        }
        if(right - left < err)
        {
            return mid;
        }
    }
}

：服务器内存1G，有一个2G的文件，里面每行存着一个QQ号（5-10位数），怎么最快找出出现过最多次的QQ号。
    首先你要注意到，数据存在服务器，存储不了（内存存不了），要想办法统计每一个qq出现的次数。
比如，因为内存是1g，首先 你用hash 的方法，把qq分配到10个（这个数字可以变动，比较）文件（在硬盘中）。
    相同的qq肯定在同一个文件中，然后对每一个文件，只要保证每一个文件少于1g的内存，统计每个qq的次数，可以使用hash_map(qq, qq_count)实现。然后，记录每个文件的最大访问次数的qq，最后，从10个文件中找出一个最大，即为所有的最大。


如果用一个循环数组q[0..m-1]表示队列时,该队列只有一个队列头指针front,不设队列尾指针rear，求这个队列中从队列投到队列尾的元素个数（包含队列头、队列尾）。

这个题分两种情况，一种是rear>front，此时n=rear-front+1；

由于是循环队列，如果是rear

所以将其综合一下就是：(rear-front+1+m)%m。

人人笔试1：一个人上台阶可以一次上1个，2个，或者3个，问这个人上n层的台阶，总共有几种走法？

f(1) = 1 // 只有一个台阶时只有一种走法
f(2) = 2 // 2个台阶时2种走法
f(3) = f(1) + f(2) + 1 = 4
/* 对于3阶，先走一阶还有f(3-1)=2种方法，先走两阶还有f(3-2)=1种方法，直接走3阶则有0种方法（但本身也算一种方法） */
因此
f(n) = f(n-1) + f(n-2) + f(n-3) // 其他情况

在如下8*6的矩阵中，请计算从A移动到B一共有多少种走法？要求每次只能向上挥着向右移动一格，并且不能经过P；

							B
			P
A

A走到B共需要12步，其中7步必须向右，5步必须向上，但次序可以不同，因此是C(7,12)，要求P不能走，那么走到P的可能次数是C(3,6)，从P走到B的可能次数是C(4,6)，因此结果是C(7,12) – C(3,6)*C(4,6)=492

在一场激烈的比赛开始前，售票工作正在紧张地进行中。每张票为50元。现在有2n个人排队购票，其中n个人手持50元的钞票，另外n个人手持100元的钞票，假设开始售票是售票处没有零钱，问者2n个人有多少种排队方式，不至于导致找不开的局面。
思路：这道题是编程之美里面的一道题，里面提供了一种很奇妙的解法.
首先，从题意出发，如果要不至于找不开的局面，我们假设从队首开始的某一段k,k里面持有50的人一定和持有100的人一样多或至少多一个，而且第一个人一定是持有50的人。那么其实2n个人，总的排队可能性就有C（2n,n）种情况，其中既有符合题目要求的，也有不符合题目要求的。现在，问题是，我们怎样来求得符合题目要求的。
为了方便，我们这里可以设置持有50元的个数为0，持有100元个数的为1，那么，我们这里就有50个0和50个1了，对于0和1组合成的排列方式，我们假设,从队列开始，存在某一个最小的数字m，m里面0的个数比1少一，即找不开，那么在下面的2n-m的队列中，1的数量就比0多1,这个队列是一个不符合条件的队列，现在，我们要考虑怎样把这些队列的个数给求出来。
我们试想一下，r如果现在是有n-1个0和n+1个1，那么可能的排列组合就有C(2n,n-1),在上面，我们知道一个不合法的队列是从队列开始，存在某一个最小的数字m，m里面0的个数比1少一，在后面2n-m个数中，1的个数比0多一，如果我们把这2n-m个数中的0变成1，1编程0，那么，就变成了有n-1个0和N-1个一了，那么刚好对应到
有n-1个0和n+1个1的这种情况。即是说，不合法组合的情况其实是跟有n-1个0和n+1个1的组组合是一致的，所以，可以得出共有C（2n,n）-C（2n,n-1）种情况。

甲、乙两个人在玩猜数字游戏，甲随机写了一个数字，在[1，100]区间之内，将这个数字写在了一张纸上，然后乙来猜。
如果乙猜的数字偏小的话，甲会提示：“数字偏小”
一旦乙猜的数字偏大的话，甲以后就再也不会提示了，只会回答“猜对 或 猜错”
问： 乙至少猜    多少次  猜可以准确猜出这个数字，在这种策略下，  乙猜的第一个数字是多少？？？
答案：猜测序列是14,、27、39、50、60、69、77、84、90、95、99
因为无论第几次猜大了，最终的总次数总是14。     这个题目类似于一道Google面试题 ：  扔玻璃球求最高楼层。。
一道关于动态规划的面试题——Google面试题：扔玻璃珠
某 幢大楼有100层。你手里有两颗一模一样的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候，一定会有两个结果，玻璃珠碎了或者没碎。这幢大楼有个临界楼层。 低于它的楼层，往下扔玻璃珠，玻璃珠不会碎，等于或高于它的楼层，扔下玻璃珠，玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式，使得在该方 式下，最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效的方式。
首先，为了保存下一颗玻璃珠自己玩，就采用最笨的办法吧：从第一层开始试，每次增加一层，当哪一层扔下玻璃珠后碎掉了，也就知道了。不过最坏的情况扔的次数可能为100。
当 然，为了这一颗玻璃珠代价也高了点，还是采取另外一种办法吧。随便挑一层，假如为N层，扔下去后，如果碎了，那就只能从第一层开始试了，最坏的情况可能为 N。假如没碎，就一次增加一层继续扔吧，这时最坏的情况为100-N。也就是说，采用这种办法，最坏的情况为max{N, 100-N+1}。之所以要加一，是因为第一次是从第N层开始扔。
不 过还是觉得不够好，运气好的话，挑到的N可能刚好是临界楼层，运气不好的话，要扔的次数还是很多。不过回过头看看第二种方式，有没有什么发现。假如没摔的 话，不如不要一次增加一层继续扔吧，而是采取另外一种方式：把问题转换为100-N，在这里面找临界楼层，这样不就把问题转换成用递归的方式来解决吗？看 下面：
假如结果都保存在F[101]这个数组里面，那么：
F[N]=100-N，
F[100]=min（max（1，1+F[N-1]），max（2，1+F[N-2]），……，max（N-1，1+F[1]））;
看出来了没有，其实最终就是利用动态规划来解决这个问题。
下面是自己随便写的C++代码：
[cpp] view plaincopy
#include  
using namespace std;  
  
int dp[101] = { 0 };  
  
void solve()  
{  
    int i , j , k;  
    for(i = 2 ; i < 101 ; ++i)  
    {  
        dp[i] = i;  
        for(j = 1 ; j < i ; ++j)  
        {  
            k = (j>=(1 + dp[i-j])) ? j : (1 + dp[i-j]);  
            if(dp[i] > k)  
                dp[i] = k;  
        }  
    }  
}  
  
int main(void)  
{  
    dp[0] = 0 , dp[1] = 1;  
    solve();  
    printf("%d\n",dp[100]);  
    return 0;  
}  
输出结果为14。也就是说，最好的方式只要试14次就能够得出结果了。
答案是先从14楼开始抛第一次；如果没碎，再从27楼抛第二次；如果还没碎，再从39楼抛第三次；如果还没碎，再从50楼抛第四次；如此，每次间隔的楼层少一层。这样，任何一次抛棋子碎时，都能确保最多抛14次可以找出临界楼层。
证明如下：
1、第一次抛棋子的楼层：最优的选择必然是间隔最大的楼层。比如，第一次如果在m层抛下棋子，以后再抛棋子时两次楼层的间隔必然不大于m层（大家可以自己用反证法简单证明）
2、从第二次抛棋子的间隔楼层最优的选择必然比第一次间隔少一层，第三次的楼层间隔比第二次间隔少一层，如此，以后每次抛棋子楼层间隔比上一次间隔少一层。（大家不妨自己证明一下）
3、所以，设n是第一次抛棋子的最佳楼层，则n即为满足下列不等式的最小自然数：
  不等式如下：  1+2+3+...+(n-1)+n  >=   100
由上式可得出n=14
即最优的策略是先从第14层抛下，最多抛14次肯定能找出临界楼层。

数据存储在磁盘上的排列方式会影响I/O服务的性能，一个圆环的磁道上有10个物理块，10个数据记录R1------R10存放在这个磁道上，记录的安排顺序如下表所示：

物理块	1	2	3	4	5	6	7	8	9	10
逻辑记录	R1	R2	R3	R4	R5	R6	R7	R8	R9	R10

假设磁盘的旋转速度为20ms/周，磁盘当前处在R1的开头处，若系统顺序扫描后将数据放入单缓冲区内，处理数据的时间为4ms（然后再读取下个记录），则处理这10个记录的最长时间为（C）

A、180ms                           B、200ms                          C、204ms                             D、220ms

解答：

首先从磁盘的转速：20ms/圈，我们可以知道：读取 一条记录需要2ms。值得注意的一点是：处理一条记录的前提，是将其读出来。所以处理第一条记录时，要先将其读取出来，再进行处理，所以处理R1所需时间 为2ms+4ms，当R1处理完时，磁头已经转到了R4的位置，此时要将其调整到R2的位置，需要经过R5，R6，R7，R8，R9，R10，R1，这样 要耗16ms的时间，再加上读取R2需要2ms以及处理数据的4ms，R2的总处理时间应为22ms。所以2+4+(16+2+4)*9=204ms。而 优化后的排列顺序应为：R1，R8，R5，R2，R9，R6，R3，R10，R7，R4，这样的排列顺序刚好是处理完R1，磁头就到了R2的位置，直接读 取R2，处理R2，处理完R2，磁头又到了R3的位置，依此类推，每条记录的读取及处理时间为：2ms+4ms=6ms，所以总时间为： (2+4)*10=60ms。


已知一个函数f可以等概率的得到1-5间的随机数，问怎么等概率的得到1-7的随机数，

算法思路是：
1. 通过 rand5()*5+rand5() 产生 6 7 8 9 10 11 …… 26，27 28 29 30 这25个数，每个数的出现机率相等
2. 只需要前面 3*7 个数，所以舍弃后面的4个数
3. 将 6 7 8 转化为 1，9 10 11 转化为 2，……，24 25 26 转化为 7。公式是 (a-3)/3

1. int rand7()
   
2. {
   
3. int a;
   
4. while( (a=rand5()*5+rand5()) > 26 );
   
5. return (a-3)/3;
   
6. }