[討論] 最近面試遇到一個有趣的程式題

看板Tech_Job作者 (星海爭霸三)時間8年前 (2015/10/08 19:44), 8年前編輯推噓3(5推 2噓 10→)
留言17則, 10人參與, 最新討論串1/1
因為我面試和演算法有關的工作 有一題是這樣的 請用複雜度 O(n)以下 解連續做出n個不重覆隨機數 先不考慮隨機數本身內的機制的話 請問要怎麼做才能讓複雜度在O(n)以下 -- XBox One Titanfall Asian East http://www.twitch.tv/starcraftiii -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.133.16.27 ※ 文章網址: https://www.ptt.cc/bbs/Tech_Job/M.1444304685.A.E53.html
推
10/08 20:03, , 1F
利用hash，做出n個只裝了1個數字的hash entry
10/08 20:03, 1F
推
10/08 20:03, , 2F
又沒限制多隨機 亂搞都是答案 爛題目
10/08 20:03, 2F
題目中已經有先,不考慮隨機數的內部機制了
→
10/08 20:04, , 3F
舉例來說，最簡單的hash就是餘數的%，每次將產生出來的數
10/08 20:04, 3F
→
10/08 20:04, , 4F
字%n，把已經產生過的相同餘數的刪掉就是了 XD
10/08 20:04, 4F
→
10/08 20:06, , 5F
幾位數也沒講 我拿系統時間也行那
10/08 20:06, 5F
→
10/08 20:08, , 7F
98981.html
10/08 20:08, 7F
我有想到用hashtable,而且跟你網頁中的第三種做法幾乎一模一樣 重點就是,我每次隨機出來的是數的編號,而不是值 ※ 編輯: starcraftiii (220.133.16.27), 10/08/2015 20:17:49
→
10/08 21:16, , 8F
直接從籃子拿
10/08 21:16, 8F
→
10/08 21:28, , 9F
不過說真的，這題離 "有趣" 還挺遠的，我從沒做過這題，
10/08 21:28, 9F
→
10/08 21:29, , 10F
也只花了十秒就有想法了，好像不是什麼需要想很久的題目
10/08 21:29, 10F
→
10/08 21:36, , 11F
抱歉@@"~我是真的想蠻久的
10/08 21:36, 11F
噓
10/08 22:24, , 12F
台灣公司當自己外商 ..
10/08 22:24, 12F
推
10/09 00:42, , 13F
這是問random_shuffle吧
10/09 00:42, 13F
→
10/09 03:00, , 14F
還滿常見的題目
10/09 03:00, 14F
推
10/09 10:17, , 15F
這題用硬體觀念做很簡單說
10/09 10:17, 15F
→
10/09 10:18, , 16F
觀念直接用套上卵體就解了
10/09 10:18, 16F
噓
10/09 16:31, , 17F
隨便生個隨機數列{n_i}，然後輸出n_1,n_1+n_2,...
10/09 16:31, 17F
‣ 更多 starcraftiii 的文章
文章代碼(AID): #1M5bSjvJ (Tech_Job)