[筆記] Master The Coding Interview – 1

工程師的面試中,不免俗的會遇見用各種型式來考你的演算法功力。這篇是 Udemy 上的知名課程 – Master the Coding Interview 的進修心得。目標是在這兩邊的精進後,可以自在的解決 LeetCode 上的問題。
coding interview


課程相關資訊

[連結]:https://www.udemy.com/course/master-the-coding-interview-data-structures-algorithms/

課程對應章節:22~47

請注意:本系列文章為個人對應課程的消化吸收後,所整理出來的內容。換言之,並不一定會包含全部的課程內容,也有可能會添加其他資源來說明。


內容

環境設置

為了操作上的方便,可以使用 Repl.it 或是 Glot.io 來進行操作。如果你是 JavaScript 的使用者,也可以直接使用瀏覽器的 Console 工具

背景知識

1. 怎樣的 Code 會被認為是高品質的?
Readable (閱讀性) 和 Scalable (可擴展性)。前者為讓他人容易讀懂,而後者則是跟 BigO 有關聯。當你的數量級越大時,你的程式碼能不能正常運作,還是會讓使用者等待時間過就造成錯誤。

2. BigO
複雜度的表格,可以上 Big O CheatSheet 的網站查看,下方是該網頁截圖:
Coding,codingForInterview,master the coding interview,master the coding interview udemy 當 BigO 的橫軸為項目總數(n),縱軸為操作次數。常作為代表 O(n) 為一條線型函數,操作的最大次數跟 n 有關。一般而言,我們會以 O(n) 作為標準,盡量避免產出大於 O(n) 的函式。
真實的 Big O 值,你需要一行行計算,但你當操作次數越發增加時,其函式的係數是可以被忽略的。
Big O 的值所呈現的,是代表整個函式執行最壞的情況。真實情況通常會在最好跟最壞之間。

3. 時間和空間複雜度

除了易讀之外,記憶體的使用量關乎 Space Complexity 而速度則是跟 Time Complexity 有關。理想情況下,自然是兩者都越有效率越好。

4. 空間複雜度計算
命名新變數、物件需要佔空間


小結

其實跟判斷函數極限值是相同道理的:去掉常數、次方高是主要影響者

O(1) Constant- no loops
O(log N) Logarithmic- usually searching algorithms have log n if they are sorted (Binary Search)
O(n) Linear- for loops, while loops through n items
O(n log(n)) Log Liniear- usually sorting operations
O(n^2) Quadratic-  Two nested loops
O(2^n) Exponential- recursive algorithms that solves a problem of size N
O(n!) Factorial- you are adding a loop for every element

Iterating through half a collection is still O(n)
Two separate collections: O(a * b)


相關文章

★全文分享★  [筆記] Master The Coding Interview – 16
[筆記] Master The Coding Interview – 16
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 15
[筆記] Master The Coding Interview – 15
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 14
[筆記] Master The Coding Interview – 14
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 13
[筆記] Master The Coding Interview – 13
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 12
[筆記] Master The Coding Interview – 12
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 11
[筆記] Master The Coding Interview – 11
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 10
[筆記] Master The Coding Interview – 10
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 9
[筆記] Master The Coding Interview – 9
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 8
[筆記] Master The Coding Interview – 8
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 7
[筆記] Master The Coding Interview – 7
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 6
[筆記] Master The Coding Interview – 6
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 5
[筆記] Master The Coding Interview – 5
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 4
[筆記] Master The Coding Interview – 4
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 3
[筆記] Master The Coding Interview – 3
這篇是 Udemy 上的知名課程 – Master the Coding
★全文分享★  [筆記] Master The Coding Interview – 2
[筆記] Master The Coding Interview – 2
這篇是 Udemy 上的知名課程 – Master the Coding
按讚加入粉絲團

延伸閱讀