睡過頭…
同步 post 於 WP
Q1. Magic Squares In Grid
給定一個 100 x 100 2d-array，
問有多少 3 x 3 sub-array 是魔方陣。
(即 行列對角線都是 15 且數字 1~9 不重複。)
這種範圍超小的拼速度題目重點變成了怎麼寫比較快，
直覺的做法有兩種：
直覺的做法有兩種：
- 直接靠定義作，每個 sub-array 檢查八條跟數字範圍。
- 因為 3×3 魔方陣只有一種 (跟他的旋轉鏡射) 先把那種手寫出來後做 pattern matching 。
由於還要做八種旋轉鏡射，這題當然是寫 1. 快很多啦。
Q2. Keys and Rooms
有許多房間，每個房間都有其他房間的鑰匙。
你一開始在房間 0 ，問你能不能進入所有房間。
非常明顯的純 BFS 題，事實上這根本是直接給你 adjacency matrix 的意思。
Q3. Split Array into Fibonacci Sequence
將一個 digit 串 拆成 >= 3塊，
滿足剛好由左而右形成類似費氏數列的關係。
例如 “110111122335588143″ 拆成 [11, 0, 11, 11, 22, 33, 55, 88, 143]
串長度至多 200 ，一看又是純粹考實作。
因為要處理 leading zero 問題，
最簡單的想法當然是把整個數列以整數方式儲存後再轉為字串，作字串比對。
這樣單一次比對的複雜度是
，顯然很充裕。
最簡單的想法當然是把整個數列以整數方式儲存後再轉為字串，作字串比對。
這樣單一次比對的複雜度是
，顯然很充裕。
那麼就只要枚舉前兩項 F1, F2 即可。
Q4. Guess the Word
給你一個 100 words 的字典，單字長度都是 6。
對方已經想了一個字典內的單字，你要在 10 次 guess 中猜到它。
你每次 guess 可以猜一個單字，他會告訴你有多少個字元位置正確 (match)。
例如 答案為 “abcdef" 你 guess(“abccfe") 會得到 3
又是 100 看到就知道複雜度不是重點。
考量我們有一個 wordlist 的情況，有什麼做法能比亂猜更好？
因為字典在我們這邊，我們可以每個都 guess 看看，看 match 的分布哪個最好。
怎麼判斷 match 的分布哪個最好 最單純的想法就是 minimize max value。
因為字典在我們這邊，我們可以每個都 guess 看看，看 match 的分布哪個最好。
怎麼判斷 match 的分布哪個最好 最單純的想法就是 minimize max value。
照著這樣做就可以過了。
(第一次寫的時候根本沒有minimize max value，固定 guess index 0 當然的錯了)
時間分配
Q1 (+26min)
Q2 (+11min)
Q3 (+15min)
Q4 (+16min) (+1bug)
賴床太久 寫太慢 好像就這樣
Q2 發現對 python 語法不太熟 (有內建的好用 queue 嗎)
馬上轉寫 c++
Q2 發現對 python 語法不太熟 (有內建的好用 queue 嗎)
馬上轉寫 c++
Q3 還是跟 python 語法不太熟 array of chars / string 搞好久
沒有留言:
張貼留言