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

[starcraftiii (星海爭霸三)]

因為我面試和演算法有關的工作

有一題是這樣的

請用複雜度 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
推 meowyih: 利用hash，做出n個只裝了1個數字的hash entry
推 DontGoCMI: 又沒限制多隨機 亂搞都是答案 爛題目
題目中已經有先,不考慮隨機數的內部機制了
→ meowyih: 舉例來說，最簡單的hash就是餘數的%，每次將產生出來的數
→ meowyih: 字%n，把已經產生過的相同餘數的刪掉就是了 XD
→ DontGoCMI: 幾位數也沒講 我拿系統時間也行那
推 gensim: http://www.cnblogs.com/lavezhang/archive/2012/05/14/24
→ gensim: 98981.html
我有想到用hashtable,而且跟你網頁中的第三種做法幾乎一模一樣
重點就是,我每次隨機出來的是數的編號,而不是值
※ 編輯: starcraftiii (220.133.16.27), 10/08/2015 20:17:49
→ supertitler: 直接從籃子拿
→ meowyih: 不過說真的，這題離 "有趣" 還挺遠的，我從沒做過這題，
→ meowyih: 也只花了十秒就有想法了，好像不是什麼需要想很久的題目
→ starcraftiii: 抱歉@@"~我是真的想蠻久的
噓 simonwang661: 台灣公司當自己外商 ..
推 chubiei: 這是問random_shuffle吧
→ carlcarl: 還滿常見的題目
推 noah538: 這題用硬體觀念做很簡單說
→ noah538: 觀念直接用套上卵體就解了
噓 Keelungman: 隨便生個隨機數列{n_i}，然後輸出n_1,n_1+n_2,...