之前去面試了一間夢想已久的外商也碰到類似的變形考題
現在碰巧翻到這古文
考題如下:
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.
※ 引述《Domos (沒事發發廢文)》之銘言：
: 看了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醬