看板Soft_Job
之前去面試了一間夢想已久的外商也碰到類似的變形考題
現在碰巧翻到這古文
考題如下:
1. 給定一 1~N 的正整數數字序列
2. 給定三個正整數 A, B, C 其中 A>B>C>0
3. 序列中能被A整除則顯示Adorable
4. 序列中能被B以及C整除則顯示CUTE
5. 序列中能被A,B,C同時整除顯示AdorableCUTE
6. 其餘顯示原本數字
* 效率越高越佳
我給的方式如下:
UINT n1,n2,n3;
UINT n1x,n2x,n3x;
.....
n1 = n2 = n3 = 0;
n1x = A; n2x = B; n3x = C;
for i=1; i<=n; ++i,already=0
if i-n1 == n1x
print "Adoriable"
already = 1; n1 = i;
if i-n2 == n2x and i-n3 == n3x
print "CUTE"
already = 1;
if i-n2 == n2x
n2 = i;
if i-n3 == n3x
n3 = i;
if !already
print i
跟面試官講解了我的邏輯概念後，面試官覺得我的邏輯正確。
但被要求給出數學證明就被考倒了(原諒我沒辦法用數學表示我的想法)。
幸好最後還是offer get.
: 看了andrei alexandrescu的Three Optimization Tips for C++
: 了解到這題的意思
: % (模數運算) 是很貴的
: 如何不用模數運算解掉這題?
: pattern就是每15一個循環
: 必定為 1 2 F 4 B F 7 8 F FB
: 寫個loop照上面輸出，一次處理15個數字
: 把尾數處理的漂亮就行了
: 另外resize是很貴的
: 回傳的vector<string>可以先reserve起來
: string本身因為不長，所以不會有malloc的動作
: to_string的效率不佳
: 追求最佳化可使用andrei提供的演算法
: 大guy4醬
--
※ 批踢踢實業坊(ptt.cc), 來自: 223.140.186.28※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1523816722.A.171.html
推 sean2449: FizzBuzz? 04/16 09:08
→ durantlin: YES, 類似的變形題 04/16 10:15
推 carlmonkey: 推一個！有點深度 學了一課！ 04/16 11:05
→ pttworld: 這題應該不需要迴圈 04/16 14:57
推 icecastleo: load hit store 04/17 02:02
推 pttnowash: 看不懂趕快推 04/17 10:36
→ pttnowash: if{not understand}, you{push} 04/17 10:37
推 becca945: Buzz! 04/18 09:02
推 silverwolf13: “能被B與C整除”應該再簡化成要嘛能被B*C整除，要 04/19 02:27
→ silverwolf13: 嘛C是B的因數所以整除B就好。上述都能在迴圈之前判 04/19 02:27
→ silverwolf13: 斷。 04/19 02:27
推 louis925: 不對吧? 12可以被4和6整除，但無法被4*6整除，4和6都互 04/26 02:26
→ louis925: 不為因數 04/26 02:26