#92 今年一月份 APCS 程式設計第三題 - 切割費用

前陣子,我的小徒弟去報名他人生第一次的 APCS 考試,可以說是他學習電腦科學以來第一次的正式上機考試.一共有四題的程式設計題目,前面兩題算是簡單的,第三題算中等,第四題比第三題再進階一點點.這篇文章就來談談第三題的解題思考.

完整的題目在 https://zerojudge.tw/ShowProblem?problemid=f607 ,首先,要解題之前,請先確定自已己經百分百了解題目.這一個題目的解決過程可以分成下列 2 個部份,

1. 讀取輸入參數,因為輸入參數並非按照切割次序而輸入的,我們要進行切割時是按照次序來切割的.因此,我們必須對輸入參數做處理,以讓沒有次序的參數集合變成有次序的參數集合.

2. 每一次切割時,都需要知道左右兩端的長度,這樣才能算出該次切割的費用,而知道左右兩端的長度,這需要一個快速的行為才能符合題目的要求.因為題目提到切割次數最多會到二十萬次,並且棍子的長度可以到 10 7 那麼長.

有關讀取輸入參數的內容,基本上有兩種做法,可以把切割資料全部讀進來之後,再以切割次序做排序.若是這樣做,這個動作將花費 O (n lg n)  ,假設是用 quick sort. 除此以外,我們可以換個角度思考,題目給的切割次序不會出錯,也就是說當切割資料讀進來時,切割次序就是一種 key,不會重覆,因為第 n 次切割只會發生一次.所以可以用 (key, value) 的 hash table 來存放切割資料.由於 hash table 的 set , get 都是 O(1) ,所以這讀取動作將花費 O(n).

因此,第一個部份的時間複雜度最小可以到 O(n).

接下來,第二部份是計算每一次切割的費用.可以想像正在發生第 k 次的切割,也就是我們要想一個快速的方法讓我們可以查到在第 k 次切割時,當時所在的位置往左邊和往右邊走碰到的第一個切割點. 假設一開始用一個 boolean array 來代表被切割的點,

index :  0    1    2    3    4    5  ......98   99  100    101    102    103  ........ n

value:   f     f     f     f    f     t  .....  t     f       f        f        t         f      .......  f

一開始 array 的都是 false ,被切割過的點就變成 true,假設第 k 次的點要切割在第 100 個位置,而 98 和 102 是 true,所以這一次的切割費用是 102 - 98 = 4.如果以程式的角度來看的話,你得寫一個 for loop 從 100 往右邊走,找到第一個 true ,然後再往左邊走找到第一個 true,然後再做減法.這樣的尋找方式是 O(n),而這個會發生在切割資料的迴圈裡,假設切割資料是 m 筆,因此這一段的時間複雜度是 O(nm),一旦 n 和 m 都很大時,這就相當於是 O(n*n).而 n 最大的值會到 20 萬,因此 O(n*n) 是不能接受的.因此,用 array 做搜尋是不合格的,所以我們必須用其他的資料結構,並且這個資料結構所花費的成本要小於 O(n) (比 array 一個一個找再快).

這時候,答案其實已很明顯了,能夠比 array O(n) 還要快的只有 binary search tree O(lg n) 或是 hash table O(1) .在這一個動作的過程中,我們需要能 "往左走" 和 "往右走" ,Hash table  顯然不會是個好選擇,因為 hash table 無法儲存元素之間的 "順序",因此,就剩下 binary search tree 了.binary search tree 在儲存的過程花費 O(lg n) 時間,而尋找的過程也是花費 O(lg n) 時間,而且 binary search tree 的特性讓我們可以 "往左走" "往右走" 來找到最近被切割過的位置.因此,採用 binary search tree 之後,時間複雜度可變成 O (m lg n) ,如果 m 和 n 都很大時,就是 O( n lg n),這個比剛剛的 O(n*n) 快上很多.

最後,以下的程式碼是我的小學徒提供的,在很大的測試資料下仍花費了 0.25 秒完成,雖然不是最快,但也符合了題目 2 秒內的要求.

Share:

#91 如何寫有影響力的履歷表

根據 Facebook 社團上的成員資料,目前三百多位成員裡有將近 40% 成員的年紀在 34 歲以下,因此,希望這篇文章可以提供年輕人有關撰寫履歷表內容時的參考.

一般來說,我會把履歷表的寫法分成兩種,一種是屬於年輕工程師的寫法,另一種是資深工程師的寫法,我將年資不到十年的人定義為年輕工程師,所以可能是在 32 - 36 歲之間,就看你在幾歲從學校畢業.在這年資以下的人,撰寫履歷表時應該要著重在技能的部份.也就是說,你得在履歷表上說明你用過了那些工具與方法來製造軟體系統,以及你運用了那些專業知識 (課本上學的) 在你的工作上.比如,某個年輕工程師從事電商系統前端功能的開發,屣歷表上就需要清楚說明用 Javascript/TypeScript 寫了什麼東西,是否用到其他的 framework,如 Angular 等等,並且做過那些功能,如購物車系統,付款流程,購物體驗等等.把這些東西寫清楚來,讓看履歷表的人明確知道你過去曾用過的工具以及熟悉的產業環境是什麼,這樣能幫助雇主加快認識你的速度.

為什麼年輕工程師要寫這樣的內容呢 ? 因為年輕工程師通常被給予的任務是小而明確的,如解 bug 或做一些小功能.履歷表上寫一些技能類的事情可以幫助未來的雇主知道你過去做過些什麼,也能幫助雇主評估是否要找你來進行面試.

如果 32 - 36 歲以上的工程師 (超過十年的業界經驗),理論上來說,在業界工作了十年應該要達到資深工程師的水準了.我猜想在台灣的公司對於職稱上的給定標準並沒有一致且較寬鬆,所以中小企業或是非資訊科技領域的公司做了三五年後就能得到資深工程師的職稱.在規模大且制度嚴謹的公司裡,要在三到五年內拼到資深工程師是件不容易的事情,資深工程師的履歷表就應該著重於有關 "影嚮力" 的事情,比如,製造一個付款交易系統,讓整個網站可以在一分鐘之內完成 n 筆交易,使得網站可以承受 m 個使用者的流量.再舉另一個例子,重新製造了購物車系統,讓原本客戶評價極差的用戶體驗變成零負評的新體驗,並且讓網站提升 n % 客戶滿意度.再舉另一個例子,製造了一套基礎建設程式庫用於處理公司內所有系統的溝通機制,將原本平均一分鐘執行時間的動作提升至十秒鐘完成.或是一個更利害的例子,製做了一個很利害的 open source software,放在 Github 上得到了 n 顆星星,造福了世界上許多的軟體工程師.透過這些簡單例子,我相信你一定明白我所謂的 "影響力" 是什麼意思了.

回過頭來,並不是說年輕工程師就不用寫影響力.對於年輕工程師而言,如果你可以寫出令人信服的影響力,一定要寫下來,因為那些都是能讓你換到新公司時談職位與薪水的利器.

不論你寫的是技能比較多或是影響力比較多,千萬要記得別亂寫或是誇大地寫.若有機會面試時,這些技能和影響力是很容易被檢查出來的,一旦面試官發現你在 "唬爛" 時,你有可能永遠不會出現在這公司的面試名單裡.

履歷表內容的基本上包含了你的個人基本資料,工作經歷,學歷,技能以及一些參考資料.以我的經驗來說,我會將影響力放在工作經歷的內容裡,所以每一個工作都會是一段描述,而不是一行文字只包含公司名稱,職位名稱和時間而己.通常來說,一到兩頁的履歷表就應該要把你自己說明清楚,過長的內容,雇主很容易跳過不看,因為有名的公司每天都會收到很多履歷資料,沒有人會把細節看完.同時也要告訴一些年輕的工程師,工作要慎選,常常換工作並不是一件好事情,技能的程度高低也許不會受到換工作的影響,但我相信影響力是需要時間累積的,若常常換工作,則很難說明與說服其他人你在短時間裡能在一家公司做出有影響力的事情! 所以,找新公司時要好好想清楚,工作經歷就像是學歷一樣無法抹去也無法作假的,因此,在換公司時也要好好想想你該如何在新公司做出影響力的事情.同時這個題目也可能當成你和你老闆一對一面談時間裡的內容.

Hope it helps,

Share: