交大資工 特殊選才心得

特選之旅還在進行中，如果想看其他間的面試心得還有結果，可以查閱特選心得彙整

前言

交大今年是最晚的，總共十個名額，較去年增加三個，算是增加三個比較彈性的資安名額，基本上就是大魔王，特別緊張

面試進行

進行方式

三位教授，坐在他們前面（有一段距離）

自我介紹

只有一分鐘，反而講得很卡

問答時間

• 請舉出一個比較熟悉的演算法
  • 我：其實學過的都差不多，比較喜歡的是矩陣快速冪
• 可以講解一下嗎？
  • 如果我們今天有一個線性遞迴的 DP 轉移式，那麼就可以推出一個轉移矩陣，並利用快速冪在 $\mathcal{O}(n\log n)$ 的時間算出來
• 可以講一下上禮拜的比賽嗎？
  • 全國賽的部分嗎？我覺得題目還蠻有趣的，可惜有兩題沒有把握好，一題是 $\mathcal{O}(n\log n)$ 被卡常，一題計算錯誤，原本能拿到三等獎，有點可惜
  • 教授：所以是連佳作都沒有嗎？
  • 我：對，因為光是卡常就少了 5、60 分了
• 矩陣快速冪在實務上的難點在哪裡？（其實我沒有聽清楚是難點還是運作上的瓶頸）
  • 主要是矩陣乘法的複雜度是 $n^3$，這會造成在矩陣本身比較大的時候，光是乘法的部分就會爛掉，像是之前寫過一題有 $C^6_2$ 的狀態數（其實是 $6^2$，優化後才會變 $C^6_2$ QQ），這樣光是在做乘法的時候就會爆掉，所以這部分算是比較有瓶頸的地方
• 知道矩陣快速冪可以用在圖論上嗎？
  • 有聽說過 😅
  • 教授：可以描述一下嗎？
  • 我：因為只有聽說過，所以不太了解😅
  • 教授：矩陣快速冪可以用在圖論上
  • 我：哦哦，是利用存圖的矩陣去做運算
  • 教授：對
  • 我：哦哦那大概知道
• 知道可以用矩陣快速冪推一般式嗎？像是費式數列
  • 這個不太知道😅
  • 教授：沒關係，這個你上大學就會學到了
  • 我：豪
• 除了競程以外，有研究其他東西嗎？
  • 資安跟開發都有碰一點點，資安的部分有參加過 T 貓盃，開發的部分主要有寫過兩個小專案，一個是 Discord Bot，裡面有一些專為競程選手打造的功能，像是比賽通知跟題目池的推薦，另一個則是 YTP 的專題，收集了各大 OJ 的題目，結合一些 Todolist 的功能
  • 教授：講一下題目池那個怎麼做的
  • 我：他有兩種模式，一種模式是利用使用者綁定的 Codeforces 帳號，設定一個難度區間，並且從這個區間中篩選出 AC 數較多的幾題出來
  • 教授：那另外一個，跟 vjudge 的有什麼不一樣
  • 我：我們的主要會有一個 todolist 的功能，可以像是 OI Checklist 一樣，標記一個題目的狀態。另外，我們會開發筆記以及白板的功能，使用者可以在平台上利用 markdown 甚至是白板，紀錄解題的過程，甚至是將這些東西分享出去，變相地變成一個題解平台，也可以彙整這些學習資源
• 這時候外面敲門了
  • 中間的教授：那你的在校成績怎麼樣
  • 我：因為我們班的目標是指考，進度比較快…..（講不完）
  • 教授：看來是答不出來
  • 😅
• 我下去 QQ

心得

果然是大魔王，整體氣場很強大，問題也都很硬。

競賽成績不夠強跟在校沒顧真的是硬傷，大概是凶多吉少。