Skip to content

以其人之道還其人之身:如何用分治法對付 LeetCode / 刷題心得跟題庫分享

  • Misc

Intro

是的,當你看到這篇文章的時候,我還沒找到工作。因此,最近的幾個月,我如果不是在刷題,就是在沒網路的路上。

截至目前為止,我嘗試了將近 300 種不同題形的解法,有效題數是 209,約 1000 多次 commit。

刷題時間久了,對 LeetCode 這個東西不禁感到又愛又恨。甚至是恨的層次居多,為什麼?我認為有以下幾個原因:

真的用得到嗎?

當然,像 146. LRU Cache253. Meeting Rooms II 這種貼近實務的題目是再好不過了,但你不得不承認,大部分的題目還是有那麼派不上用場的意味在,那種感覺就像你在高中學了艱澀的數學理論,但並不知道怎麼在真實世界中應用它們一樣。

試想一下,你拿刷題的時間去嗑一本有關程式設計的書,或去想辦法弄些什麼專案,學到的「馬上可用的知識點」應該都比刷題多得更多。

應徵的公司在場上覆蓋三張陷阱卡,其中一張是神的宣告

你有沒有覺得,現在好多公司都好愛考刷題,先是聯繫到你,告訴你說「我覺得你很可能就是我們要找的 XXX」,然後也不跟你約時間,就丟一個考試連結給你。

然後你可能沒辦法在 20 分鐘內「把零移到前面」或找不到「買賣股票的進出點」,然後就失去了面試機會,或者再也沒有下文。這代表了一件事——開發者的價值被 LeetCode 給過度簡單地歸類了——如果你不刷題,不管你曾經開發過什麼,都不再有意義,因為你連門票都拿不到。

這種面試體驗,我至少就遇到過三次。

是的,即使你知道什麼是陣列、什麼是 swap、indexing,你也知道時間複雜度跟空間複雜度是在講什麼,但你就是想不出來怎麼把該死的 0 給移到前面去。

還記得 Homebrew 的開發者 Max Howell 因為不會翻轉二元樹被 Google 拒絕了,他氣得發了一篇反諷推文。不過他事後表明:我某種程度來說也很爛,我還是搞不太懂二元樹是什麼,但我不怪 Google 了。

這個例子可以很好地概括我目前對面試考題的想法:Get Over It。

當刷題儼然成為找工作的「內建」、必要條件,那麼也許,我們就不要再 ㄍ一ㄥ 了吧。

Read More »以其人之道還其人之身:如何用分治法對付 LeetCode / 刷題心得跟題庫分享

Fluent Python 讀書筆記(三)

物件參考、可變性與重複使用

  • 「變數是標籤,不是盒子」
  • 使用參考變數 (reference variable) 時,說「變數被指派給一個物件」會比較合理,畢竟——物件是在賦值之前建立的
  • 兩個變數被指派到同一個物件時,這兩個變數互為「別名(alias)」
  • 「每一個物件都有一個身份(ID)、一個型態跟一個值」,在 CPython,這個身份是 id(),回傳物件的記憶體位置(不同解譯器可能會使用不同東西作為 ID)
  • == 比較物件的值;is 比較物件的 ID
  • is== 快,因為它無法多載(不需要尋找或呼叫特殊方法來演算出一個值)
  • 原始物件的 __eq__ 會比較 ID,但大多數覆寫 __eq__ 的情況通常會加入或使用別的比較
  • tuple 不可變的意思是「保存在它當中的物件參考 ID 不變」,即使 tuple 可能存了可變的物件
  • 淺複製 (shallow copy) 即容器本身會被複製,但新的容器裡面保存的是舊的參考,例如 arr[:]arr.copy()copy(arr)
  • 實作 deep copy 要小心物件可能會循環參考 (Ring),要判斷物件是否已經複製過
  • 覆寫 __copy____deepcopy__ 可以控制 copy.copy()copy.deepcopy() 的行為
  • Python 函式傳遞的是參考(call by sharing) —— 即函數的參數 (parameter) 會指向引數 (argument) 的參考,換句話說,「函式內的參數就是其實際引數的別名」
  • 同上,這也是為什麼「函式的預設參數不要使用可變型態」,簡單的改良:預設為 None,在函式中判斷是否初始化新的可變物件
  • del 刪除的是參考,而不是物件本身;物件只有在「參考數量變成零」的情況下才有可能被回收,這種銷毀可能不是立即性的
  • CPython 回收記憶體的演算法主要是計算參考數量,這個參考數量存在物件本身,但假若有循環參考時,容易發生 memory leak
  • 在 CPython 的實作下,對 tuplestrbytes而言 s[:] 不會製作複本,而是回傳物件的參考
  • 在使用執行緒時,修改可變物件很難得到正確的結果:無法適當同步的執行序,會導致資料損毀;過度同步的執行序,會造成 deadlock

弱參考 (Weak Reference)

  • 常用在使用快取的情境下,須要「參考一個不會被保存太久的物件」
  • 弱參考是一種可呼叫的物件,它會回傳參考的物件,或者 None
  • 使用弱參考而非賦值,就不會讓物件的「參考數量」增加
  • 考慮使用 WeakKeyDictionaryWeakValueDictionaryWeakSetfinalize 這些內部使用弱參考的高階界面,而非自己用 weakref.ref 實作
  • 因為實作的限制,listdict 的子類別可以被弱參考(原始型態不行),而 inttuple 則完全無法被弱參考


字串常值的共用,是一種優化技術,稱為 interning,Cpython 會對小型的整數使用相同的技術,來避免沒必要的重複

Read More »Fluent Python 讀書筆記(三)

Fluent Python 讀書筆記(二)

一級函式

  • 在 Python 所有函式都是一級物件:
    • 可在執行階段建立
    • 可以指派給變數,或資料結構內的元素
    • 可以當成引數傳給函式
    • 可以當成函式的結果回傳
  • 如果一個函式的引數是包含函式,或回傳的物件是函式,它就是高階函式 (higher-order function),經典的例子是 mapfilterreduce
  • listcomp、genexp 可作 mapfilter 的工作,且更容易閱讀,後兩者已經沒有那麼重要了
  • 除了用來處理高階函式的引數外,匿名函式在 Python 並沒什麼其他用處,且通常難以閱讀
  • Python 的七種 callable
    1. User-defined functions: deflambda
    2. Built-in functions:以 C 寫成的函式,如 lentime.strftime
    3. Built-in methods:以 C 寫成的方法,如 dict.get
    4. Methods
    5. Classes: 透過 __new__ 建立,再經 __init__ 初始化
    6. Class instances:須實作 __call__(任何物件都能有函式的行為)
    7. Generator functions
  • 如同自訂類別的實例,函式會使用 __dict__ 儲存特定的使用者屬性
  • 幾個重要的函式專用特殊方法:`
    • __annotations__:參數與回傳註解
    • __closure__:綁定自由變數(free variables)的空間
    • __code__:中繼資料、及編碼後的函式內文
    • __defaults__:以 tuple 儲存正式參數的預設值
    • __kwdefaults__:以 dict 儲存限關鍵字的正式參數的預設值
  • 要知道函式需要什麼參數、以及有沒有預設值,使用 inspect 模組會比較方便。因為 __(kw)defaults__ 雖然儲存了預設值,但參數名稱卻是放在 __code__ 裡面,必須由後往前掃描一次,才能將每一個值與各自的參數連結

  • inspect.Signature 物件有一個 bind 方法可以拿來測試傳入的參數組合
  • 函式註釋(Function Annotations)常見的型態是類別,如 strint,或字串如 int > 0,註釋不會處理任何工作,會被保存在 __annotation__ 屬性裡
  • 對解譯器來說,註釋沒有意義,它只們是可能會被工具所使用的中繼資料
  • Guido 清楚地表示不想讓 Python 成為 Funtional Programming 語言(但是因為有 operatorfunctools 模組,可以善加運用在 FP 風格上)
  • 列出一些有用的 FP 工具:operator.itemgetteroperator.attrgetteroperator.methodcallerfunctools.partial
  • 在 Python 中廣泛採用 FP 語法的最大障礙,就是缺乏尾部遞迴消除 (tail-recursion elimination) 的最佳化功能
  • 「所有匿名函式都有一個嚴重的缺點:它們沒有名字」

Read More »Fluent Python 讀書筆記(二)

公園生活

  • Quote

只要在公園長椅上發呆的時間一久,就會發現風景這種東西其實要有意識才看得到。泛著漣漪的池子、長著青苔的石垣、樹木、花朵、航跡雲,這一切雖然盡收眼底,其實等於視而不見,只有在意識到其中一樣事物,例如意識到在池面上游泳的水鳥時,水鳥才會從周遭的一切中切割出來。

她的耳垂上,該說是耳環嗎,嵌著一個大小像戒指般的粗厚金屬,開了個圓洞。空洞的另一邊,看得到駒澤路上塞住的車陣。

新聞畫面,特別是播報戰禍的影像,關掉聲音來看的話,人類就只是一具具軀體,這在螢幕上成了一件再自然不過的事,給人一種新的衝擊。一旦轉開音量,不論是賓拉登、布希、包威爾、夏隆、阿拉法特,或是新聞旁白,吐出的都是連串艱澀的詞句,彷彿那些詞句孕育出思考,而這孕育出的思考又在醞釀著什麼。如果把聲音關掉,就完全無法看出人類的思考了,所看到的只是或走、或坐、或躺的人類軀體罷了。

穿了五年的運動褲鬆緊帶已經鬆了,只要一邁出步伐就會往下滑落。我想把褲繩綁緊,不過一邊褲繩的前端縮到繩口裡去,找不出來了。

錄放影機的時鐘顯示我打電話的時間是「20:34」,掛上話筒後是「20:43」。差一分鐘就正好十分鐘了,我並不是說要用那一分鐘來說什麼,只是覺得應該可以用那一分鐘再說些什麼。

她一派輕鬆的模樣,彷彿身上若是掛了條圍裙,八成還會在上面抹抹手吧!

簡而言之,只要在插花的時後想像花器上方有個透明的球體就行了,而花辨識插在那個球體的內部。從花器往上方正中間延伸的花材稱為「真枝」,搭配真枝有朝左延伸的「副枝」,和向右延伸的「體枝」。插花就是由這三種役枝所構成的。

只要和鞠子在一起,就會覺得整個人鬆懈下來。那是一種和別人在一起無法體會到的奇妙感受,我的眼前浮現人造衛星脫離軌道後,失去衝勁的背影。

她希望我放下沈重的貨物,輕盈地四處飛躍。不過我卻害怕真要這麼做的話,就會如同漂浮於大海中的泡沫,不論隨波逐流到哪裡,最終都會破滅消逝。

殘酷的語言多半都是出自於浮著笑意的雙唇間。

Fluent Python 讀書筆記(一)

  • Python

特殊方法

  • 資料模型對 Python 來說是一種「框架」,這個框架(可以想成 Python 的解譯器 Interpreter)會呼叫特定的方法(指 method),這個特定的方法就是 Dunder Method
  • 當你實作了 __getitem__,就代表類別實例可以是可迭代(iterable),且支援了 indexing、slicing、函式庫如 random.choice
  • 若可迭代物件沒有實作 __contains__,在 in 運算子下的預設的行為是循序掃描
  • len() 對於內建型態(如 list、str、bytearray),解譯器並非呼叫 __len__,而是回到底層的 C 結構查詢,因為速度快很多 —— 這也說明了為什麼是 len(collection) 而不是 collection.len,這是一種「在內建物件效率與語言一致性之間取得平衡」
  • for 語句私下是呼叫 iter() 再呼叫 __iter__()
  • 一般而言,你的程式不該自己呼叫特殊方法,而是透過內建方法(如 len、iter、str)
  • 交互式終端與除錯程式會對運算式的結果呼叫 repr()
  • __repr__ 回傳的字串必須精確,盡可能匹配原始碼,好表示「物件如何建立的」以利再次重建
  • 沒有自訂的 __str__,解譯器會呼叫 __repr__ 提供回饋
  • 反向運算子 (reverse operator) 應用在交換律的後備機制如 a * bb * a
  • 擴增賦值運算子 (augmented assignment operator) 意在結合中輟運算 (infix) 與賦值行為,如 a <<= b
  • 「讓使用者使用核心開發人員所使用的工具」,我的理解是,將底層 API 開放給上層使用
  • 「特殊方法其實是魔術方法的相反」,魔術功能通常意指「你不能在自己定義的物件中模擬這些功能」

序列

  • 牢記可變 VS. 不可變、容器序列 VS. 一般序列的不同
  • List comprehension 只做一件事:建構新序列
  • tuple 可以當成「不可變序列」來用,也可當成沒有欄位名稱的「紀錄」(有 unpacking 的優勢)
  • 變數名 _ 翻譯成「啞變數」(使用底線有缺點,會被當成 gettext 的函數別名)
  • 當賦值的對象是切片時,賦值物件必須是 iterable,如 l[2:5] = [20, 30]
  • 序列的 +* 一定都是建立新物件
  • += (原地算法)的特殊方法是 __iadd__, i 代表 in-place,如果 __iadd__沒有被實作的話,Python 會退而呼叫 __add__,可以解讀成「是否真的是原地算法,取決於運算哪種物件」—— 同一個概念可以套用到 *=
  • 檢視 Python 的 bytecode: dis.dis('<your code here>')
  • 重要的 Python API 慣例:當函式或方法就地改變物件(沒有建立新的物件)時,必須回傳 None,簡單的範例是 list.sort(),反例是 sorted(list)
  • 另一種快速的數值儲存方式,是使用 pickle 模組來做物件序列化,使用 pickle.dump 來儲存一個陣列的浮點數幾乎和 array.tofile 一樣快
  • 內建的 memoryview 類別是 Python 的一個廣義 NumPy 陣列結構,可以用它在資料結構間共用記憶體(PIL、SQLite、NumPy 陣列等),而不需要先做複製
  • 移除 deque 中間的項目並不是那麼快,它其實最適合在兩端進行操作
  • queue 函式庫實作的佇列如 Queue、LifoQueue 用來在執行緒之間進行安全通訊
  • Python 的 sort 是使用 Timesort,根據資料的排序狀況來決定採用 MergeSort 或是 InsertionSort

Read More »Fluent Python 讀書筆記(一)

火花

在山間迴響的煙火聲蓋過了我的聲音,我對渺小的自己很失望,但我之所以沒有被逼到絕望,只因為我對大自然與煙火抱有崇高的敬意,就只是如此平凡的理由。

不過,我們必須把自己的畫作展示出來讓某人買下,選用的畫框想必會大幅改變畫作給人的印象。完全放棄任何商業性的行為,說不定會改變自己作品本來的意義,那樣等於是完全沒有保護作品。

我們早已過了會自作多情的年紀;我們已經到了就連假裝自作多情而招來惡評,都視為一種工作的年紀。

而且,我早已隱約的察覺,我們的工作也在漸漸減少。過去令我恐懼、讓我成長的後輩們也已邁向新的人生了。我可以肯定的說,我們那彷彿永無止境的無藥可醫的歲月,絕非只是荒唐的騷動。我們是真的感到恐懼,我們打從心底恐懼父母、戀人日漸老去,一切將會再也來不及。我們是真心害怕自己主動結束夢想,彷彿舉世皆為陌生人的頁晚一再來臨。

劇場這些年來累積的笑聲,都被這骯髒的牆壁吸收,觀眾一笑,牆壁也會跟著一起笑。

耗費長時間一直在做沒有必要的事情很可怕吧?在僅此一次的寶貴人生中,挑戰或許會完全沒有結果的事情很可怕吧。排除無謂的徒勞,也就等於是在迴避危險。無論是膽小、自作多情或是無藥可救的笨蛋都行,總之只有敢站上充滿風險的舞台,全力向顛覆常識去挑戰的人,才能夠成為相聲師。透過這耗費漫長時光的莽撞挑戰,我認為我已得到自己真正的人生。