作者kimjay (kim)
看板Tech_Job
标题[请益] 外商面试时的一道程式考题
时间Fri Sep 5 09:13:55 2014
有一个问题想请教板上各位先进，
这是朋友的弟弟当完兵後，今年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://webptt.com/cn.aspx?n=bbs/Tech_Job/M.1409879638.A.560.html
1F：→ b941152: 写一个矩阵用做判别，当取过之後把该位置的数字归零 09/05 09:24
2F：→ b941152: 当再遇到归零的数字之後再往下取 直到有非零的数字? 09/05 09:25
3F：推 theone777: 浅见，mod，注意边界 09/05 09:25
4F：→ b941152: @@ 临时想到的... 应该有高手可以帮忙 09/05 09:26
5F：→ kimjay: mod取余数～和发扑克牌程式一样，但是他是有规则取出， 09/05 09:32
6F：→ kimjay: 并非乱数随机，我一开始有想到，但发现有问题 09/05 09:33
7F：→ kimjay: 还是我哪里做错了吗？ 09/05 09:33
※ 编辑: kimjay (210.241.35.186), 09/05/2014 09:39:17
8F：→ a7904120: hashtable collision? 09/05 10:50
9F：→ manlike: 楼上这样乱烙专有名词不行噢~ 09/05 10:57
10F：→ manlike: 大概就用个queue存1~N, 然後开始选, 没选到的就dequeue再 09/05 11:49
11F：→ manlike: enqueue, 然後一直选, 直到选完或者queue空了。 09/05 11:49
12F：→ manlike: queue可以用array做或是linked list, 用array可以发挥到 09/05 11:51
13F：→ manlike: 极致, 就一直 mod 和 memecpy。 09/05 11:52
14F：→ manlike: *memcpy 09/05 11:53
15F：→ a7904120: 我觉得概念满像的呀~~ 09/05 11:53
16F：推 jojowolf: 目前想到linked list可解，元素断开链结也很方便 09/05 13:30
17F：推 steve422: 我用python写好了 09/05 13:51
18F：→ saladim: mod 有 cycle问题 要小心一点 09/05 13:57
19F：→ saladim: 这个在需求那边没定义 09/05 13:57
用Link list串列的方式，大致上能了解，另有人说使用mod的方式，会有其循环的问题
这部份是要如何去解决？我目前不太能够理解是使用怎样的演算步骤
另想请教像这种东西，如外商公司面试官所说的，要向一个不懂程式的人
去举例解说这个取号规则，是有什麽样子的好例子能够解释听得懂的吗？
※ 编辑: kimjay (210.241.35.186), 09/05/2014 14:36:07
20F：→ saladim: 例子一就是会产生循环(9的下一个) 题目只说不会取出已取 09/05 17:40
21F：→ saladim: 出的 可是没说遇到时怎麽处理 不过看来是取下一个 09/05 17:40
22F：推 zenuo: N可以被间隔整除时就会循环，此时当取到的数大於N时 余数+1 09/05 18:09
23F：推 boss0405: 用linked list写个queue就可以了y 09/05 18:38
25F：→ buletris: 表达就想像10个人排列分别又左至右别1号到10号的号码牌 09/05 19:02
26F：→ buletris: 随机挑到第三位出列後, 顺时针下一位接序报数1 09/05 19:03
27F：→ buletris: 再下一位报2 每报到3就出列, 直到出列数达7人为止 09/05 19:04
28F：→ buletris: 依序看出列顺序看号码牌即为排列顺序 09/05 19:05
29F：→ buletris: 补充报到3 下一位再从1开始报起 09/05 19:06
30F：推 kimiyuan: 这题算很简单吧…他快把algorithm说完了 09/05 21:06
31F：→ kimiyuan: 照题目就能直接 coding 09/05 21:07
32F：推 sam9595: bule的解法并没有想到间隔很大会跑得极慢的问题 09/06 03:24
33F：→ sam9595: 我不会说很简单 有一堆细节没有经验的人是不会注意到的 09/06 03:24
34F：→ futureq: 去看演算法的书吧 09/06 09:11
35F：→ futureq: 不过名字忘记了，囧。 09/06 09:12
36F：推 longlongint: 约瑟夫问题 09/06 22:12
37F：推 longlongint: 直接解可用阵列 高速解用余数可是要查一下资料OTZ 09/06 22:14