111 陽明交大資訊工程學系(APCS組)面試

• 111 陽明交大資訊工程學系(APCS組)面試
  • 成績
  • 面試準備
  • 面試過程
  • 心得

成績

結果：備取 4 (X) (備到 3)

項目	學測( $\mathrm{數}\times 1$)(20%)	審查資料(35%)	口試(45%)	總分
分數	66.7	88.63	93.67	86.51

最低正取分數： 93.84

面試準備

就在自介挖洞給教授跳，然後針對每個問題先準備好答案。
那問題準備在這裡：Link。

面試過程

1 分鐘自我介紹+6 分鐘問答。

Q. 請開始 1 分鐘的自我介紹。

A. （自我介紹）。

（最右邊教授，卡車教授）
Q. 欸剛剛那位是你的同學嗎？

A. 對。

Q. 那你在擔任幹部時主要教學的內容是什麼？

A. 以資料結構當中的線段樹為主。它最基本的是解決序列問題，對於區間答案有結合性的可以使用。進階一點的話，延遲標記可以用於區間問題，降低時間或空間複雜度，動態開點可以降低空間複雜度，避免記憶體爆掉，另外線段樹也可以搭配其他演算法一起使用，比如掃描線。以上。

Q. 那給你一個序列，線段樹儲存區間和，求連續區間和大於等於

$k$ 的位置在哪？

A. 這可以用線段樹上二分搜的演算法，對於線段樹節點而言，我可以知道左區間的區間和，那

$k$ 如果大於（應該是大於等於才對）左區間和，那就往右遞迴，參數為

$k$ 減掉左區間和，如果沒有的話就繼續往左遞迴，類推遞迴下去，就可找到區間和大於等於

$k$ 的那個位置。

Q. 那這樣複雜度多少？

A. 如果序列長度是

$N$ 的話，那時間複雜度是

$O(\log N)$。

Q. 那為什麼這樣和直接二分搜比呢？
（我不知道教授是想聽到前綴和+二分搜的

$O(\log N)$，還是二分搜index+線段樹查詢的

$O({\log }^{2}N)$，教授也可能想聽的是線段樹可以帶修改⋯）

A. 直接二分搜是找到位置花

$O(\log N)$，線段樹查詢時

$O(\log N)$，所以複雜度是

$O({\log }^{2}N)$，但線段樹上二分搜就直接遞迴查詢，

$O(\log N)$ 即可。

Q. 你可以再明確一點說你的做法嗎？

A. （再說一次作法）。

Q. 那你有沒有做過更高維度的查詢，比如區域查詢的問題？

A. 有。讓我印象最深刻的是 IOI 有一題是區域查詢 gcd，就是最大公因數，它是利用線段樹套樹的方式解題，另外因為範圍是

${10}^9$，還要搭配延遲標記，如果該區間只有一個數就不要遞迴建構，降低空間使用。

（最左邊教授）
Q. 那在最近 AI 很熱門，我在你的資料中看到手寫辨識、MNIST，你可以簡單說明一下嗎？

（因為我忘記那啥了，所以轉移問題回答去迴避，然後順便講未來發展）
A. 呃，我在在大學部分的規劃有兩個，一是競賽程式設計演算法，二是人工智慧。我在最近也有關注 AI 的發展，比如聯發科和 Google 發布的論文，是用 AI 做晶片設計，大幅縮短晶片設計的時間，我在未來想往這方向做研究。

Q. 那你對這篇 paper 應該有一定的了解，可以說明一下嗎？

A. 它是用晶片放置的位置，然後藉由鄰近位置調整參數，經由累積獎勵最大化的方式，訓練 AI。

（中間教授）
Q. 我在你的審查資料中看到 Discord bot，可以介紹一下嗎？

A. 在我設計的功能中，最大的是利用網路爬蟲可以快速爬去 Zerojudge 的解題資料⋯

Q. 不好意思，時間到了。

A. （起身鞠躬）謝謝教授。

心得

因為不像清大有簡報，比較容易準備和被提問。交大的不確定性很高，所以有額外準備可能被問的問題。

面試前看到助理(?)是韋詠祥欸，然後就發揮強大的社交能力去認識朋友 <(_ _)>，我跟他講超多的，給我自信，也讓我冷靜下來去面對面試，人真的很熱情 (。・∀・)ノ。

面試時會根據自我介紹而引導接下來的問題，那很幸運的是我引導到的是線段樹，是我最熟悉的東西，所以被問的時候算是得心應手，沒有被問爆，Ian Shih 被問到均攤分析 \|/。其它部分像是 MNIST 的那個迴避，有讓教授對那篇 paper 有興趣而追問，然後有準備所以被問起來沒太大的問題，也成功轉移我不會的題目。

以上，希望一切順利。