--- tags: AD --- # 111 陽明交大資訊工程學系(APCS組)面試 [TOC] ## 成績 :::danger 結果：備取 4 (X) (備到 3) ::: | 項目 | 學測($數\times1$)(20%) | 審查資料(35%) | 口試(45%) | 總分 | | --- | ---- | ------ | ---- | ----- | | 分數 | 66.7 | 88.63 | 93.67 | 86.51 | :::info 最低正取分數： 93.84 ::: ## 面試準備 就在自介挖洞給教授跳，然後針對每個問題先準備好答案。 那問題準備在這裡：[Link](/HJg4jduDq)。 ## 面試過程 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 有興趣而追問，然後有準備所以被問起來沒太大的問題，也成功轉移我不會的題目。 以上，希望一切順利。