a Microsoft interview Question

只看该作者 · 发表于 2004-12-20 01:35:26

提示: 作者被禁止或删除内容自动屏蔽

sunguobiao · 发表于 2004-12-20 11:21:03

降序冒泡算法

sean9991 · 发表于 2004-12-20 19:46:03

There is no guaranteed way to get the biggest diamond. All we can do is to miximize the probability of getting it. The overall strategy is to stopped and get the diamond which is the biggest so far. For example, we stopped at the nth floor and observed that the diamond on that floor was the biggest so far (from floor 1 to floor n), then we simply took it and left the building. A stochastic dynamic programming formulation will help us to determine the optimal strategy (the best stopping point), which in this case, is to skip (but check their sizes) the first 37% percent (or first 4 floors), then pick the one which is the biggest among the all the checked diamonds.

BTW, you can apply this method in dating girls/boys :-).

只看该作者 · 发表于 2004-12-21 03:04:35

提示: 作者被禁止或删除内容自动屏蔽

sean9991 · 发表于 2004-12-21 20:08:32

this is a sorting algorithm when you want to sort a list of elements in ascending or descending order. it's not efficient in computational complexity. it's not for this question either.

IG · 发表于 2004-12-21 20:25:07

I came across a similar problem before, the answer was after went through n floors (n=1/e * total number of floors), then take the first one that's bigger than those you have seen so far in the following floors.

In fact an Austrian mathematician (a woman) have applied this to dating and marriage. She claims that you should experience 12(?, I'm not 100% sure) lovers before commit youself to the next best. so she assumed the total number of lovers you would experience in your life is = 12*e = 33, which I think is quite a big number for average Chinese,... I see some cultural different here.

ob · 发表于 2004-12-22 10:18:09

Very interesting. I guess she is still single

IG · 发表于 2004-12-23 00:38:17

That part I don't know, but she's pretty.

		自动登录	找回密码
密码			立即注册

achen 该用户已被删除	电梯直达楼主发表于 2004-12-20 01:35:26 \| 只看该作者 \|倒序浏览 \|阅读模式提示: 作者被禁止或删除内容自动屏蔽
achen 该用户已被删除	收藏0 分享支持0 反对0
	回复使用道具举报置顶卡千斤顶

achen 该用户已被删除	地板楼主\| 发表于 2004-12-21 03:04:35 \| 只看该作者提示: 作者被禁止或删除内容自动屏蔽
achen 该用户已被删除
	回复支持反对使用道具举报

动态微博

a Microsoft interview Question

回复：a Microsoft interview Question

回复：a Microsoft interview Question

回复：can u explain it?

回复：回复：a Microsoft interview Question

Very interesting. I guess she is still single[:D)]

That part I don't know, but she's pretty.[;)]