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

作者: kimjay (kim)   2014-09-05 09:13:55
有一個問題想請教板上各位先進,
這是朋友的弟弟當完兵後,今年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都當掉,後來直接先打好先貼上了~
作者: b941152 ( )   2014-09-05 09:24:00
寫一個矩陣用做判別,當取過之後把該位置的數字歸零當再遇到歸零的數字之後再往下取 直到有非零的數字?
作者: theone777 (你想要什麼)   2014-09-05 09:25:00
淺見,mod,注意邊界
作者: b941152 ( )   2014-09-05 09:26:00
@@ 臨時想到的... 應該有高手可以幫忙
作者: kimjay (kim)   2014-09-05 09:32:00
mod取餘數~和發撲克牌程式一樣,但是他是有規則取出,並非亂數隨機,我一開始有想到,但發現有問題還是我哪裡做錯了嗎?
作者: a7904120 (pubear)   2014-09-05 10:50:00
hashtable collision?
作者: manlike ( )   2014-09-05 10:57:00
樓上這樣亂烙專有名詞不行噢~大概就用個queue存1~N, 然後開始選, 沒選到的就dequeue再enqueue, 然後一直選, 直到選完或者queue空了。queue可以用array做或是linked list, 用array可以發揮到極致, 就一直 mod 和 memecpy。*memcpy
作者: a7904120 (pubear)   2014-09-05 11:53:00
我覺得概念滿像的呀~~
作者: jojowolf (天使羽根)   2014-09-05 13:30:00
目前想到linked list可解,元素斷開鏈結也很方便
作者: steve422 (steve422)   2014-09-05 13:51:00
我用python寫好了
作者: saladim (殺拉頂)   2014-09-05 13:57:00
mod 有 cycle問題 要小心一點這個在需求那邊沒定義
作者: zenuo (堅持到底永不放棄)   2014-09-05 18:09:00
N可以被間隔整除時就會循環,此時當取到的數大於N時 餘數+1
作者: boss0405 (boss)   2014-09-05 18:38:00
用linked list寫個queue就可以了y
作者: buletris (◆愛發呆◇)   2014-09-05 19:00:00
小弟我會這樣寫~http://ppt.cc/PWIx表達就想像10個人排列分別又左至右別1號到10號的號碼牌隨機挑到第三位出列後, 順時針下一位接序報數1再下一位報2 每報到3就出列, 直到出列數達7人為止依序看出列順序看號碼牌即為排列順序補充報到3 下一位再從1開始報起
作者: kimiyuan (kimiko)   2014-09-05 21:06:00
這題算很簡單吧…他快把algorithm說完了照題目就能直接 coding
作者: sam9595 (帕帕)   2014-09-06 03:24:00
bule的解法並沒有想到間隔很大會跑得極慢的問題我不會說很簡單 有一堆細節沒有經驗的人是不會注意到的
作者: futureq (無名再見)   2014-09-06 09:11:00
去看演算法的書吧不過名字忘記了,囧。
作者: longlongint (華哥爾)   2014-09-06 22:12:00
約瑟夫問題直接解可用陣列 高速解用餘數可是要查一下資料OTZ

Links booklink

Contact Us: admin [ a t ] ucptt.com