google面试题（三）

算法题一：Given 1 GB memory, input a file which contians 4 billion integers,
output one integer that is not in the file. What if you have only 10 MB
memory?

算法题二：There are 100 hundred sorted arrays, and each of them contains 100
numbers. Give an algorithm to merge them into a single sorted array, using
only one temporary array in the middle steps.

编程题：Input an integer array of size n and an integer k (k<=n), output all subsets of size k.

思路：
(一) 整型变量的值的范围是-（2的15次方）至（2的15次方）-1，因此为数组开辟2^16的空间，也就是64K的大小，设置一定大小的缓冲(几十K左右)，把文件读入，依次统计缓冲区的整数出现的次数，次数为0的即位结果
(二) 使用胜者树或败者树，K=100路归并，用one temporary array来构造以及重构树。或者
1. 取100个数组中各自的第一个数，组成一个最小堆。
2. 输出堆中的最小值，并且把这个最小值对应的数组的第二个数加入堆，并且调整。
3. 重复步骤2直到所有数组中的值都被输出。
显然前者效率较高。
空间需要为一个长度为10000的临时数组。
(三) for i=0 to n-k-1 do {
  for j=i to i+k-1 do{
    out(a[j]+" ");
  }
  out("\n");
}
循环次数nk-k^2, 时间复杂度0(n)

评论

1 楼 lingguang1997 2011-10-25  

第三题的解法是错的吧，只能打出连续的组合。