珍珠湾ART

标题: a Microsoft interview Question [打印本页]

作者: achen 时间: 2004-12-20 01:35
提示: 作者被禁止或删除内容自动屏蔽

作者: sunguobiao 时间: 2004-12-20 11:21
标题: 回复：a Microsoft interview Question

降序冒泡算法

作者: sean9991 时间: 2004-12-20 19:46
标题: 回复：a Microsoft interview Question

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 :-).

作者: achen 时间: 2004-12-21 03:04
提示: 作者被禁止或删除内容自动屏蔽

作者: sean9991 时间: 2004-12-21 20:08
标题: 回复：can u explain it?

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
标题: 回复：回复：a Microsoft interview Question

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
标题: Very interesting. I guess she is still single[:D)]

Very interesting. I guess she is still single

作者: IG 时间: 2004-12-23 00:38
标题: That part I don't know, but she's pretty.[;)]

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

欢迎光临珍珠湾ART (http://66.160.158.134/)