2012年最新C和C++程序员笔试题 - 图文

0 0 1

表示编号为1的项目在第一轮面试编号为1的同学，第二轮面试编号为3的同学，第三轮面试编号为2的同学 编号为2的项目在第一轮面试编号为3的同学，第二轮面试编号为1的同学，第二轮不用面试 编号为3的项目在第一轮和第二轮都不用面试，第三轮面试编号为1的同学

4**9 的笔试题，比较简单： 1.求链表的倒数第二个节点

2.有一个整数数组，求数组中第二大的数 阿里巴巴二道题 第一道：

对于给定的整数集合S，求出最大的d，使得a+b+c=d。a,b,c,d互不相同，且都属于S。集合的元素个数小于等于2000

个，元素的取值范围在[-2^28，2^28 - 1]，假定可用内存空间为100MB，硬盘使用空间无限大，试分析时间和空

间复杂度，找出最快的解决方法。 点评：

@绿色夹克衫：两两相加转为多项式乘法，比如(1 2 4 6) + (2 3 4 5) => (x + x^2 + x^4 + x^6)*(x^2 + x^3 + x^4 + x^5) 。 阿里巴巴第二道(研发类)

笔试题1，原题大致描述有一大批数据，百万级别的。数据项内容是：用户ID、科目ABC各自的成绩。其中用户ID为0~1000万之间，且是连续的，可以唯一标识一条记录。科目ABC成绩均在0~100之间。有两块磁盘，空间大小均为512M，内存空间64M。

1) 为实现快速查询某用户ID对应的各科成绩，问磁盘文件及内存该如何组织； 2) 改变题目条件，ID为0~10亿之间，且不连续。问磁盘文件及内存该如何组织；

3) 在问题2的基础上，增加一个需求。在查询各科成绩的同时，获取该用户的排名，问磁盘文件及内存该如何组织。 笔试题2：代码实现计算字符串的相似度。 点评：和计算两字符串的最长公共子序列相似。

设Ai为字符串A(a1a2a3 … am)的前i个字符（即为a1,a2,a3 … ai） 设Bj为字符串B(b1b2b3 … bn)的前j个字符（即为b1,b2,b3 … bj） 设 L(i , j)为使两个字符串和Ai和Bj相等的最小操作次数。 当ai等于bj时 显然L(i, j)=L(i-1, j-1) 当ai不等于bj时

若将它们修改为相等，则对两个字符串至少还要操作L(i-1, j-1)次 若删除ai或在Bj后添加ai，则对两个字符串至少还要操作L(i-1, j)次 若删除bj或在Ai后添加bj，则对两个字符串至少还要操作L(i, j-1)次 此时L(i, j)=min( L(i-1, j-1), L(i-1, j), L(i, j-1) ) + 1

显然，L(i, 0)=i，L(0, j)=j, 再利用上述的递推公式，可以直接计算出L(i, j)值。具体代码请见这：

??

9月14日，小米笔试，给一个浮点数序列，取最大乘积子序列的值，例如 -2.5，4，0，3，0.5，8，

-1，则取出的最大乘积子序列为3，0.5，8。 点评： 解法一、

或许，读者初看此题，自然会想到最大乘积子序列问题类似于最大子数组和问题：然实则具体处理起来诸多不同，为什么呢，因为乘积子序列中有正有负也还可能有0。

既如此，我们可以把问题简化成这样：数组中找一个子序列，使得它的乘积最大；同时找一个子序列，使得它的乘积最小（负数的情况）。因为虽然我们只要一个最大积，但由于负数的存在，我们同时找这两

个乘积做起来反而方便。也就是说，不但记录最大乘积，也要记录最小乘积。So，

我们让maxCurrent表示当前最大乘积的candidate， minCurrent反之，表示当前最小乘积的candidate。

（用candidate这个词是因为只是可能成为新一轮的最大/最小乘积）， 而maxProduct则记录到目前为止所有最大乘积candidates的最大值。

由于空集的乘积定义为1，在搜索数组前，maxCurrent,minCurrent,maxProduct都赋为1。

假设在任何时刻你已经有了maxCurrent和minCurrent这两个最大/最小乘积的candidates，新读入数组的元素x(i)后，新的最大乘积candidate只可能是maxCurrent或者minCurrent与x(i)的乘积中的较大者，如果x(i)<0导致maxCurrent

当任何时候maxCurrent<1，由于1（空集）是比maxCurrent更好的candidate，所以更新maxCurrent为1，类似的可以更新minCurrent。任何时候maxCurrent如果比最好的maxProduct大，更新maxProduct。 具体代码如下：

template ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??

Comparable maxprod( const vector&v) { int i;

Comparable maxProduct = 1; Comparable minProduct = 1; Comparable maxCurrent = 1; Comparable minCurrent = 1; //Comparable t;

for( i=0; i< v.size() ;i++) {

maxCurrent *= v[i]; minCurrent *= v[i];

if(maxCurrent > maxProduct) maxProduct = maxCurrent; if(minCurrent > maxProduct) maxProduct = minCurrent; if(maxCurrent < minProduct) minProduct = maxCurrent; if(minCurrent < minProduct) minProduct = minCurrent; if(minCurrent > maxCurrent) swap(maxCurrent,minCurrent); if(maxCurrent<1) maxCurrent = 1; //if(minCurrent>1) // minCurrent =1;

?? ?? ?? ??

}

return maxProduct; }

解法二、

本题除了上述类似最大子数组和的解法，也可以直接用动态规划求解（其实，上述的解法一本质上也是动态

规划，只是解题所表现出来的具体形式与接下来的解法二不同罢了。这个不同就在于下面的解法二会写出动态规划问题中经典常见的状态转移方程，而解法一是直接求解）。具体解法如下：

假设数组为a[]，直接利用动归来求解，考虑到可能存在负数的情况，我们用Max[i]来表示以a[i]结尾的最大连续子序列的乘积值，用Min[i]表示以a[i]结尾的最小的连续子序列的乘积值，那么状态转移方程为： Max[i]=max{a[i], Max[i-1]*a[i], Min[i-1]*a[i]}; Min[i]=min{a[i], Max[i-1]*a[i], Min[i-1]*a[i]}; 初始状态为Max[1]=Min[1]=a[1]。代码如下：

/* ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??

给定一个整数数组，有正有负数，0，正数组成,数组下标从1算起

求最大连续子序列乘积，并输出这个序列，如果最大子序列乘积为负数，那么就输出-1 用Max[i]表示以a[i]结尾乘积最大的连续子序列

用Min[i]表示以a[i]结尾乘积最小的连续子序列 因为有复数，所以保存这个是必须的 */

void longest_multiple(int *a,int n){ int *Min=new int[n+1](); int *Max=new int[n+1](); int *p=new int[n+1](); //初始化

for(int i=0;i<=n;i++){ p[i]=-1; }

Min[1]=a[1]; Max[1]=a[1]; int max_val=Max[1]; for(int i=2;i<=n;i++){

Max[i]=max(Max[i-1]*a[i],Min[i-1]*a[i],a[i]); Min[i]=min(Max[i-1]*a[i],Min[i-1]*a[i],a[i]); if(max_val

if(max_val<0) printf(\else

printf(\//内存释放

?? ?? ??

delete [] Max; delete [] Min; }

变种

此外，此题还有另外的一个变种形式，即给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意（N-1）个数的组合中乘积最大的一组，并写出算法的时间复杂度。

我们可以把所有可能的（N-1）个数的组合找出来，分别计算它们的乘积，并比较大小。由于总共有N个（N-1）个数的组合，总的时间复杂度为O（N2），显然这不是最好的解法。 OK，以下解答来自编程之美 解法1

解法2

此外，还可以通过分析，进一步减少解答问题的计算量。假设N个整数的乘积为P，针对P的正负性进行如下分析（其中，AN-1表示N-1个数的组合，PN-1表示N-1个数的组合的乘积）。

1.P为0 那么，数组中至少包含有一个0。假设除去一个0之外，其他N-1个数的乘积为Q，根据Q的正负性进行讨论：Q为0

说明数组中至少有两个0，那么N-1个数的乘积只能为0，返回0； Q为正数

返回Q，因为如果以0替换此时AN-1中的任一个数，所得到的PN-1为0，必然小于Q； Q为负数

如果以0替换此时AN-1中的任一个数，所得到的PN-1为0，大于Q，乘积最大值为0。 2. P为负数

根据“负负得正”的乘法性质，自然想到从N个整数中去掉一个负数，使得PN-1为一个正数。而要使这个正数最大，这个被去掉的负数的绝对值必须是数组中最小的。我们只需要扫描一遍数组，把绝对值最小的负数给去掉就可以了。 3. P为正数

类似地，如果数组中存在正数值，那么应该去掉最小的正数值，否则去掉绝对值最大的负数值。