Google面试题中的两道趣题

看看下面两道题，它的解答非常简单，即使没学过信息学的人也可以想到答案。你能在多短的时间内想出问题的算法来？一小时？一分钟？一秒钟？

1. 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。

2. 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*…*A[n]/A[i]。你不能使用除法运算。

Solution:

1. 遍历链表，给每个元素赋一个0到1之间的随机数作为权重（像Treap一样），最后取出权重最大的k个元素。你可以用一个堆来维护当前最大的k个数。

2. 从前往后扫一遍，然后从后往前再扫一遍。也就是说，线性时间构造两个新数组，P[i]=A[1]*A[2]*…*A[i]，Q[i]=A[n]*A[n-1]*…*A[i]。于是，B[i]=P[i-1]*Q[i+1]。

突然想到，给别人(MM?)介绍信息学时，用这两道题当例子挺合适的。