Google笔试卷-2011年

1、程序设计：给定2个大小分别为n, m的整数集合，分别存放在两个数组中 int A[n], B[m]，输出两个集合的交集。

2、银行取款排队模拟
假设银行有4个柜台，假设某天有200位客户来办理业务，每个客户到达银行的时间和业务处理时间分别用两个数组arrive_time 和 process_time 来描述。
请写程序计算所有客户的平均等待时间，假设每个客户在去到营业部之后先拿号排队，然后在任意一个柜台有空闲的时候，号码数最小的客户上去办理，假设所有的客户拿到号码之后不会因为银行众所周知的慢而失去耐心走掉。

3、对数值范围为 0到 n^2-1的 n 个整数进行排序。请详细描述算法（若引用经典算法也需要给出具体实现），并分析算法的时间复杂度和空间复杂度。要求时间复杂度尽量优化，在此前提下空间复杂度尽量优化。

参考答案：

1、Java代码：

public static int[] intersection(int[] a,int[] b){ 
    int aLen = a.length; 
    int bLen = b.length; 
    int aIndex = 0; 
    int bIndex = 0; 
    int cIndex = 0; 
    int[] c = new int[aLen]; 

    Arrays.sort(a); 
    Arrays.sort(b); 

    while(aIndex != aLen && bIndex != bLen){ 
        if(a[aIndex] == b[bIndex]){ 
        c[cIndex++] = a[aIndex]; 
        aIndex++; 
        bIndex++; 
        }else if(a[aIndex ] < b[bIndex]){ 
            aIndex++; 
        }else{ 
            bIndex++; 
        } 
    } 

    if(cIndex != aLen){ 
    c = Arrays.copyOf(c ,cIndex); 
    } 
    return c; 
} 

2、参考代码：

int arrive_time[] = new int[] { 10, 12, 15, 17, 18, 19, 19, 20, 25 };
int process_time[] = new int[] { 1, 18, 10, 19, 16, 8, 6, 7, 3 };
int total = 0, lastTime = 0;
int atms[] = new int[] { 0, 0, 0, 0 };
for (int i = 0; i < process_time.length; i++) {
    int time = arrive_time[i] - lastTime;
    for (int j = 0; j < atms.length; j++) {
        atms[j] -= time;
    }
    lastTime = arrive_time[i];
    boolean wait = true;
    for (int j = 0; j < atms.length; j++) {
        if (atms[j] <= 0) {
            atms[j] = process_time[i];
            wait = false;
            break;
        }
    }
    if (wait) {
        int temp = atms[0];
        for (int j = 0; j < atms.length; j++) {
            for (int j2 = j + 1; j2 < atms.length; j2++) {
                if (atms[j2] < atms[j]) {
                    temp = atms[j2];
                    atms[j2] = atms[j];
                    atms[j] = temp;
        }
    }
}
        total += atms[0];
        atms[0] += process_time[i];
    }
}
System.out.println((double) total / arrive_time.length);

3、题目要求说  “要求时间复杂度尽量优化”，所以我们肯定要想到基数排序、计数排序、桶排序等，这些时间复杂度比较小  （ O(n) ）