Re: [請益] 請教一題面試題
※ 引述《CIDgreen (承)》之銘言：
: 換工作的季節到了 XD 於是想起來 當時在面試軟體公司的時候，寫的面試題目，
: 有一題很奇妙，而面試題目也不會拿到詳解，所以想問一下 這一題是什麼意思。
: 抱歉有幾年了，所以記憶有點衰退。
: 題目大意上是說，今天你坐一台電梯，每層樓都會停，
: 門打開的時候都會看到一顆寶石，每層樓的寶石的大小、重量、色澤都不一定，
: 但你只能選擇一顆寶石，而且選擇了以後就不能更換，電梯也不會回頭。
: 電梯從一樓到十二樓，請問你會拿哪一層樓的寶石？
: 或是問說 你會怎麼選擇？
: 想請問這個問題在問的東西到底是什麼？
: 而有正確答案嗎？
先假設N是你的選項數（這裡就是樓數N=12)
e=2.718... （euler's number)
假設存在一個function v(條件) = 價值
講白一點就是給寶石的參數可以得到一個 ”價值”
(1) 先觀測前 N/e 個，並記錄最佳值（假設max)
(2) 第N/e +1 個以後，如果看到比max大的就取他
不然就取最後一個
有人叫這個方法Gilbert & Mosteller law
基本上可以應用在很多類似的地方
證明請google: The Strategy of John Gilbert and Frederick Mosteller (G&M)
原理很簡單，基本上統計來說，你觀測的愈多，max估的愈準
但max估的愈準（卻沒取），你剩下的選擇愈小
所以是以期望值的角度來回答
這可以用來解決很多的問題，基本上就是只能觀測一次不能回頭
都可以用這個idea來解…
我覺得面試者不會期待你知道答案
但你應該要能分析我上面提到的原理
並提出一些”逼近”這個原理的”奇怪”演算法，然後實作它
例如提到 Monte Carlo method 一類的方法，諸如等等
基本上考你的機率統計底子，如果是應徵scientist的工作
這個題目不算不合理
但如果是software developer，那面試者應該要合理的引導你
畢竟重點是考coding…不是考你的統計就是了 :)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 67.49.85.83
※ 編輯: chucheng 來自: 67.49.85.83 (04/14 18:19)
→
04/14 20:24, , 1F
04/14 20:24, 1F
→
04/14 21:27, , 2F
04/14 21:27, 2F
推
04/14 23:57, , 3F
04/14 23:57, 3F
→
04/14 23:58, , 4F
04/14 23:58, 4F
→
04/14 23:59, , 5F
04/14 23:59, 5F
→
04/15 00:01, , 6F
04/15 00:01, 6F
推
04/15 00:26, , 7F
04/15 00:26, 7F
→
04/15 01:09, , 8F
04/15 01:09, 8F
推
04/15 02:42, , 9F
04/15 02:42, 9F
→
04/15 02:42, , 10F
04/15 02:42, 10F
→
04/15 02:43, , 11F
04/15 02:43, 11F
→
04/15 02:43, , 12F
04/15 02:43, 12F
→
04/15 04:11, , 13F
04/15 04:11, 13F
→
04/15 04:14, , 14F
04/15 04:14, 14F
→
04/15 04:15, , 15F
04/15 04:15, 15F
→
04/15 04:18, , 16F
04/15 04:18, 16F
推
04/15 09:10, , 17F
04/15 09:10, 17F
→
04/15 09:10, , 18F
04/15 09:10, 18F
討論串 (同標題文章)