[心得] 政大APCS面試

[ypl891218 (YPL)]

（代Po)

政大資訊科學面試心得
    小弟學測考爆，好在有考apcs能填幾間資訊相關的學校。
    不廢話，直接進入正題。
    面試的時候五人一組，面對三個教授，桌上給你紙筆以回答題目。
    面試時間約30分鐘，一開始教授會先讓5個學生做1分鐘的自我介紹，接著會分別出題
目，讓5個學生以紙筆回答。
    第一題是程式題，題目是給你一個陣列，叫你以最小時間複雜度求第K大的數字。超
級水題，我想到的是直接sort完後，O(1)輸出答案。
    第二題是英文題，給你一篇英文文章，要你在2分鐘內讀完，並在紙張上寫出你看了
什麼。我記得是講被火燒掉的聖母院，蘋果公司說要協助出資修復的文章。
     最後一題是數學題，題目說有四個海盜要分金幣，由位階高的一位提出一個方案，
只要有50%（含）以上的人同意，就會按照方案分金幣，否則會被丟進海裡餵鯊魚，接著
換次高位的海盜題方案。題目問位階最高的海盜如何能得到最多的金幣（假設海盜都是理
性的）。這題我的想法有二，ㄧ則籠絡次高位，以25/25平分金幣，二則是直接告訴教授
說，第一位50全拿，然後告訴第二位以後第一的位子給你，讓第二位支持他，如此便能以
50%通過方案。我其實還不知道正確的解法，大家可以想想看XD
    政大的教授人都不錯，希望能金榜題名

——————————-

（本人的看法）

第一題求k大值，其實是有更好的解法的，有興趣可以研究一下。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.21.169
※ 文章網址: https://www.ptt.cc/bbs/SENIORHIGH/M.1555756037.A.7B9.html
推 Apache: sort完O(1)還能叫O(1)嗎XD
→ Apache: 這題回答用quicksort的partition來做會不會比較高分
推 Dreamer48763: https://youtu.be/qXg1r_FwkvA
推 headender: 海盜拿金幣是老智力測驗問題了
推 xcnx123: 如果k是常數，取k次最大值就只要O(n)啦 最簡單暴力
推 skyHuan: median of medians => O(n)
→ tomsawyer: 不是ubi嗎(x
→ Apache: mom只是避免O(n^2)的優化策略吧
推 skyHuan: m-of-m's可用來找第k大元素花O(n)
→ skyHuan: 樓上說的應該是Qsort可用m-of-m's選PK來防止worst case達
→ skyHuan: 到O(n^2)
推 skyHuan: 但被m-of-m's當作O(1)計算的小組內sorting其實常數很大，
→ skyHuan: 花的時間還是很常，又碰到worst case的機率很低，所以Qso
→ skyHuan: rt實作上不太會採m-of-m's來避免worst case
推 skyHuan: 二樓的partition有可能worst case，例如資料由小到大排
→ skyHuan: 序會導致partition失效，每次O(n)要做k次，複雜度還是在O
→ skyHuan: (nk)
推 Embrace0209: 你應該是我認識的人
→ Embrace0209: 祝你上啦
推 ivan010517: 我是有跟你握手的那個 希望以後可以認識認識
→ s3131212: 第一題不就 selection algorithm，不要 sort 啦 XD
→ ypl891218: 我是代po的，你們怎麼認得出來這是誰的文XD
推 hanyi0923: 第一題是O(N)經典題，快排另外一邊不排就是線性了
→ Apache: T(n)=T(n/2)+n
推 Apache: 研究了一下skyHuan講的mom 實際上還是QuickSelect算法
→ Apache: 實際上使用隨機選擇pivot 機率上就能達到平均複雜度O(N)