--- tags: AD --- # 111 清華大學資訊工學學系(APCS組)面試 [TOC] ## 成績 :::success 結果：備取 1 (O) (備到 1) ::: | 項目 | 學測($英\times1+數\times1+自\times1$)(20%) | 審查資料(40%) | 口試(40%) | 總分 | | --- | ---- | ------ | ---- | ----- | | 分數 | 80.00 | 93.75 | 97.75 | 92.60 | :::info 最低正取分數： 93.23 ::: ## 面試準備 我是前一天才寫完講稿，總之就很卡又問題一堆，被一堆人點出問題後，晚上還重新寫過講稿，感謝方女神幫忙欸，不然真的會來不及。 ## 面試過程 ### 第一間 5 分鐘的自我介紹(投影片輔助)+5 分鐘的問題。 #### 自我介紹 大致上依照準備的節奏。 #### 問答 Q. 人工智慧的領域這麼廣，你想往哪個方向發展？ A. 在我剛剛的陳述中，有提到 google 和聯發科發表的論文，是有關於AI做晶片設計的方面，它是運用一些動作和累積獎勵的方式來訓練AI，來達到最大化的效益，而我正是對此有興趣，於暑假會研習相關論文。 Q. 研究論文是以現階段來說比較難的事情，那你該怎麼做？ A. 重新解讀消化吸收論文，另外我姑丈是在聯發科工作的，我在暑假期間，也會主動找他詢問這方面相關的問題。 Q. 喔有內線的（資源）⋯就對了。 Q. 那看到你在簡報說程設班八年傳承，請問是什麼意思？ A. 在我之前有經營了八年，而我是第九屆幹部，規模也從原本的十幾個人至今已有近百人，從一開始只有簡單的課程，而至今已有完善的規劃。 Q. 你說你在高中主要是打演算法競賽，那遇到不會寫的題目怎麼辦？ A. 我會先重新閱讀題目，題目可能會引導錯誤的方向，因此我會重新閱讀題目重新思考。還是不會的話我會上網搜尋網路上的資源，消化吸收重新理解並重新思考題目。還是不會的話會請問學長姐該題如何分析和下手。所以我遇到不會的問題時，我會重新思考、上網查詢、求助學長姐。 Q. 欸剛剛上一位也是你的競賽隊友，那請問在團隊你們是怎麼分工的？ A. 我在團隊負責的主要是資料結構和實作題⋯（計時器響起）。 Q. 謝謝黃同學。 A. 謝謝教授。 ### 第二間 10分鐘專業題目講解。 桌上有三列白色信封可以抽，沒有標示簡單/中等/困難。 #### 題目 | 3 | 9 | 15 | 4 | 2 | | - | - | - | - | - | 給一個序列，$A$、$B$ 輪流拿取，每次的拿取過程中，先找到序列中最大的數，拿取該數以及該數左右 $k$ 個，然後輪流拿取，直到陣列拿完為止。假設$k=1$，那 $A$ 就拿取 $9,15,4$，換 $B$ 時就拿取 $3,2$，邊界沒有就忽略。最後序列為空時，$A$ 拿到了$9,15,4$，$B$ 拿到了 $3,2$。 > 題尾還有一句話，但我忘了，可能是問題目要幹嘛，也可能根本不重要，大致上就是要模擬這個過程。 #### 答題狀況 我讀了一下題目，還在想最佳解時，教授說直接從簡單的解法開始，問了一下教授可不可以用白板輔助，他說可以，白板筆在旁邊。 我先講了暴力搜尋的解法。 教授詢問：「那假如這個序列的長度是 $N$，請問這樣的複雜度是多少？」 我想了一下，回答：「$O(N^2)$」。 教授說：「不算錯，但詳細一點的說是 $O(N^2/k)$。那請問有沒有辦法優化？」 我想了一下，說：「我目前想到了一個根號算法，就是每 $k$ 個一塊，紀錄該塊的最大值和還剩餘幾個沒有被選取，這樣可以以 $k$ 個為單位，根據算幾不等式可以得到 $O(N\sqrt{N})$。」 教授說：「你這樣⋯（中間我忘了）⋯沒有辦法說服我這是一個可行的方法，請再想想看，有沒有辦法再優化。」 我又想了一下，說：「我想到了可以用 treap 維護序列，存取最大值，然後每次找到該數後，往左往右各 $k$ 個的區段切出來，再將兩邊的treap合併，可以做出複雜度 $O(N\log N)$ 的解。」 教授說：「那請問這樣的複雜度是 best case、average case、worst case 還是 expected case？我說平均複雜度（但應該是期望）是 $O(N\log N)$，但 treap 有很低可能出現 $O(N^2)$⋯（計時器響起）。 教授說：「非常好，有空可以再來玩。」 我說：「謝謝教授。」 教授說：「可能會有 worst case，回去可以再想想這一題。」 我說：「好，謝謝教授。」 ## 心得 簡報很重要，是呈現你個人特質的主要來源，還有敢寫的話，就要對自己寫的東西有一定的了解，而一問三不知。 在第一間的問答中，感覺沒啥東西好被提問的，還有被說到前一位是我的隊友，可能就覺得我好弱。回答上就中規中矩，沒有被問爆，但也沒有回答得特別好，明確一點來說就是不夠特色吧。 在第二間的問答中，我覺得狀況還不錯，我其實想到什麼就講什麼，但沒有實際確認過可不可行，反正教授主要是聽你對解題的想法，我也盡力在有限的時間內想到什麼就講什麼，應該是有回答到教授想要的東西。 另外，兩間的教授其實人都非常好，不會特別刁難，只要盡力呈現自己，應該都會被教授看見吧。 以上，希望一切順利。