三个面试试题

1、假设有一个无限长度的单向链表，要求只遍历一次就得到前k大的元素该怎么办？
2、遍历一次无限长度的单向链表，然后从中等概率的随机抽取k个元素。
3、长度为n的数组，遍历得到数组最小值的那个临时变量被update的期望次数是多少？

1、是不是维护一个大小为k的大顶堆？
2、读不懂意思
3、讨论最小值出现在各个位置是啥情况，出现递归的情况，写不出式子

第二个有问题吧？ 长度无限如何等概率呢？