Skip to content

Misc

步入中年的轉職馬拉松 / 一個低端工程師的自白

Intro

在 2019 年底,還在上個公司就職的我,應一個面試邀約拜訪了 91APP。因為拜社群之福,我在早期就有「持續面試很重要」這個概念,不管你當下有沒有工作。

當時的我剛完成一個機器學習的基礎設施,讓整個流程得以自動化,頗為自得意滿。我天真地以為,別人會找我去面試,單純是因為我值得。

也是在這個面試中,我踩了人生第一個面試地雷——那就是抱怨當前的工作。我說:公司專案太多又太雜了,又都只有一兩個人負責。

結果可想而知,在隔天收到了感謝函。不過幸運的是,邀約我的前輩順帶給了一些很客氣的提點。他在信裡這麼說:「你的硬實力是不錯的,但你缺乏軟實力。」

同一個時期,想要離職的念頭開始萌芽。當然,我並非討厭這個工作,反而更像是漸漸找不到工作的意義了。上下班的時候,腦中不停發出例外,可以說它是一種 ValueError ,而當時的我並不知道如何去處理這個例外。

造成這個例外的可能情形:

  • 潛意識地知道自己知識量不足(軟實力),但沒花足夠的時間來彌補,大部分時間都花在拼湊和硬幹上面(硬實力)
  • 腦海中有「標準」的藍圖,但不是很清楚,而公司的標準接近能動就好,因此無所適從
  • 開始懷疑自己,懷疑專案的發展性
  • 一直以來的單打獨鬥,嚮往可以激盪討論合作的環境,說白一點就是希望有人帶
  • 不想再扮黑臉(沒錯我是 INTP)

終於,某天公司的舊系統因為太舊出問題了(單純就是因為太舊),雖然我沒接觸過該系統,但身為後端人員,多少還是覺得有點責任。當下去了一趟 Legacy 後,發覺再也忍受不了了。我喪失了所有自信。我只想讓腦袋重新開機。

我必須馬上去談這件事。當天,我跟主管提出離職的想法。我只知道自己該做出一些改變,或者更深入地說,我害怕因為長時間忽略這些內心感受,進而潛移默化成自己不想變成的那個人,再也做不出正確的決定。我也想起有人說三十歲是工程師生涯重要的臨界點。那麼與其不上不下的,不如去尋求一個長遠的突破。

借托爾斯泰之筆,我們可以這樣隱晦描述──「幸福的 RD 總是幸福的,不幸的 RD 各有各的不幸。」

也就是說,即使在別人眼裡,工程師看起來是那樣吃得好穿得暖,但事實是每個工程師和你們一樣,都有各自難以解決的問題。就如同我的 ValueError

Read More »步入中年的轉職馬拉松 / 一個低端工程師的自白

以其人之道還其人之身:如何用分治法對付 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 / 刷題心得跟題庫分享

第一次開發選服就烙賽

Intro

自從邱威傑市民服務網站上線後,一直想要完成這篇,紀錄一下這一個月多月開發以來的心得感想,但因為專案完成,本身也剛換工作,無預警進入了懈怠期,不知不覺就拖到現在了

晚上和呱吉跟他的政治團隊吃飯,回家後提醒自己寫下紀錄,今天大概就能算是一個圓滿的結束點吧~

18.12.07 確定接下案子

在這之前,第一次和負責的團隊成員——很年輕的法律系學生 @Eddy 見面,一開始當然不知道呱吉會打算怎麼做這個系統,原本以為會有前輩主導開發,去參與討論或插花即可,但實際上是最多找2-3個人做;也以為是要做能讓多個議員註冊、使用的平台,但需求聽起來卻像呱吉個人的宣傳式網站

我認知到一件事,那就是 Eddy 沒辦法準確評估我的技術水準,只知道我有做過網站。令人訝異的是,當天握手之後就直接把任務交給我了。當然,這是風險評估出了問題呢,還是完全信任夥伴?我選擇相信後者。(團隊的風氣感覺是年輕人放手去做就對了,烙賽沒關係?)

專案需求雖然很簡單:使用者填寫表單、送出後可以在後台編輯。但我還是一樣超沒信心,因為認知到:

  • 我希望這是一個開源專案,如果要開源,會有資安上須考量的風險,加上呱吉是公眾人物,容易成為箭靶
  • 短期會有高流量,分散式部署是必要的;自己沒有實際維運過分散系統,大概知道是怎麼做,但沒把握
  • 重點是前端視覺與使用者體驗,但自己頂多做後端,前端雖然會寫,但根本在標準之下

Read More »第一次開發選服就烙賽

以Python實作演算法 – Algorithms Implements using Python

  • Misc, Python

TOC

圖論 Graph Theory

G(V, E)

  • 由頂點(vertex, node)和連接頂點的邊(Edge)關聯成的圖形
  • 其中關聯分作有方向性(directed)及無方向性(undirected)
  • 須考慮最大流問題(maximum flow)

在程式語言有幾種方式來建構Graphs:

相鄰矩陣 adjacency matrixes

image
圖片來源

陣列 edge list representation

應用

  • 最短路徑演算法 Shortest Path Algorithm: GPS, 高頻交易
  • 生成樹協定 Spanning Tree Protocol, STP
  • 爬蟲

廣度優先搜尋 Breadth-first Search, BFS

  • 時間複雜度:O(V+E)(分別遍歷所有節點和各節點的所有鄰居)
  • 空間複雜度:O(V)(Queue中最多可能存放所有節點)
  • 用於有效率的迭代(traversal)
  • 迭代的方式為鄰近的先訪問(level-ordered)
  • 劣勢在於儲存指標記憶體空間,有時用DFS替代
  • 使用FIFO的Queue來實作,Queue為空代表完成迭代

應用

  • machine learning
  • Edmonds-Karp演算法
  • Cheney演算法

以Python實作,輸出請參考gist

深度優先搜尋 Depth-first Search, DFS

  • 時間複雜度:O(V+E)
  • 空間複雜度:O(logV)(訪問至末端節點後LIFO,Stack最多只會同時存在logV個節點,也就是樹的高度)
  • 為了解Maze Problem而生的演算法
  • 效能比BFS稍佳
  • 使用LIFO的Stack來實作

應用

  • 拓撲排序 Topological Order
  • Kosaraju演算法: 推薦系統 Recommand System
  • 判斷Grapth是否有cycle(DAG)
  • Maze

以Python實作,輸出請參考gist

Read More »以Python實作演算法 – Algorithms Implements using Python

以Python實作資料結構 – Data Structure Implements in Python

  • Misc, Python

以Python實作資料結構

tags: data-structure, python

TOC

簡介

什麼是資料結構?為什麼要使用資料結構?

是電腦中儲存、組織資料的方式,可以讓我們有效地儲存資料,並讓所有運算能最有效率地完成

演算法的運行時間是根據資料結構決定的,所以使用適當的資料結構來降低演算法的時間複雜度,如:

  • 最短路徑演算法若無適當的資料結構,運行時間是O(N^2),使用(heap/priority queue)可以大幅降低運行時間至O(N*logN)

抽象資料型態 Abstract Data Types

簡單而言,ADT是針對資料結構的「規範」或「描述」,像是物件導向語言裡面的interface,但不會實作細節

舉例堆疊的ADT描述:

  • push(): 插入元素 item 至堆疊頂端
  • pop(): 移除並回傳堆疊頂端的元素
  • peek(): 看堆疊頂端的資料而不取出
  • size(): 看堆疊的長度

ADT跟資料結構的關係

每個ADT在底層都有相對應的資料結構去實作ADT裡定義過的行為(method)

ADT Data Structures
Stack array, linked list
Queue array, linked list
Priority Queue heap
Dictionary/Hashmap array

時間複雜度 Big O notation

描述演算法的效率(複雜度),舉例來說,A宅想要分享他的D槽給B宅,有以下幾種做法:

  1. 台北騎車到屏東B宅家
  2. 用網路傳輸,不考慮被FBI攔截的情況
1GB 1TB 500TB
騎車運送硬碟 600 min 600 min 600 min
網路傳輸 3 min 3072 min 1536000 min

從上表來看,騎車這個選項雖然聽起來很蠢,但不管硬碟有多大,都能確保10個小時內可以送達—— O(1);至於網路傳輸隨著檔案越大,所需的時間也越長 —— O(N);從這裡就可以看出常數時間(constant time)和線性時間(linear time)的差別對效率的影響有多大了

在表現複雜度函數的時候,有幾個通用的規則:

  • 多個步驟用加法: O(a+b)

  • 省略常數: ~~O(3n)~~ O(n)

  • 不同的input用不同的變數表示: ~~O(N^2)~~ O(a*b)

  • 省略影響不大的變數: ~~O(n+n^2)~~ O(n^2)

陣列 Array

物件或值的集合,每個物件或值可以被陣列的索引(index, key)識別

  • 索引從0開始
  • 因為有索引,我們可以對陣列做隨機存取(Random Access)

優點:

  • 隨機存取不用搜尋就能訪問陣列當中所有值,執行速度快O(1)
  • 不會因為鏈結斷裂而遺失資料
  • 循序存取快

缺點:

  • 重建或插入陣列須要逐一複製裏頭的值,時間複雜度是O(N)
  • 編譯的時候必須事先知道陣列的大小,這讓陣列這個資料結構不夠動態(dynamic)
  • 通常陣列只能存同一種型別
  • 不支援連結串列的共享

Implements

行為 big O
search 搜尋 O(1)
insert 插入第一項 O(N)
append 插入最後一項 O(1)
remove 移除第一項 O(N)
removeLast 移除最後一項 O(1)

以Python實作

random indexing: O(1)

linear search: O(n)

連結串列 Linked List & 雙向連結串列 Double Linked List

  • 節點包含datareferenced object
  • 連結的方式是節點(node)記住其他節點的參考(reference)
  • 最後一個節點的參考是NULL

優點

  • 各節點型態、記憶體大小不用相同
  • 動態佔用的記憶體,不須事先宣告大小
  • 插入、刪除快O(1)

缺點

  • 不支援隨機存取,只能循序存取(sequencial access),時間複雜度為O(N)
  • 須額外空間儲存其他節點的參考
  • 可靠性較差,連結斷裂容易遺失資料
  • 難以向前(backward)訪問,可以用雙向連結串列來處理,不過會多佔用記憶體空間

Implements

行為 big O
search 搜尋 O(N)
insert 插入第一項 O(1)
append 插入最後一項 O(N)
remove 移除第一項 O(1)
removeLast 移除最後一項 O(N)

註:連結串列沒有index,處理插入或移除第N項會需要先循序找到插入/移除位置,因此會需要O(N)的時間

以Python實作

以下的代碼是我實作的範例,有錯誤煩請指正。

主要概念是實作__getitem__來循序存取(indexing),另外Double Linked List支援反向存取,故訪問lst[0]lst[-1]皆可以達成O(1)的時間複雜度

執行結果請參考travishen/gist/linked-list.md

Linked List現實中的應用

  1. 低級別的內存管理(Low Level Memory Management),以C語言為例:
  • malloc()free(): 見Heap Management
  • chart * chart_ptr = (chart*)malloc(30);: 取得30byte的heap memory
  1. 許多Windows的應用程式:工具列視窗切換、PhotoViewer
  2. 區塊鏈技術

image
[圖片來源]

堆疊 Stack

  • 推疊是一種抽象資料型態,特性是先進後出(LIFO, last in first out)
  • 在高階程式語言,容易用array、linked list來實作
  • 大部分的程式語言都是Stack-Oriented,因為仰賴堆疊來處理method call(呼叫堆疊, Call Stack)。

Implements

行為 big O
push 將資料放入堆疊的頂端 O(1)
pop 回傳堆疊頂端資料 O(1)
peek 看堆疊頂端的資料而不取出 O(1)

應用

  • call stack + stack memory
  • 深度優先搜尋演算法(Depth-First-Search)
  • 尤拉迴路(Eulerian Circuit)
  • 瀏覽器回上一頁
  • PhotoShop上一步(undo)

註:任何遞迴(recursion)形式的演算法,都可以用Stack改寫,例如DFS。不過就算我們使用遞迴寫法,程式最終被parsing還是Stack

Stack memory vs Heap memory

stack memory heap memory
有限的記憶體配置空間 記憶體配置空間較大
存活時間規律可預測的 存活時間不規律不可預測的
CPU自動管理空間(GC) 使用者自主管理空間
區域變數宣告的空間不能更動 物件的值可以變動,如realloc()

以Python實作

Using Lists as Stacks

佇列 Queue

  • 佇列是一種抽象資料型態,特性是先進先出(FIFO, first in first out)
  • 在高階程式語言,容易用array、linked list來實作

應用

  • 多個程序的資源共享,例如CPU排程
  • 非同步任務佇列,例如I/O Buffer
  • 廣度優先搜尋演算法(Depth-First-Search)

以Python實作

參考

二元搜尋樹 Binary Search Tree

主要的優點就是時間複雜度能優化至O(logN)

  • 每個節點最多有兩個子節點
  • 子節點有左右之分
  • 左子樹的節點小於根節點、右子樹的節點大於根節點
  • 節點值不重複
Average case Worst case
insert O(logN) O(N)
delete O(logN) O(N)
search O(logN) O(N)

以Python實作insert, remove, search,執行結果請參考gist

BST現實中的應用

  • OS file system
  • 機器學習:決策樹

平衡二元搜尋樹 Balancing Binary Search Tree, AVL Tree

  • 能保證O(logN)的時間複雜度
  • 每次insert, delete都要檢查平衡,非平衡需要額外做rotation
  • 判斷是否平衡:
    • 左子樹高度 - 右子樹高度 > 1: rotate to right
    • 左子樹高度 - 右子樹高度 < -1: rotate to left
    • image
Average case Worst case
insert O(logN) O(logN)
delete O(logN) O(logN)
search O(logN) O(logN)

不適合用在排序,時間複雜度為O(N*logN)

  • 插入n個:O(N*logN)
  • in-order迭代:O(N)

繼承上面BST繼續往下實作,有bug請協助指正,執行結果請參考gist

  • 任一節點設定完left或right,更新該節點height
  • 每個insert的call stack檢查檢查節點是否平衡,不平衡則rotate

紅黑樹 Red-Black Tree

  • 相較於AVL樹,紅黑樹犧牲了部分平衡性換取插入/刪除操作時更少的翻轉操作,整體效能較佳(插入、刪除快)
  • 不像AVL樹的節點屬性用height來判斷是否須翻轉,而是用紅色/黑色來判斷
    • 根節點、末端節點(NULL)是黑色
    • 紅色節點的父節點和子節點是黑色
    • 每條路徑上黑色節點的數量相同
    • 每個新節點預設是紅色,若違反以上規則:
    • 翻轉,或
    • 更新節點顏色

image

Average case Worst case
insert O(logN) O(logN)
delete O(logN) O(logN)
search O(logN) O(logN)

github上用python實作的範例:Red-Black-Tree

優先權佇列 Priority Queue

  • 相較於Stack或Queue,對資料項目的取出順序是以權重(priority)來決定
  • 常用heap來實作

二元堆積 Binary Heap

  • 是一種二元樹資料結構,通常透過一維陣列(one dimension array)
  • 根據排序行為分成minmax
    • max heap: 父節點的值(value)或權重(key)大於子節點
    • min heap: 父節點的值(value)或權重(key)小於子節點
  • 必須是完全(compelete)二元樹或近似完全二元樹

註:

  • heap資料結構跟heap memory沒有關聯
  • 優勢在於取得最大權重或最小權重項目(root),時間複雜度為O(1)
time complexity
insert O(N) + O(logN) reconsturct times
delete O(N) + O(logN) reconsturct times

應用

  • 堆積排序法(Heap Sort)
  • 普林演算法(Prim’s Algorithm)
  • 戴克斯特拉演算法(Dijkstra’s Algorithm)

堆積排序 Heapsort

  • 是一種比較排序法(Comparision Sort)
  • 主要優勢在於能確保O(NlogN)的時間複雜度
  • 屬於原地演算法(in-place algorithm),缺點是每次排序都須重建heap——增加O(N)時間複雜度
  • 在一維陣列起始位置為0的indexing:

image

用Python實作Max Binary Heap,請參考gist

python build-in heapq

關聯陣列/對映/字典 Associative Array/ Map/ Dictionary

  • 鍵、值的配對(key-value)
  • 相較於樹狀資料結構,劣勢在於排序困難
  • 主要操作:
    • 新增、刪除、修改值
    • 搜尋已知的鍵

image

hash function

  • division method: modulo operator

h(x) = n % m

n: number of keys, m: number of buckets

Collision

當多個key存取同一個bucket(slot),解決collision會導致時間複雜度提高

解法:

  • chaining: 在同一個slot用linked list存放多個關聯
  • open addressing: 分配另一個空的slot
    • linear probing: 線性探測
    • quadratic probing: 二次方探測,如1, 2, 4, 8…
    • rehashing

Dynamic resizing

load factor(佔用率): n / m

  • load factor會影響到存取的效能,因此須要根據使用率動態變更陣列大小;
  • 舉例來說,Java觸發resize的時機點大約是佔用超過75%時、Python則約是66%

應用

  • 資料庫
  • Network Routing
  • Rabin-Karp演算法
  • Hashing廣泛用於資料加密

以Python實作,請參考gist

Average case Worst case
insert O(1) O(N)
delete O(1) O(N)
search O(1) O(N)

三元搜尋樹 Ternary Search Tree, TST

  • 相較其他樹狀資料結構而言,佔用記憶體空間較小
  • 只儲存string,不存NULL或其他物件
  • 父節點可以有3個子節點:left(less)middle(equal)right(greater)
  • 可以同時用來當作hashmap使用,也可以做排序
  • 效能上比hashmap更佳,在解析key時是漸進式的(如cat若root沒有c就不用繼續找了)

image

應用

  • autocompelete
  • 拼字檢查
  • 最近鄰居搜尋(Near-neighbor)
  • WWW package routing
  • 最長前綴匹配(perfix matching)
  • Google Search

以Python實作,請參考gist

互斥集 Disjoint sets / union-find data structure

  • 一堆沒有交集的集合,如10個學生分成4組
  • 主要操作: unionfindmakeSet
  • 通常以linked list或tree來實作
  • 訪問disjoint set中的任何節點都回傳同一個root value

set在union過程中會遇到不平衡的問題,有兩種最佳化方法:

  1. union by rank: 讓小的樹接到較大的樹
  2. path compression: 訪問節點時調整樹的結構,直接與root連結

應用

  • Kruskal: 檢查圖中是否有cycle

以Python實作,輸出請參考gist