[討論] 面試題 - 陣列輸出.矩陣乘法
小弟平時會 "挖" 一些面試題，< 有新的也有舊的 >
這個月有幾題覺得還不錯，< 其實重點是覺得自己解不好 >
讓人蠻感興趣，於此想與各位版友一起探討，也懇請不吝賜教。
提到一些演算法的東西, 但盡量附上 code 。
為留有思考空間，題目與小弟的想法分上下段分開寫。
也由於題目範圍會跳 tone 些，故若對於其中任意一題有想法，
請不吝提出，感激不盡。
Q1 假設一陣列 a[] = {4,15,21,17,6,1,99}，
如何輸出 1~100 ，而 a 陣列出現之數字即不輸出？
( 記憶體使用量盡可能少，程式執行速度盡可能快 )
Q2 假設已知二陣列 double a[p][q], b[q][r],
現欲求 double c[p][r] = a[p][q] * b[q][r]，
已知 500 < p, q, r < 1000 , 請試完成 c。
( as soon as possible. )
* Q3 就你所知，能否簡述 AutoRun.inf 病毒防護機制或原理？
或直接提示一想法去防護 ?
( 很抱歉這題我竟沒太多想法 )
－－－－－－－－－－－－－－－－－－－－－－－－－－
A1 : 這題小弟解法 : http://ppt.cc/rS@8
< 上面廢話跳過，拉到最下面看 code >
A2 : 最有得討論的大概是這題。
(1) 傳統 < 略 >
簡單的說是 rst[i][j] += a[i][k] * b[k][j] ;
0 < i < p ; 0 < j < r ; 0 < k < q
(2) 轉置
先將 b[q][r] 轉置成為 b'[r][q]
變成 rst[i][j] += a[i][k] * b[j][k]
0 < i < p ; 0 < j < r ; 0 < k < q
for(i=0; i<p; ++i){
for(j=0; j<r; ++j){
sum = 0.0;
for(k=0; k<q; ++k)
sum += a[i][k] * b[j][k];
rst[i][j] = sum;
}
}
測試出來 ( wall time testing ) 約比傳統快 6～7 倍
* (3) Div Block
這裡會用到 6 個 for-loop, 前面 3 個是限制 block, 後 3 個是計算 rst,
同時利用到 (2) 的技巧，也就是先將 b[q][r] 先轉置成 b'[r][q]，
實測跑出來下面這段 code 結果會出包 < 結果是錯的 >
不知是否我哪段有誤？
const size_t BLOCK = 64;
for(ci=0; ci< p; ci+=BLOCK)
for(cj=0; cj< r; cj+=BLOCK)
for(ck=0; ck< q; ck+=BLOCK)
for(i=ci; i<min(ci+BLOCK, p); ++i)
for(j=cj; j<min(cj+BLOCK, r); ++j) {
sum = 0.0;
for(k=ck; k<min(ck+BLOCK, q); ++k)
sum += a[i][k] * b[j][k];
rst[i][j] = sum;
}
小弟驗證答案是錯的，不知是否哪裡有誤？
< wall time 大概比上一個方法快 10%~20%, 不過取決於 Block Size>
完整測試碼 http://codepad.org/X81ymBjQ
* (4) Q
下面三個其他想法有問題, 苦找不到方向 ：
(a) Div Block , 有辦法推出較佳的 Block ”大概” 是多少嗎？
(b) 有種演算法叫 Strassen algorithm, 目前看的 code 都有一前提在
matrix 為 nxn , 且 n = 2^k ( k 為整數 )，
使用此演算法必定需符合此前提嗎 ?
< 另我較好奇的是，這種演算法使用分而治之，大多用遞迴手法完成，
如此下來是不是真的比 (3) 還快倒讓人蠻懷疑的 >
(c) " 目前 "， matrix multiple 是否可以 multi-thread 完成？
( 或說，multi-thread 對於 matrix multiple 是否有較佳設計模式？
目前我試是較慢的，所以想說應該是我沒設計好 )
我知道最快的方法躺在 I2A 裡面，不過實在沒興趣 K 它實作 Orz。
A3 :
這問題可能跳 tone 許多，也是一個 open problem，
縮小範圍，下面就當笑話看看吧..
(1) 我知道一些單位，電腦裡面會放一支 serv,
當 usb 插入後會讀到 pid , 於是在 Win32 API 抓到
WM_DEVICE_CHANGE 時去確認 pid, 不是符合的就自動斷掉
但不知道病毒的動作會不會比這個還快，
不過這並不能算是「防毒軟體」Orz
(2) 另一種方式大概只能做 trace API,
但難度在於監看 process API 之調用,
如何監控哪些 process 用到了
FindWindow、SendMessage、Read/WriteProcessMemory... etc，
這點卻完全摸不著頭緒。
若真有辦法控監的話，誤判機率應該蠻大的，
目前能想到的修正大概是：
CreateProcess -> ReadProcessMemroy -> WriteProcessMemory,
要判斷是否為「某一系列 API 之連續調用」，再判斷是否為病毒。
< 所以應該會用到 FSM >
－－－－－－－－－－－－－－－－－－－－－－－－－－
以上，請各位版友不吝解惑與賜教，小弟感激不盡！
--
「自從我學了 C# , 人都變聰明 , 考試都考一百分」
「自從我學了 VB , 皮膚都變好 , 人也變漂亮了 」
「自從我學了 Java , 明顯變壯 , 個子也變高了 」
「自從我學了 C++ , 內分泌失調 , 頭都禿了... 」
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.76.161
推
05/26 22:04, , 1F
05/26 22:04, 1F
推
05/26 22:05, , 2F
05/26 22:05, 2F
→
05/26 22:05, , 3F
05/26 22:05, 3F
→
05/26 22:06, , 4F
05/26 22:06, 4F
→
05/26 22:07, , 5F
05/26 22:07, 5F
→
05/26 22:08, , 6F
05/26 22:08, 6F
→
05/26 22:09, , 7F
05/26 22:09, 7F
→
05/26 22:09, , 8F
05/26 22:09, 8F
→
05/26 22:10, , 9F
05/26 22:10, 9F
→
05/26 22:10, , 10F
05/26 22:10, 10F
→
05/26 22:11, , 11F
05/26 22:11, 11F
→
05/26 22:11, , 12F
05/26 22:11, 12F
推
05/26 22:12, , 13F
05/26 22:12, 13F
→
05/26 22:12, , 14F
05/26 22:12, 14F
→
05/26 22:14, , 15F
05/26 22:14, 15F
→
05/26 22:15, , 16F
05/26 22:15, 16F
→
05/26 22:16, , 17F
05/26 22:16, 17F
→
05/26 23:29, , 18F
05/26 23:29, 18F
→
05/26 23:35, , 19F
05/26 23:35, 19F
→
05/27 05:53, , 20F
05/27 05:53, 20F
→
05/27 05:54, , 21F
05/27 05:54, 21F
→
05/27 07:12, , 22F
05/27 07:12, 22F
→
05/27 07:12, , 23F
05/27 07:12, 23F
A2.3 也解出來了, 效能似乎與轉置沒太大差異。
※ 編輯: EdisonX 來自: 180.177.76.161 (05/27 09:34)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
