[Data Structures]資料結構一日速成 with AlgoExpert

Published in

jimmy-wang

11 min readJun 22, 2021

The foundational knowledge you need to ace the coding interviews.

本篇記錄AlgoExpert課程Data Structures Crash Course筆記。

零、Why AlgoExpert?
一、為什麼面試中的資料結構重要?
二、衡量問題的複雜度分析(Complexity Analysis)
三、數組 Arrays
四、鏈結串列 Linked Lists
五、雜湊表 Hash Tables
六、堆疊與佇列 Stacks And Queues
七、字串 Strings
八、圖 Graphs
九、樹 Trees

零、Why AlgoExpert?

相比LeetCode, HackerRank，付費的AlgoExpert包含了基礎概念解析，也有160題經典演算法、資料結構題目可以刷，其介面如下圖，有清楚的敘述，包含Prompt、I／O、Tests區塊，題目敘述清晰、有解題答案、解題過程、編程過程與思路影片。
(購買兩門課作為一bundle約 3200台幣)

優勢

完整、入門的資料結構與演算法教學(透過影片)。
有多重解法的題目，都會附上不同解法的code。
有解題思路的題目解構、coding過程影片。
[這點大勝Leetcode, HackerRank的討論區，在討論區通常要自己梳理]
解題介面(UI)舒適，就如下圖。會有四個區塊。

一、為什麼面試中的資料結構重要?

如同各種領域中都需要基礎知識，基礎知識就如同學科中的物理、化學、數學，而成為工程師的基礎學科主要有二，其一就是演算法(algorithm)，其二則是資料結構(Data Structures)，而這些基礎學科是面試中經常被詢問的基本概念。

Coding的本質是資料處理過程。可能是發request取得資料，可能是呈現資訊到UI上，可能是API的結構建立。總的來說，所有概念的初始都源自資料的I／O。

資料在不同的情境，透過許多不一樣的格式進行運算，基本如數組(array)、列表(list)、樹狀(tree)、網絡(network)等等。

但資料如何儲存 ?

記憶體 Memory

當我們在coding時，宣告變數的過程，就是在與記憶體空間(memory slot)要求儲存空間。但記憶體的度量衡如何計算?

Bit: 0101的二元數字(binary digit)表示。
Byte: 一組8個bits組成的組合，例如01101000就是一個byte。每一個byte最大能表示的資料值有256個(2⁸, 0~255)。
Fixed-Width Integer: 32-bit integer(4 bytes), 64-bit integer(8 bytes)，鎖定變數儲存資料的長度，一旦宣告，就會依據該長度將資料儲存到記憶體中。
指標(pointer)概念如在一個slot中儲存memory address(slot的位置編號)，透過指標的概念，我們可以在記憶體中，進行更快、更複雜的運算。

二、衡量問題的複雜度分析(Complexity Analysis)

在面試過程中，我們面對的題目通常不會有單一解法，因此就需要解析不同做法的優劣勢，在此會以複雜度分析進行解析。

1. 時間複雜度 Time Complexity

演算法運算效率，需要多少時間。耗時越短越好。

2. 空間複雜度 Space Complexity

需要多少記憶體。且兩者通常都會用Big O進行表示。

Big O Notation

考量資料隨input長度變化的複雜度。

假設 a = [1,2,3]，資料長度為N=3第一種: 常數加array第一個值
output 1+1
O(1), constant第二種: 加總array數字
output 1+2+3+...(隨a長度N變化)
O(N), linear第三種: 配對array中數字
output 11 12 13 21 22 23 31 32 33
O(N^2), Quadratic

O(1)中的1代表什麼意思?
回到記憶體的概念，由於a[0]是一個固定的記憶體slot，不論在32-bit或64-bit都是相對應的概念。不去在乎要多少slot空間，例如32-bit應為O(8)，但皆用O(1)代表。

可以加三種方法加起來當作一種演算法嗎?
可以，複雜度變成O(N^2+N+1)，但表示時，我們只會以O(N^2)代表。留下隨input size加速度最快的。

排序大小由左上至左下，再由右上至右下。Source: https://www.algoexpert.io/data-structures

隨著不同的複雜度，處理時間也會呈現不同的變化，加速度也不同。
視覺畫圖如下。

Source: https://danielmiessler.com/study/big-o-notation/

有兩個變數會如何表示?
用M, N分別表示，並保留變化數度最快的。例如:
- O(M^2+N)
- O(N!+log(m))

對數 Logarithm

以下兩者相等嗎?

Yes, 相等，在左式同時取b指數，就可以轉為右式。
Coding最常被使用的b是2。(base=2)
因此log(4) = 2，log(16) = 4。

log(N)最大的好處，就是當資料長度就算翻倍(double)複雜度也只是log(N+1)。而且當input長度越長，複雜度增加的加速度越少。

什麼是O(log N)的代表演算法? Trees！尤其是balanced binary trees。

三、數組 Arrays

以[1,2,3]，資料儲存以64-bit integer為例，圖中框起來的空間就是需要的空間。藍色方框為每一個value起始位置。

A dynamic array
依據array預先分配兩倍記憶體空間。代表array可以依據長度進行變化讓insert資料更快速，使用這個方式的代表語言如Python、JavaScript。
A Static array
依據array需要的空間進行分配記憶體，如需要新增資料，會額外分配。

四、鏈結串列 Linked Lists

從左讀至右，但在記憶體空間可以跳著順序進行儲存，儲存方式為一個slot存value、一個slot存next。串列尾巴(tail)的next存指向null。

以 3 => 1 => 4 => 2 的單向鏈結串列(Singly Linked List)為例，要取得4這個值，就必須從3找到1再找到4。

Doubly Linked List

相較於Singly Linked List，更多存了prev這個property。因此儲存在記憶體的空間就會是一個數值對應三個slots，分別是value, prev, next。

五、雜湊表 Hash Tables

在Python內建的雜湊表，就是dictionary。由key-value作為一個pair組成並儲存(key-value pair)。

Hash Tables是一種可以提供快速insert、delete、search的資料結構。

六、堆疊與佇列 Stacks And Queues

就是先進先出、先進後出的概念應用。

Source: GeeksforGeeks-Queue using Stacks

堆疊 Stacks

後進先出(LIFO)，如同書本堆疊，當我們要取資料時，必會先取到最後一本堆疊上去的書。

通常透過動態數組(dynamic array)或單向鏈結串列(Singly Linked List)實踐。

佇列 Queues

先進後出(FIFO)，如同商店排隊或等候專線，會是最先進入或排隊的人，優先序在前，因此會是先進後出。

通常透過雙向鏈結串列(Doubly Linked List)實踐。

七、字串 Strings

每一個數字的字串、文字的字串都可以透過ASCII對應轉換成一組數字表示。這也代表字串是不可變的(immutable)。

字串時間複雜度範例：

string = 'this is a str.'
newString = ''for i character in string:
　　newString += character複雜度為O(n^2)，
因為從string資料取出長度為n[為O(n)的執行]，放入newString操作次數為n*O(n)，因此複雜度為複雜度為O(n^2)。