解答一下google intern 那两个算法题

算法题：
Q1. 给你一大串数字，你不知道有多少个数字，如何从中*随机等概率*地挑出一个数字？问一个恒定内存的方法
Q2. 给你一大串价格，比如，股价。如何决定最好的买入和卖出时机？

A1:假如数字是以流的方式一次读一个的： 第一个进来存到变量t里，第二个进来有1/2的机会替代现有的t的值.... 第i个有1/i个机会替代现有的值则i号元素被被选中的几率为(1/i)*(i/i+1)*(i+1/i+2)..(n-1)/n = 1/n (n为总数，在你一个个的读取数的时候最后你总知道有几个数，只不过你不需要把它们都存下来而已)

A2:数学归纳法（递归）：遍历数组记录所有波峰波谷到一个数组然后再以数学归纳发的眼光求解，比较简单就不具体说了

恩, 赞

A2这个。。。。assumption是符合历史数据的model一定可以预测未来，但是这个assumption是不成立的啊，brownian motion的假设就是下一步的方向独立于前一步啊
而且误差也不符合正态分布
sigh

A2这个。。。。assumption是符合历史数据的model一定可以预测未来，但是这个assumption是不成立的啊，brownian motion的假设就是下一步的方向独立于前一步啊
而且误差也不符合正态分布
sigh
小K 发表于 2011-2-5 11:26

统计老妖怪出来了……

统计老妖怪出来了……
zach 发表于 2011-2-5 13:26

小心小K姐姐打你屁股，哈哈

Q2的表述好像很不确切，到底是要预测还是要已知价格做最优化？从表述来看象后者。后者也更像是一个算法题，而非统计题。前者的话，如果这些价格完全不相关，那么做多少归纳，建多少模型，也是没有用的吧。所以我觉得这道题如果不做更确切的表述，那就没法做确切的回答。

我晕，第二题你们怎么都想那么复杂啊。。。
不就是一个数组，比如0,2,-1,3,4,5,-3,1，4,-2,1,0,-22
那么最佳买入时间就是-3那个点，最佳抛出时间就是-3后面的那个4,应为4-(-3)=7 是最大滴

我晕，第二题你们怎么都想那么复杂啊。。。
不就是一个数组，比如0,2,-1,3,4,5,-3,1，4,-2,1,0,-22
那么最佳买入时间就是-3那个点，最佳抛出时间就是-3后面的那个4,应为4-(-3)=7 是最大滴
wwwyhx 发表于 2011-2-5 23:48

这个不叫数学归纳法把？

如果是google的题，肯定不会就递归这么简单，我想他们要的是快速算法，或者恒定内存之类。简单做递归那连课堂练习的水平都不如。