[請益] 外商面試時的一道程式考題(求解）

看板Tech_Job作者 (kim)時間9年前 (2014/09/05 09:13), 9年前編輯推噓10(10推 0噓 27→)
留言37則, 15人參與, 最新討論串1/1
有一個問題想請教板上各位先進， 這是朋友的弟弟當完兵後，今年6月去應徵外商一個做應用程式開發的部門， 朋友弟弟在面試時，遇到的其中一個題目 （剛好聊到，我想嘗試自己解解看，可是寫了好幾次都解不出來） 因為並沒有指定特定語言，我又想知道這題該如何解？所以不知道PO在科技版合不合適？ 聽他說主要是考面試者的基本程式設計和邏輯，以及表達能力 題目內容大概照他說的大概描述如下 －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 1.(考基本程式設計和邏輯) 假設有N個人排隊來領號碼牌，領的號碼牌是1-N號，接下來要從N個人挑7個人入選 （也就是說排隊的人只是先取得資格，中選的人是另由程式挑選） 排序規則如下，請依題目撰寫程式（使用程式語言不限）。 從N個號碼挑選一個起始號碼，以及一個間隔號碼，共取7個人，超過N則從頭開始算起 已被取出的號碼就不會在數列中（註：非隨機取亂數） 2.(考表達能力) 根據題目描述部份，如果今天您要向客戶主管說明這個取號遊戲規則，您要如何向客戶主管舉例說明 （把客戶主管當做不會程式的笨蛋，但要使其瞭解） －－－－－－－－－－－－－－－－－－－－－－－－－－－ 1. 假設N=9，起始號碼=3，間隔碼號=3，挑選人數=7 那麼取出的號碼順序如下： 3、6、9、4、8、5、2 2. 假設N=10，起始號碼=3，間隔碼號=3，挑選人數=7 那麼取出的號碼順序如下： 3、6、9、2、7、1、8 3. 假設N=11，起始號碼=3，間隔碼號=3，挑選人數=7 那麼取出的號碼順序如下： 3、6、9、1、5、10、4 －－－－－－－－－－－－－－－－－－－－－－－－ 以上，就是程式寫完後應得出的結果，也就是在已知N的狀況下， 不管其他起始號碼、間隔碼號、挑選人數這些變數如何變動 是有規則的取出順序號碼，想請問此題的解題技巧在哪裡？ 知道其概念，但程式解不出來＝　＝｜｜ 打了好幾次，pietty都當掉，後來直接先打好先貼上了～ -- " 生命，只有一回！ 夢想，不會只有一次！ 錯過的愛情，只要肯回頭，還是有找回心靈相印的一天……" -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.241.35.186 ※ 文章網址: http://www.ptt.cc/bbs/Tech_Job/M.1409879638.A.560.html
→
09/05 09:24, , 1F
寫一個矩陣用做判別，當取過之後把該位置的數字歸零
09/05 09:24, 1F
→
09/05 09:25, , 2F
當再遇到歸零的數字之後再往下取 直到有非零的數字?
09/05 09:25, 2F
推
09/05 09:25, , 3F
淺見，mod，注意邊界
09/05 09:25, 3F
→
09/05 09:26, , 4F
@@ 臨時想到的... 應該有高手可以幫忙
09/05 09:26, 4F
→
09/05 09:32, , 5F
mod取餘數～和發撲克牌程式一樣，但是他是有規則取出，
09/05 09:32, 5F
→
09/05 09:33, , 6F
並非亂數隨機，我一開始有想到，但發現有問題
09/05 09:33, 6F
→
09/05 09:33, , 7F
還是我哪裡做錯了嗎？
09/05 09:33, 7F
※ 編輯: kimjay (210.241.35.186), 09/05/2014 09:39:17
→
09/05 10:50, , 8F
hashtable collision?
09/05 10:50, 8F
→
09/05 10:57, , 9F
樓上這樣亂烙專有名詞不行噢~
09/05 10:57, 9F
→
09/05 11:49, , 10F
大概就用個queue存1~N, 然後開始選, 沒選到的就dequeue再
09/05 11:49, 10F
→
09/05 11:49, , 11F
enqueue, 然後一直選, 直到選完或者queue空了。
09/05 11:49, 11F
→
09/05 11:51, , 12F
queue可以用array做或是linked list, 用array可以發揮到
09/05 11:51, 12F
→
09/05 11:52, , 13F
極致, 就一直 mod 和 memecpy。
09/05 11:52, 13F
→
09/05 11:53, , 14F
*memcpy
09/05 11:53, 14F
→
09/05 11:53, , 15F
我覺得概念滿像的呀~~
09/05 11:53, 15F
推
09/05 13:30, , 16F
目前想到linked list可解，元素斷開鏈結也很方便
09/05 13:30, 16F
推
09/05 13:51, , 17F
我用python寫好了
09/05 13:51, 17F
→
09/05 13:57, , 18F
mod 有 cycle問題 要小心一點
09/05 13:57, 18F
→
09/05 13:57, , 19F
這個在需求那邊沒定義
09/05 13:57, 19F
用Link list串列的方式，大致上能瞭解，另有人說使用mod的方式，會有其循環的問題 這部份是要如何去解決？我目前不太能夠理解是使用怎樣的演算步驟 另想請教像這種東西，如外商公司面試官所說的，要向一個不懂程式的人 去舉例解說這個取號規則，是有什麼樣子的好例子能夠解釋聽得懂的嗎？ ※ 編輯: kimjay (210.241.35.186), 09/05/2014 14:36:07
→
09/05 17:40, , 20F
例子一就是會產生循環(9的下一個) 題目只說不會取出已取
09/05 17:40, 20F
→
09/05 17:40, , 21F
出的 可是沒說遇到時怎麼處理 不過看來是取下一個
09/05 17:40, 21F
推
09/05 18:09, , 22F
N可以被間隔整除時就會循環，此時當取到的數大於N時 餘數+1
09/05 18:09, 22F
推
09/05 18:38, , 23F
用linked list寫個queue就可以了y
09/05 18:38, 23F
推
09/05 19:00, , 24F
小弟我會這樣寫~http://ppt.cc/PWIx
09/05 19:00, 24F
→
09/05 19:02, , 25F
表達就想像10個人排列分別又左至右別1號到10號的號碼牌
09/05 19:02, 25F
→
09/05 19:03, , 26F
隨機挑到第三位出列後, 順時針下一位接序報數1
09/05 19:03, 26F
→
09/05 19:04, , 27F
再下一位報2 每報到3就出列, 直到出列數達7人為止
09/05 19:04, 27F
→
09/05 19:05, , 28F
依序看出列順序看號碼牌即為排列順序
09/05 19:05, 28F
→
09/05 19:06, , 29F
補充報到3 下一位再從1開始報起
09/05 19:06, 29F
推
09/05 21:06, , 30F
這題算很簡單吧…他快把algorithm說完了
09/05 21:06, 30F
→
09/05 21:07, , 31F
照題目就能直接 coding
09/05 21:07, 31F
推
09/06 03:24, , 32F
bule的解法並沒有想到間隔很大會跑得極慢的問題
09/06 03:24, 32F
→
09/06 03:24, , 33F
我不會說很簡單 有一堆細節沒有經驗的人是不會注意到的
09/06 03:24, 33F
→
09/06 09:11, , 34F
去看演算法的書吧
09/06 09:11, 34F
→
09/06 09:12, , 35F
不過名字忘記了，囧。
09/06 09:12, 35F
推
09/06 22:12, , 36F
約瑟夫問題
09/06 22:12, 36F
推
09/06 22:14, , 37F
直接解可用陣列 高速解用餘數可是要查一下資料OTZ
09/06 22:14, 37F
‣ 更多 kimjay 的文章
文章代碼(AID): #1K2GvMLW (Tech_Job)