PHP - Data Structure and Algorithm

# 前言

資料結構與演算法學習筆記 T_T, 出來混, 遲早要還的…

# Questions and Answers

以下的演算法邏輯是？

• Example:

  <?php class Solution { /** * @param TreeNode $root * @param Integer $k * @return Boolean */ function findTarget($root, $k) { $result = $this->find($set, $k, $root); return $result; } private function find(&$set, $k, $root):bool { if ($root === null) { return false; } if (array_key_exists($k - $root->val, $set)) { return true; } $set[$root->val] = true; return $this->find($set, $k, $root->right) || $this->find($set, $k, $root->left); } }

• Answer:
  twoSumBST

以下的演算法題目, twoSum 的解法邏輯是？

• Example:
  Input: nums = [2,7,11,15], target = 9
  Output: [1,2]
  Output: Because nums[0] + nums[1] == 9, we return [1, 2].

• Answer:

  <?php class Solution { /** * @param Integer[] $nums * @param Integer $target * @return Integer[] */ function twoSum($nums, $target) { $map = []; for($i=0;$i<=count($nums);$i++) { $difference = $target - $nums[$i]; if (array_key_exists($difference, $map)) { return [$i, $map[$difference]]; } $map[$nums[$i]] = $i; } } }

  在 loop 過程中將 $nums key value 顛倒存成 $map = [value, key], 而只要 $target - $nums[$i] 的結果存在於 $map 的 key 中, 假設為 $difference, 則第一個 index 為 $i, 第二個為 $map[$difference]

以下的演算法題目, twoSum 的解法邏輯是？

• Example:
  Input: nums = [2,7,11,15], target = 9
  Output: [0,1]
  Output: Because nums[0] + nums[1] == 9, we return [0, 1].

• Answer:

  <?php class Solution { /** * @param Integer[] $nums * @param Integer $target * @return Integer[] */ function twoSum($nums, $target) { $map = []; for($i=0;$i<=count($nums);$i++) { $difference = $target - $nums[$i]; if (array_key_exists($difference, $map)) { return [$i, $map[$difference]]; } $map[$nums[$i]] = $i; } } }

  在 loop 過程中將 $nums key value 顛倒存成 $map = [value, key], 而只要 $target - $nums[$i] 的結果存在於 $map 的 key 中, 假設為 $difference, 則第一個 index 為 $i, 第二個為 $map[$difference]

以下的 php example code 的意思是？

• Example:

  <?php function mergeSort(array $arr): array { $len = count($arr); $mid = (int) ($len / 2); if ($len == 1) { return $arr; } $left = mergeSort(array_slice($arr, 0, $mid)); $right = mergeSort(array_slice($arr, $mid)); return merge($left, $right); } function merge(array $left, array $right): array { $combined = []; $countLeft = count($left); $countRight = count($right); $leftIndex = $rightIndex = 0; while ($leftIndex < $countLeft && $rightIndex < $countRight) { if ($left[$leftIndex] > $right[$rightIndex]) { $combined[] = $right[$rightIndex]; $rightIndex++; } else { $combined[] = $left[$leftIndex]; $leftIndex++; } } while ($leftIndex < $countLeft) { $combined[] = $left[$leftIndex]; $leftIndex++; } while ($rightIndex < $countRight) { $combined[] = $right[$rightIndex]; $rightIndex++; } return $combined; } $array = [8, 4, 1, 8, 19, 3, 5, 11, 9, 13]; $result = mergeSort($array); print_r($result);

• Answer:
  merge sort, 先使用 binary 遞迴將 array 1 分為 2, 直到一個 array 中只有一個 item, 在從終點處往回推, 使每一個 array 都是排序過的, 在排序兩個已經排序過的 array, 回推到終點時, 已完成所有的排序

B tree 通常被使用在什麼地方？

大型資料, 例如資料庫或檔案系統

AVL tree 算是哪一種 tree 的一種？

height balancing binary search tree

Binary search tree 跟 self-balanced binary search tree 的效率哪種較佳？

後者

Binary search tree 跟 self-balanced binary search tree 的差異是？

後者會自動調整, 讓自身的 height 盡可能的小

Binary tree 跟 Binary search tree 的差異是？

binary search tree 中, node 的必須以特定的方式排列儲存

演算法中, 何謂穩定排序與不穩定排序?

• 排序前 key/value 相同的 index, 在排序後的順序跟排序前一樣, 那稱為穩定排序, 如 [3, 2, 2(2), 1, 4] 排序後為 [1, 2, 2(2), 3, 4]
• 排序前 key/value 相同的 index, 在排序後的順序跟排序前不一樣, 那稱為不穩定排序, 如 [3, 2, 2(2), 1, 4] 排序後為 [1, 2(2), 2), 3, 4]

以下的 PHP Example code 的意思是？

• Example:

  <?php function insertionSort(array &$arr) { $len = count($arr); for ($i = 1; $i < $len; $i++) { $key = $arr[$i]; $j = $i - 1; while($j >= 0 && $arr[$j] > $key) { $arr[$j+1] = $arr[$j]; $j--; } $arr[$j+1] = $key; } } $arr = [20, 45, 93, 67, 10, 97, 52, 88, 33, 92]; insertionSort($arr); echo implode(",", $arr);

• Answer:

  <?php // 使用 PHP Reference, 因此會直接更動外面的 $arr 內容 function insertionSort(array &$arr) { $len = count($arr); // 外層迴圈決定了 "待比較" index, 1-9 都會依次被比較 for ($i = 1; $i < $len; $i++) { // $key 即是每輪的主要 "待比較" 數 $key = $arr[$i]; $j = $i - 1; // 內層 while 迴圈決定了 "待比較數" 的確切位置 // 會將 $key 與往前的 index 依序比較, 若 $key 較小, 則會將該 index 往後挪 // 依序往前比較, 直到 $key 不小於該 index, 這時 $key 會取代該 index 的後一個 index // 因為後一個 index 在上一輪已經被往後挪了 while($j >= 0 && $arr[$j] > $key) { $arr[$j+1] = $arr[$j]; $j--; } $arr[$j+1] = $key; } } $arr = [20, 45, 93, 67, 10, 97, 52, 88, 33, 92]; insertionSort($arr); echo implode(",", $arr);

以下的 Example code 的邏輯是？

• Example:

  <?php function selectionSort(array $arr): array { $len = count($arr); for ($i = 0; $i < $len; $i++) { $min = $i; for ($j = $i+1; $j < $len; $j++) { if ($arr[$j] < $arr[$min]) { $min = $j; } } if ($min != $i) { $tmp = $arr[$i]; $arr[$i] = $arr[$min]; $arr[$min] = $tmp; } } return $arr; }

• Answer:

  <?php function selectionSort(array $arr): array { $len = count($arr); // $i 從 0 開始跑, 亦即從 index 0 開始跑到最後一個 index for ($i = 0; $i < $len; $i++) { // 這裡定下 $min 預設的位置, 以 first loop 來說, $i 為 0, 目標為將最小值移動到 $i 即 index 0 的位置 // 以 second loop 來說, $i = 1, 目標為將最小值移動到 index 1 的位置 $min = $i; // $j = $i+1, 所以以 first loop first step 來說, 會是 index 1 跟 index 0 做比較, 而 second loop first step 就會是 // index 2 跟 index 1 做比較, 由於 index 0 已經被賦予上一輪中取得的最小值, 所以在 second loop 開始不需參與比較 for ($j = $i+1; $j < $len; $j++) { // 以 first loop first step 來說, 如果 index 1 < index 0, 那 $min 會記下 index 1 的位置, 表示目前取得的最小值位置在 index 1 // 繼續往下跑, 會依序把每一個 index 都去跟 $min 做比較, 而每個 step 中, 如果當前 index 比 $min 還小, 會即時更新 $min 的值 // 即是即時更新最小值的 index 位置 if ($arr[$j] < $arr[$min]) { $min = $j; } } // 當上面的 loop 結束後, 如果最小值的位置, 跟 $i 不同, 那就將上面得到的此輪最小值移動到 $i 的位置 // 以 first loop 來說, 最小值會移動到 index 0 的位置, 而隨著 loop 往後跑, 每一輪的最小值都會移動到 $i 的位置 // first loop 移動到 index 0, second loop 移動到 index 1, 以此類推 if ($min != $i) { $tmp = $arr[$i]; $arr[$i] = $arr[$min]; $arr[$min] = $tmp; } } return $arr; }

以下的 Example code 的邏輯是？

• Example:

  <?php function bubbleSort(array $arr): array { $len = count($arr); $count = 0; $bound = $len-1; for ($i = 0; $i < $len; $i++) { $swapped = FALSE; $newBound = 0; for ($j = 0; $j < $bound; $j++) { $count++; if ($arr[$j] > $arr[$j + 1]) { $tmp = $arr[$j + 1]; $arr[$j + 1] = $arr[$j]; $arr[$j] = $tmp; $swapped = TRUE; $newBound = $j; } } $bound = $newBound; if(! $swapped) break; } echo $count."\n"; return $arr; }

• Answer:

  <?php function bubbleSort(array $arr): array { $len = count($arr); $count = 0; $bound = $len-1; for ($i = 0; $i < $len; $i++) { $swapped = FALSE; $newBound = 0; // 依照 loop 邏輯, 每一輪 $i 都會 iterate array 的每一個 index // 並把越大的 index value 往後移動, 換言之, 如 array 有 10 個 index // 但第一輪只需將第 6 個跟第 7 個對調, 然後後面的都不需要調動 // 那跑第二輪 $i 時, 就不需要再比較 index 6 之後的 index 了 // 所以 $bound 會在每一輪 $i 結束後更新 for ($j = 0; $j < $bound; $j++) { $count++; if ($arr[$j] > $arr[$j + 1]) { $tmp = $arr[$j + 1]; $arr[$j + 1] = $arr[$j]; $arr[$j] = $tmp; $swapped = TRUE; // 這裏更新 $newBound, $newBound 會儲存最後一次有調整的 index $newBound = $j; } } // 將 $bound value 替換為 $newBound, 下一輪的 $i 就不需要去比較 $bound 之後的 index 了 $bound = $newBound; if(! $swapped) break; } echo $count."\n"; return $arr; }

以下的 Example code 的邏輯是？

• Example:

  <?php function bubbleSort(array $arr): array { $len = count($arr); for ($i = 0; $i < $len; $i++) { $swapped = FALSE; for ($j = 0; $j < $len - $i - 1; $j++) { if ($arr[$j] > $arr[$j + 1]) { $tmp = $arr[$j + 1]; $arr[$j + 1] = $arr[$j]; $arr[$j] = $tmp; $swapped = TRUE; } } if(! $swapped) break; } return $arr;

• Answer:

  <?php function bubbleSort(array $arr): array { $len = count($arr); // 這邊 i 應為 $len - 1 即可, 但並不影響到 Big O for ($i = 0; $i < $len; $i++) { $swapped = FALSE; // $i 每跑完一個 loop, 代表該 array 中最大的 index value 會被排到最後一個 index // 換句話說, 當第一輪跑完, 第二輪就不需要再比較倒數第二個 index 跟最後一個 index 了 // 如下示意圖 for ($j = 0; $j < $len - $i - 1; $j++) { if ($arr[$j] > $arr[$j + 1]) { $tmp = $arr[$j + 1]; $arr[$j + 1] = $arr[$j]; $arr[$j] = $tmp; $swapped = TRUE; } } if(! $swapped) break; } return $arr;

  

以下的 Example code 的邏輯是？

• Example:

  <?php function bubbleSort(array $arr): array { $len = count($arr); for ($i = 0; $i < $len; $i++) { $swapped = FALSE; for ($j = 0; $j < $len - 1; $j++) { if ($arr[$j] > $arr[$j + 1]) { $tmp = $arr[$j + 1]; $arr[$j + 1] = $arr[$j]; $arr[$j] = $tmp; $swapped = TRUE; } } if(! $swapped) break; } return $arr; }

• Answer:

  <?php function bubbleSort(array $arr): array { $len = count($arr); // 這邊 i 應為 $len - 1 即可, 但並不影響到 Big O for ($i = 0; $i < $len; $i++) { // 定義 $swapped 為 false, 預計每個 loop 至少會調整順序一次, 如果都沒有調整到, 代表 // 此 array 已經調整完畢, 儘管 $i 還沒跑完也不需要再往下跑了 $swapped = FALSE; // $j = 0, 代表從 array index 0 開始跑 // $j < $len - 1, 所以會跑到倒數第二個 index for ($j = 0; $j < $len - 1; $j++) { // 比較當前 index 以及下一個 index, 這也是為何上一行只需要跑到倒數第二個 index // 如果當前較 index value 下一個 index value 大, 表示順序需要調整 if ($arr[$j] > $arr[$j + 1]) { // 先將下一個 index value 取出並丟到 $tmp $tmp = $arr[$j + 1]; // 將下一個 index value 替換為當前 index value $arr[$j + 1] = $arr[$j]; // 將當前 index value 替換為 $tmp $arr[$j] = $tmp; // swapped 為 true, 表示此輪依然有調整順序 $swapped = TRUE; } } // 如果跑到這 $swapped 為 false, 代表 $j 從頭跑到尾都沒有調整過順序, 那 // 不管 $i 跑到第幾輪 loop, 後續的就不用再跑了 if(! $swapped) break; } return $arr; }

以下的 Example code 的邏輯是？

• Example:

  <?php function bubbleSort(array $arr): array { $len = count($arr); for ($i = 0; $i < $len; $i++) { for ($j = 0; $j < $len - 1; $j++) { if ($arr[$j] > $arr[$j + 1]) { $tmp = $arr[$j + 1]; $arr[$j + 1] = $arr[$j]; $arr[$j] = $tmp; } } } return $arr; }

• Answer:

  <?php function bubbleSort(array $arr): array { // 求得 array length $len = count($arr); // i 從 0 開始, 若 $len = 10, 那就需要跑 9 次, 由於 $1 從 0 開始, 所以 $i < $len - 1 即可 for ($i = 0; $i < $len - 1; $i++) { // 假設 $len = 10, 那 index 會是 0 - 9, 由於下面的 code 會是 $j 比較 $j+1 // 所以 $j 取到 index 8 即可 for ($j = 0; $j < $len - 1; $j++) { // $j 與 $j+1 比較, 也就是當前 index 與下一個 index 相比 // 如果當前的比較大, 即符合條件 if ($arr[$j] > $arr[$j + 1]) { // 由於當前 index $j 較大, 所以 // 1. 先取得 index $j+1 的值, 放到 variable $tmp // 2. 將 index $j+1 的 value 替換成 value 較大的當前 $j index // 3. 最後再將當前 index $j 替換為 variable $tmp $tmp = $arr[$j + 1]; $arr[$j + 1] = $arr[$j]; $arr[$j] = $tmp; } } } return $arr; }

以下的 Example code 的邏輯是？

• Example:

  <?php function insert(int $data) { if ($this->isEmpty()) { $node = new Node($data); $this->root = $node; return $node; } $node = $this->root; while ($node) { if ($data > $node->data) { if ($node->right) { $node = $node->right; } else { $node->right = new Node($data, $node); $node = $node->right; break; } } elseif ($data < $node->data) { if ($node->left) { $node = $node->left; } else { $node->left = new Node($data, $node); $node = $node->left; break; } } else { break; } } return $node; }

• Answer:

  <?php function insert(int $data) { if ($this->isEmpty()) { $node = new Node($data); $this->root = $node; return $node; } $node = $this->root; // 如果有 $node 的情況下 while ($node) { // 如果帶入的 $data 比當前 node->data 還大的話 if ($data > $node->data) { // 如果當前 node 有 right child 的話, 就持續往下找, 並跟下一個 node 比較 if ($node->right) { $node = $node->right; } // 如果當前 node 已經沒有 right child, 那就使用帶入的 data 新增一個當前 node的 // right child, 已經成功找到位置並且新增了, 可以 break 離開 loop 了 else { $node->right = new Node($data, $node); $node = $node->right; break; } } // 如果帶入的 $data 比當前 node->data 還小的話, 邏輯同上 elseif ($data < $node->data) { if ($node->left) { $node = $node->left; } else { $node->left = new Node($data, $node); $node = $node->left; break; } } // 如果帶入的 $data 跟當前 node->data 一樣的話 else { break; } } return $node; }

以下的 Example code 的邏輯是？

• Example:

  <?php public function delete() { $node = $this; if (!$node->left && !$node->right) { if ($node->parent->left === $node) { $node->parent->left = NULL; } else { $node->parent->right = NULL; } } elseif ($node->left && $node->right) { $successor = $node->successor(); $node->data = $successor->data; $successor->delete(); } elseif ($node->left) { if ($node->parent->left === $node) { $node->parent->left = $node->left; $node->left->parent = $node->parent->left; } else { $node->parent->right = $node->left; $node->left->parent = $node->parent->right; } $node->left = NULL; } elseif ($node->right) { if ($node->parent->left === $node) { $node->parent->left = $node->right; $node->right->parent = $node->parent->left; } else { $node->parent->right = $node->right; $node->right->parent = $node->parent->right; } $node->right = NULL; } }

• Answer:

  <?php public function delete() { $node = $this; // 若該 node 下面沒有任何 child node if (!$node->left && !$node->right) { // 若該 node 是其 parent 的 left child node if ($node->parent->left === $node) { // 斷掉 parent node 的 connection, 所以將不再能從 tree 存取該 node // 因為該 node 下面沒有任何 child node, 所以這是最簡單的情況 // 直接斷掉該 node 與其 parent 的 connection 即可 $node->parent->left = NULL; } else { // 同上 $node->parent->right = NULL; } // 若該 node 下面有 left child node 也有 right child node } elseif ($node->left && $node->right) { // $successor 為該 node 的下一個最大值, 依照 BST 的規則, 該 $successor 的位置 // 會是該 node 的 right child node 往下開始的最左最底 $successor = $node->successor(); // 將該 node 的 data 替換成 $successor->data, 剩餘的 $left 以及 $right 不需更改 // 如上所敘, $successor 為大於該 node 的下一個值, 也就是說, 若依照大小排列, 該 node 的 // 下一個就是 $successor // 也就是說, $successor 會比該 node 的 left child node 還大, 並且比 right child node 還小 $node->data = $successor->data; // 這邊是遞迴, 由於 successor 已經是某 node 的最左端, 不會再有 left child, 因此會 // 依照是否有 right child node 若兩者皆無的狀態進下一次 delete method 的判斷 $successor->delete(); // 若該 node 下面只有 left child node } elseif ($node->left) { // 如果該 node 是其 parent 的 left child 的話 if ($node->parent->left === $node) { // 將其 parent 的 left 替換成該 node 的 left, 所以從其 parent 不再可以 connect 到該 node $node->parent->left = $node->left; // 同樣的, 將該 node 的 left chiid 的 parent property 取代為 $node->parent $node->left->parent = $node->parent; // 如果該 node 是其 parent 的 right child 的話 } else { // 基本上邏輯同上 $node->parent->right = $node->left; $node->left->parent = $node->parent; } $node->left = NULL; // 若該 node 下面只有 right child node } elseif ($node->right) { // 邏輯同上 if ($node->parent->left === $node) { $node->parent->left = $node->right; $node->right->parent = $node->parent; } else { $node->parent->right = $node->right; $node->right->parent = $node->parent; } $node->right = NULL; } }

以下的 Example code 的邏輯是？

• Example:

  <?php class BST { public $root = NULL; public function __construct(int $data) { $this->root = new Node($data); } public function isEmpty(): bool { return $this->root === NULL; } public function insert(int $data) { if($this->isEmpty()) { $node = new Node($data); $this->root = $node; return $node; } $node = $this->root; while($node) { if($data > $node->data) { if($node->right) { $node = $node->right; } else { $node->right = new Node($data); $node = $node->right; break; } } elseif($data < $node->data) { if($node->left) { $node = $node->left; } else { $node->left = new Node($data); $node = $node->left; break; } } else { break; } } return $node; } public function traverse(Node $node) { if ($node) { if ($node->left) $this->traverse($node->left); echo $node->data . "\n"; if ($node->right) $this->traverse($node->right); } } }

• Answer:

  <?php class BST { public $root = NULL; public function __construct(int $data) { $this->root = new Node($data); } public function isEmpty(): bool { return $this->root === NULL; } public function insert(int $data) { // 若該 tree 為 empty, assign root 為該 node if($this->isEmpty()) { $node = new Node($data); $this->root = $node; return $node; } $node = $this->root; while($node) { // 如果帶入的 data 比當前 node 大, 進入判斷 if($data > $node->data) { // 如果當前 node 底下有 right child node if($node->right) { // 將當前 node 替換為其 child right node // 繼續 loop 看 child right node 會進哪一個判斷 $node = $node->right; // 如果當前 node 底下沒有 right child node } else { // 將 new node assign 給 right child node $node->right = new Node($data); $node = $node->right; // 結束 loop break; } // 如果帶入的 data 比當前 node 小, 進入判斷 } elseif($data < $node->data) { // 如果當前 node 底下有 left child node if($node->left) { // 將當前 node 替換為其 child left node // 繼續 loop 看 child left node 會進哪一個判斷 $node = $node->left; // 如果當前 node 底下沒有 left child node } else { // 將 new node assign 給 left child node $node->left = new Node($data); $node = $node->left; // 結束 loop break; } // 如果帶入的 data 不大於也不小於當前 node, 那有可能是等於當前 node, 直接結束迴圈 } else { break; } } return $node; } public function traverse(Node $node) { // 如果有帶入 node, 進判斷 if ($node) { // 如果該 node 有 left child node if ($node->left) // 遞迴 traverse function, argument 為當前 node 的 left child node $this->traverse($node->left); // 印出當前 node 的 data echo $node->data . "\n"; if ($node->right) // 遞迴 traverse function, argument 為當前 node 的 right child node $this->traverse($node->right); } } }

以下的 Example code 的邏輯是？

• Example:

  <?php class Node { public $data; public $left; public $right; public function __construct(int $data = NULL) { $this->data = $data; $this->left = NULL; $this->right = NULL; } public function min() { $node = $this; while($node->left) { $node = $node->left; } return $node; } public function max() { $node = $this; while($node->right) { $node = $node->right; } return $node; } public function successor() { $node = $this; if($node->right) return $node->right->min(); else return NULL; } public function predecessor() { $node = $this; if($node->left) return $node->left->max(); else return NULL; } }

• Answer:

  <?php class Node { public $data; public $left; public $right; public function __construct(int $data = NULL) { $this->data = $data; $this->left = NULL; $this->right = NULL; } public function min() { $node = $this; // BST 的規則中, 每個 node 的兩個 children node, 左邊的小於 parent, 右邊的大於 parent // 所以 min 的是最底層的最左 while($node->left) { $node = $node->left; } return $node; } public function max() { $node = $this; // BST 的規則中, 每個 node 的兩個 children node, 左邊的小於 parent, 右邊的大於 parent // 所以 min 的是最底層的最右 while($node->right) { $node = $node->right; } return $node; } public function successor() { $node = $this; // BST 的規則中, 每個 node 的兩個 children node, 左邊的小於 parent, 右邊的大於 parent // 所以該 node 的 successor 為右邊 child node 下的最小值, // 也就是右邊 child node 下的最左最底那個 node if($node->right) return $node->right->min(); else return NULL; } public function predecessor() { $node = $this; // BST 的規則中, 每個 node 的兩個 children node, 左邊的小於 parent, 右邊的大於 parent // 所以該 node 的 presuccessor 為左邊 child node 下的最大值, // 也就是左邊 child node 下的最右最底那個 node if($node->left) return $node->left->max(); else return NULL; } }

以下的 Example code 的邏輯是？

• Example:

  <?php class BST { public $root = NULL; public function __construct(int $data) { $this->root = new Node($data); } public function isEmpty(): bool { return $this->root === NULL; } public function insert(int $data) { if($this->isEmpty()) { $node = new Node($data); $this->root = $node; return $node; } $node = $this->root; while($node) { if($data > $node->data) { if($node->right) { $node = $node->right; } else { $node->right = new Node($data); $node = $node->right; break; } } elseif($data < $node->data) { if($node->left) { $node = $node->left; } else { $node->left = new Node($data); $node = $node->left; break; } } else { break; } } return $node; }

• Answer:
  PHP code implement BST structure

以下的 Example code 的邏輯是？

• Example:

  <?php class BinaryTree { public $nodes = []; public function __construct(Array $nodes) { $this->nodes = $nodes; } public function traverse(int $num = 0, int $level = 0) { if (isset($this->nodes[$num])) { echo str_repeat("-", $level); echo $this->nodes[$num] . "\n"; $this->traverse(2 * $num + 1, $level+1); $this->traverse(2 * ($num + 1), $level+1); } } }

• Answer:
  利用 PHP array implement Binary Tree

以下的 Example code 的邏輯是？

• Example:

  <?php class BinaryNode { public $data; public $left; public $right; public function __construct(string $data = NULL) { $this->data = $data; $this->left = NULL; $this->right = NULL; } public function addChildren(BinaryNode $left, BinaryNode $right) { $this->left = $left; $this->right = $right; } } class BinaryTree { public $root = NULL; public function __construct(BinaryNode $node) { $this->root = $node; } public function traverse(BinaryNode $node, int $level = 0) { if ($node) { echo str_repeat("-", $level); echo $node->data . "\n"; if ($node->left) $this->traverse($node->left, $level + 1); if ($node->right) $this->traverse($node->right, $level + 1); } } }

• Answer:
  implement tree data structure

Data Structure 中, N-ary Tree 的 node 可以有幾個 children?

N 個

Data Structure 中, B-tree 跟一般的 BST 有什麼差異？

B-tree 的 child node 沒有限制, BST 只可有兩個

以下的 AVL tree 圖片中, 規則是？

• Example:
  
• Answer:
  每一個 node 的 subtree 的 height 最大容許值 = 1
  拿 J 來說, 其 subtree P 線的 height 為 4, 而另一個 subtree F 的 height 為 3, 所以 3 - 2 = 1
  拿 F 來說, 其 subtree D 線的 height 為 2, 而 G 線則為 1, 所以 0 - 1 = -1

以下的圖片中, 哪一個是 height-balanced tree?

• Example:
  
• Answer:
  右邊

以下的圖片中, H 的 depth 是多少？

• Example:
  
• Answer:
  2, 與 root node 之間的 edges 數量

以下的圖片中, height of tree 是多少？

• Example:
  
• Answer:
  root node 的高度, 此例中, 為 3

以下的圖片中, B 的 level 為多少？

• Example:
  
• Answer:
  B 的 level 為 1
  A = 0
  B, C, D 為 1
  依此往下類推

以下的圖片中, B 的 height of node 為多少？

• Example:
  
• Answer:
  2
  B 與其最底層 Descendent 之間相隔的 edges 數量

以下的圖片中, A 的 degree 為多少？

• Example:
  
• Answer:
  3
  child node 的數量

以下的圖片中, M 的 Ancestors 是哪些 node？

• Example:
  
• Answer:
  H, G, F, C, A

以下的圖片中, C 的 Descendents 有哪些 node？

• Example:
  
• Answer:
  F, G, H, M

以下程式碼的邏輯是？

• Example:

  <?php class listnode { public $data = null; public $next = null; public $prev = null; public function __construct(string $data = null) { $this->data = $data; } } class doublylinkedlist { private $_firstnode = null; private $_lastnode = null; private $_totalnode = 0; public function delete(string $query = null) { if ($this->_firstNode) { $previous = null; $currentNode = $this->_firstNode; while ($currentNode !== null) { if ($currentNode->data === $query) { if ($currentNode->next === null) { $previous->next = null; } else { $previous->next = $currentNode->next; $currentNode->next->prev = $previous; } $this->_totalNode--; break; } $previous = $currentNode; $currentNode = $currentNode->next; } } } }

• Answer:

  <?php class doublylinkedlist { private $_firstnode = null; private $_lastnode = null; private $_totalnode = 0; public function delete(string $query = null) { // 如果非為空 if ($this->_firstNode) { $previous = null; $currentNode = $this->_firstNode; while ($currentNode !== null) { // 如果找到了 if ($currentNode->data === $query) { // 如果該 node 是最後一個 if ($currentNode->next === null) { $previous->next = null; } else { // 這樣等於不指向 currentNode 了 $previous->next = $currentNode->next; // 同上 $currentNode->next->prev = $previous; } $this->_totalNode--; break; } $previous = $currentNode; $currentNode = $currentNode->next; } } } }

• 以下程式碼的邏輯是？
  • Example:

    <?php class listnode { public $data = null; public $next = null; public $prev = null; public function __construct(string $data = null) { $this->data = $data; } } class doublylinkedlist { private $_firstnode = null; private $_lastnode = null; private $_totalnode = 0; public function deleteLast() { if ($this->_lastNode !== null) { $currentNode = $this->_lastNode; if ($currentNode->prev === null) { $this->_firstNode = null; $this->_lastNode = null; } else { $previousNode = $currentNode->prev; $this->_lastNode = $previousNode; $previousNode->next = null; $this->_totalNode--; return true; } } return false; } }

  • Answer:

    <?php class doublylinkedlist { private $_firstnode = null; private $_lastnode = null; private $_totalnode = 0; public function deleteLast() { // 如果不是空的 list if ($this->_lastNode !== null) { $currentNode = $this->_lastNode; // 如果只有一個 node if ($currentNode->prev === null) { // 將 firstNode 以及 lastNode 都去掉 $this->_firstNode = null; $this->_lastNode = null; // 如果不是只有一個 node } else { // 取得 previousNode $previousNode = $currentNode->prev; // 更新 lastNode $this->_lastNode = $previousNode; // 更新 lastNode property $previousNode->next = null; $this->_totalNode--; return true; } } return false; } }

• 以下程式碼的邏輯是？
  • Example:

    <?php class listnode { public $data = null; public $next = null; public $prev = null; public function __construct(string $data = null) { $this->data = $data; } } class doublylinkedlist { private $_firstnode = null; private $_lastnode = null; private $_totalnode = 0; public function deleteFirst() { if ($this->_firstNode !== null) { if ($this->_firstNode->next !== null) { $this->_firstNode = $this->_firstNode->next; $this->_firstNode->prev = null; } else { $this->_firstNode = null; } $this->_totalNode--; return true; } return false; } }

  • Answer:

    <?php class doublylinkedlist { private $_firstnode = null; private $_lastnode = null; private $_totalnode = 0; public function deleteFirst() { // 如果 list 非為空 if ($this->_firstNode !== null) { // 如果這不是唯一一個 node if ($this->_firstNode->next !== null) { // firstNode 等於下一個, 所以原本的 firstnode delete 掉了 $this->_firstNode = $this->_firstNode->next; // 新的 firstNode 的 prev 為 null $this->_firstNode->prev = null; } else { // 如果是唯一 node, 直接去掉即可 $this->_firstNode = null; } $this->_totalNode--; return true; } return false; } }

• 以下程式碼的邏輯是？
  • Example:

    <?php class listnode { public $data = null; public $next = null; public $prev = null; public function __construct(string $data = null) { $this->data = $data; } } class doublylinkedlist { private $_firstnode = null; private $_lastnode = null; private $_totalnode = 0; public function insertBefore( string $data = null, string $query = null ) { $newNode = new ListNode($data); if ($this->_firstNode) { $previous = null; $currentNode = $this->_firstNode; while ($currentNode !== null) { if ($currentNode->data === $query) { $newNode->next = $currentNode; $currentNode->prev = $newNode; $previous->next = $newNode; $newNode->prev = $previous; $this->_totalNode++; break; } $previous = $currentNode; $currentNode = $currentNode->next; } } } }

  • Answer:

    <?php class doublylinkedlist { private $_firstnode = null; private $_lastnode = null; private $_totalnode = 0; public function insertBefore( string $data = null, string $query = null ) { $newNode = new ListNode($data); // 如果非為空 if ($this->_firstNode) { $previous = null; $currentNode = $this->_firstNode; // 如果該 node 非為該 list 中的最後一個 node, 持續 loop while ($currentNode !== null) { // 找到 specific node if ($currentNode->data === $query) { // newNode 的 next 為當前的 currentNode $newNode->next = $currentNode; // 當前 currentNode 的 prev 為帶入的 newNode $currentNode->prev = $newNode; // 若找到的 node 為第一個, previous 為 null $previous->next = $newNode; // $previous 為 insert 進去的 node 的 prev 指向, 呈上, 若 found node 為第一個, 則 prev 為 newNode 自己 $newNode->prev = $previous; $this->_totalNode++; break; } // 若沒找到, 則 previous 為上一個 node $previous = $currentNode; // 繼續找下一個 $currentNode = $currentNode->next; } } } }

• 以下程式碼的邏輯是？
  • Example:

    <?php class listnode { public $data = null; public $next = null; public $prev = null; public function __construct(string $data = null) { $this->data = $data; } } class doublylinkedlist { private $_firstnode = null; private $_lastnode = null; private $_totalnode = 0; public function insertAtLast(string $data = null) { $newNode = new ListNode($data); if ($this->_firstNode === null) { $this->_firstNode = &$newNode; $this->_lastNode = $newNode; } else { $currentNode = $this->_lastNode; $currentNode->next = $newNode; $newNode->prev = $currentNode; $this->_lastNode = $newNode; } $this->_totalNode++; return true; } }

  • Answer:

    <?php class doublylinkedlist { private $_firstnode = null; private $_lastnode = null; private $_totalnode = 0; public function insertAtLast(string $data = null) { $newNode = new ListNode($data); // 如果為空, 則將 newNode 設為 firstNode 以及 lastNode if ($this->_firstNode === null) { $this->_firstNode = &$newNode; $this->_lastNode = $newNode; // 如果不為空 } else { // 先取得目前的 lastnode $currentNode = $this->_lastNode; // 將目前的 lastnode 的 next 指向 newnode $currentNode->next = $newNode; // 將 newnode 的 prev 指向目前的 lastnode $newNode->prev = $currentNode; // 將新的 lastnode 指向 newnode $this->_lastNode = $newNode; } $this->_totalNode++; return true; } }

• 以下程式碼的邏輯是？
  • Example:

    <?php class listnode { public $data = null; public $next = null; public $prev = null; public function __construct(string $data = null) { $this->data = $data; } } class doublylinkedlist { private $_firstnode = null; private $_lastnode = null; private $_totalnode = 0; public function insertatfirst(string $data = null) { $newnode = new listnode($data); if ($this->_firstnode === null) { $this->_firstnode = &$newnode; $this->_lastnode = $newnode; } else { $currentfirstnode = $this->_firstnode; $this->_firstnode = &$newnode; $newnode->next = $currentfirstnode; $currentfirstnode->prev = $newnode; } $this->_totalnode++; return true; } }

  • Answer:

    <?php class doublylinkedlist { private $_firstnode = null; private $_lastnode = null; private $_totalnode = 0; public function insertatfirst(string $data = null) { $newnode = new listnode($data); // 如果為空 if ($this->_firstnode === null) { $this->_firstnode = &$newnode; $this->_lastnode = $newnode; // 如果非為空 } else { // 先取出 firstNode 並設為 $currentFirstNode $currentfirstnode = $this->_firstnode; // 將 new node 設為 firstNode $this->_firstnode = &$newnode; // new node 的 next 為原本的 first node, 因為 newNode 與 firstNode 已綁定, 這邊也會同時修改到 firstNode $newnode->next = $currentfirstnode; // 將原本的 firstNode 的 prev 設為 newNode $currentfirstnode->prev = $newnode; } $this->_totalnode++; return true; } }

• 以下程式碼的邏輯是？
  • Example:

    <?php class ListNode { public $data = null; public $next = null; public function __construct(string $data = null) { $this->data = $data; } } class CircularLinkedList { private $_firstNode = null; private $_totalNode = 0; public function insertAtEnd(string $data = null) { $newNode = new ListNode($data); if ($this->_firstNode === null) { $this->_firstNode = &$newNode; } else { $currentNode = $this->_firstNode; while ($currentNode->next !== $this->_firstNode) { $currentNode = $currentNode->next; } $currentNode->next = $newNode; } $newNode->next = $this->_firstNode; $this->_totalNode++; return true; } }

  • Answer:

    <?php class CircularLinkedList { private $_firstNode = null; private $_totalNode = 0; public function insertAtEnd(string $data = null) { $newNode = new ListNode($data); // 如果 list 為空 if ($this->_firstNode === null) { $this->_firstNode = &$newNode; // 如果 list 不為空 } else { $currentNode = $this->_firstNode; // 一直往下找, 只要 $currentNode->next 不等於 $currentNode 自己, // 如果 $currentNode->next 等於 $currentNode 自己, 那表示找到最後一個了 while ($currentNode->next !== $this->_firstNode) { $currentNode = $currentNode->next; } // 將最後一個 node->next 等於 $newNode, 相當於原本的 next 是自己, 現在變成 $newNode $currentNode->next = $newNode; } // 如果 $newNode 為第一個 node, $newNode->next 會等於 $newNode 自己, // 所以會是一個 object 的 next property 是 object 自己, 可參照下圖 // 如果 $newNode 不是此 list 的第一個 node, 那 $newNode 相當於最後一個 node, // 將其 next 指向第一個 node, 完成 circular $newNode->next = $this->_firstNode; $this->_totalNode++; return true; } }

  • 圖片
    

• 以下程式碼的邏輯是？
  • Example:

    <?php class ListNode { public $data = null; public $next = null; public function __construct(string $data = null) { $this->data = $data; } } class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function getNthNode(int $n = 0) { $count = 1; if ($this->_firstNode !== null) { $currentNode = $this->_firstNode; while ($currentNode !== null) { if ($count === $n) { return $currentNode; } $count++; $currentNode = $currentNode->next; } } } }

  • Answer:

    <?php class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function getNthNode(int $n = 0) { $count = 1; // 若非為空 if ($this->_firstNode !== null) { // 取得 $currentNode $currentNode = $this->_firstNode; // loop 到後最一個 node while ($currentNode !== null) { // 如果找到了 if ($count === $n) { return $currentNode; } $count++; // 繼續往下找 $currentNode = $currentNode->next; } } } }

• 以下程式碼的邏輯是？
  • Example:

    <?php class ListNode { public $data = null; public $next = null; public function __construct(string $data = null) { $this->data = $data; } } class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function reverse() { if ($this->_firstNode !== null) { if ($this->_firstNode->next !== null) { $reversedList = null; $next = null; $currentNode = $this->_firstNode; while ($currentNode !== null) { $next = $currentNode->next; $currentNode->next = $reversedList; $reversedList = $currentNode; $currentNode = $next; } $this->_firstNode = $reversedList; } } } }

  • Answer:

    <?php class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function reverse() { // 如果非為空 if ($this->_firstNode !== null) { // 如果此 list 非只有一個 node if ($this->_firstNode->next !== null) { $reversedList = null; $next = null; $currentNode = $this->_firstNode; // loop 所有 node while ($currentNode !== null) { // 這邊先取得 $next, loop 最後會用到 $next = $currentNode->next; // 將 $currentNode 的 next property 設為 $reversedList $currentNode->next = $reversedList; // 此時因為上面的 $currentNode 已經跟 $this->_firstNode 不同了, // 此時將 $reversedList 指向 $currentNode, 在第一輪, // $reversedList 的預設值為 null, 因此 $currentNode->next // 會是 null, 在第二輪, $reversedList 已經變成上一輪的 // $currentNode, 其 next 為 null, 所以上一行會變成是 // $currentNode->next = 上一輪的 $currentNode, // 而這一行會取得這這一個 linkedList, 讓 $revsersedList 指向它, // 所以在每一輪, reversedList 會變成一個 object, 不斷地指向上一個 node $reversedList = $currentNode; $currentNode = $next; } // 最後, 將 $this->_firstNode 指向 $reversedList $this->_firstNode = $reversedList; } } } }

• 以下程式碼的邏輯是？
  • Example:

    <?php class ListNode { public $data = null; public $next = null; public function __construct(string $data = null) { $this->data = $data; } } class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function delete(string $query = null) { if ($this->_firstNode) { $previous = null; $currentNode = $this->_firstNode; while ($currentNode !== null) { if ($currentNode->data === $query) { if ($currentNode->next === null) { $previous->next = null; } else { $previous->next = $currentNode->next; } $this->_totalNode--; break; } $previous = $currentNode; $currentNode = $currentNode->next; } } } }

  • Answer:

    <?php class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function delete(string $query = null) { // 如果非為空 if ($this->_firstNode) { $previous = null; $currentNode = $this->_firstNode; // 會 loop 到最後一個 while ($currentNode !== null) { // 如果找到搜尋的 node if ($currentNode->data === $query) { // 如果此 node 已是最後一個 if ($currentNode->next === null) { // 變更 reference 的 property, 他會變更 $this->_firstNode 中的搜尋到的那一個 node 的 property, 所以會影響到 $this->_firstNode 的值 $previous->next = null; // 若不是最後一個 } else { // 這邊等於是把 currentNode 拿掉, 邏輯上是去變更 $previous (也就是 $currentNode 的上一個) 的 next property, 因此此 object 會變更, 連帶 $this->_firstNode 中也有此 object, 因此也會變更 $previous->next = $currentNode->next; } $this->_totalNode--; break; } // 即將新的 loop, 下一個 loop 中的 $previous 為當前 loop 中的 $currentNode $previous = $currentNode; // 取得下一輪 loop 中的 $currentNode $currentNode = $currentNode->next; } } } }

• 以下程式碼的邏輯是？
  • Example:

    <?php class ListNode { public $data = null; public $next = null; public function __construct(string $data = null) { $this->data = $data; } } class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function deleteLast() { if ($this->_firstNode !== null) { $currentNode = $this->_firstNode; if ($currentNode->next === null) { $this->_firstNode = null; } else { $previousNode = null; while ($currentNode->next !== null) { $previousNode = $currentNode; $currentNode = $currentNode->next; } $previousNode->next = null; $this->_totalNode--; return true; } } return false; } }

  • Answer:

    <?php class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function deleteLast() { // 如果不是空的 if ($this->_firstNode !== null) { $currentNode = $this->_firstNode; // 如果當前的是最後一個, 那就把當前的設為 null if ($currentNode->next === null) { $this->_firstNode = null; // 如果不是最後一個 } else { $previousNode = null; // 找到最後一個為止 while ($currentNode->next !== null) { $previousNode = $currentNode; // 找下一個 $currentNode = $currentNode->next; } // 找到最後, 將 $previousNode->next 變成 null, 為什麼這邊不用 $currentNode = null 呢？ 因為 $currentNode 是一塊記憶體位址, 指向最後一個 node, 也就是最後一個 object, 如果我們讓 $currentNode = null, 實際上只是將 $currentNode 這塊記憶體位置變成 null, 其指向的 object 的值並不會改變。 但若是 $previousNode->next = null, 實際上是對 $previousNode 指向的 object 裡頭的 next property 做變更, 因此會更動到被指向的 object 的 property, 而這個 object 也是 $this->_firstNode 指向的 object, 因此也更新了 $this->_firstNode 的值 $previousNode->next = null; $this->_totalNode--; return true; } } return false; } }

• 以下程式碼的邏輯是？
  • Example:

    <?php class ListNode { public $data = null; public $next = null; public function __construct(string $data = null) { $this->data = $data; } } class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function deleteFirst() { if ($this->_firstNode !== null) { if ($this->_firstNode->next !== null) { $this->_firstNode = $this->_firstNode->next; } else { $this->_firstNode = null; } $this->_totalNode--; return true; } return false; } }

  • Answer:

    <?php class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function deleteFirst() { // 如果不是空的 list if ($this->_firstNode !== null) { // 如果不是最後一個, 就把當前的等於下一個, 也就是當前的就不見啦 // 如果已經是最後一個, 就直接把當前的設為 null if ($this->_firstNode->next !== null) { $this->_firstNode = $this->_firstNode->next; } else { $this->_firstNode = null; } $this->_totalNode--; return true; } return false; } }

    

• 以下程式碼的邏輯是？
  • Example:

    <?php class ListNode { public $data = null; public $next = null; public function __construct(string $data = null) { $this->data = $data; } } class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function insertAfter( string $data = null, string $query = null ) { $newNode = new ListNode($data); if ($this->_firstNode) { $nextNode = null; $currentNode = $this->_firstNode; while ($currentNode !== null) { if ($currentNode->data === $query) { if ($nextNode !== null) { $newNode->next = $nextNode; } $currentNode->next = $newNode; $this->_totalNode++; break; } $currentNode = $currentNode->next; $nextNode = $currentNode->next; } } } }

  • Answer:

    <?php class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function insertAfter( string $data = null, string $query = null ) { $newNode = new ListNode($data); // 如果不是空的 if ($this->_firstNode) { $nextNode = null; $currentNode = $this->_firstNode; // 找到最後一個為止 while ($currentNode !== null) { // 如果找到了 if ($currentNode->data === $query) { // 如果當前 node 不是最後一個 if ($nextNode !== null) { // 把下一個 node 接在 $newNode 之後 $newNode->next = $nextNode; } // 把 $newNode 接在當前 node 之後 $currentNode->next = $newNode; $this->_totalNode++; // 結束 while loop break; } // 如果沒找到, 並且還有沒跑過的 node, 才會執行到這一行 // 繼續往下找 $currentNode = $currentNode->next; $nextNode = $currentNode->next; } } } }

• 以下程式碼的邏輯是？
  • Example:

    <?php class ListNode { public $data = null; public $next = null; public function __construct(string $data = null) { $this->data = $data; } } class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function insertBefore(string $data = null, string $query = null) { $newNode = new ListNode($data); if ($this->_firstNode) { $previous = null; $currentNode = $this->_firstNode; while ($currentNode !== null) { if ($currentNode->data === $query) { $newNode->next = $currentNode; $previous->next = $newNode; $this->_totalNode++; break; } $previous = $currentNode; $currentNode = $currentNode->next; } } } }

  • Answer:

    <?php class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function insertBefore(string $data = null, string $query = null) { // init an ListNode object $newNode = new ListNode($data); // 如果該 list 不是空的 if ($this->_firstNode) { $previous = null; $currentNode = $this->_firstNode; // 往下找直到最後一個 while ($currentNode !== null) { // 如果當前 node 值等於帶入的 query if ($currentNode->data === $query) { // 將當前 node 接在 $newNode 之後 $newNode->next = $currentNode; // 如果是第一個, 自然為 null, 如果不是第一次, 會把 $newNode 接在上一個 node 之後 $previous->next = $newNode; $this->_totalNode++; break; } // 如果 query 不等於當前 node 才會執行這一段 $previous = $currentNode; // 繼續往下找 $currentNode = $currentNode->next; } } } }

    

• 以下程式碼的邏輯是？
  • Example:

    class ListNode { public $data = null; public $next = null; public function __construct(string $data = null) { $this->data = $data; } } class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function search(string $data = null) { if ($this->_totalNode) { $currentNode = $this->_firstNode; while ($currentNode !== null) { if ($currentNode->data === $data) { return $currentNode; } $currentNode = $currentNode->next; } } return false; } }

  • Answer:

    <?php class LinkedList { private $_firstNode = null; private $_totalNodes = 0; public function search(string $data = null) { // 如果 totalNode !== null if ($this->_totalNode) { $currentNode = $this->_firstNode; // 如果 $currentNode 不為 null, 表示還沒 search 完 while ($currentNode !== null) { // 如果找到了就 return if ($currentNode->data === $data) { return $currentNode; } // 如果沒找到, 找下一個 $currentNode = $currentNode->next; } } // 沒找到就 return false return false; } }

• 以下程式碼的邏輯是？
  • Example:

    <?php class ListNode { public $data = NULL; public $next = NULL; public function __construct(string $data = NULL) { $this->data = $data; } class LinkedList { private $_firstNode = NULL; private $_totalNodes = 0; public function insertAtFirst(string $data = NULL) { $newNode = new ListNode($data); if ($this->_firstNode === NULL) { $this->_firstNode = &$newNode; } else { $currentFirstNode = $this->_firstNode; $this->_firstNode = &$newNode; $newNode->next = $currentFirstNode; } $this->_totalNode++; return TRUE; } }

  • Answer:
    1. 建立一個新的 node
    2. 把這個新的 node 放在第一個
    3. 將之前的第一個 node 接在新的 node 後面

• 下圖是哪種資料結構？
  • 圖片
    
  • Answer
    multi-linked lists

• 下圖是哪種資料結構？
  • 圖片
    
  • Answer
    Circular linked list

• PHP 當中如何實作 linked list, 概念即可

  <?php class LinkedList { private $_firstNode = NULL; private $_totalNodes = 0; public function insert(string $data = NULL) { $newNode = new ListNode($data); if ($this->_firstNode === NULL) { $this->_firstNode = &$newNode; } else { $currentNode = $this->_firstNode; while ($currentNode->next !== NULL) { $currentNode = $currentNode->next; } $currentNode->next = $newNode; } $this->_totalNode++; return TRUE; } public function display() { echo "Total book titles: ".$this->_totalNode."\n"; $currentNode = $this->_firstNode; while ($currentNode !== NULL) { echo $currentNode->data . "\n"; $currentNode = $currentNode->next; } } } $BookTitles = new LinkedList(); $BookTitles->insert("Introduction to Algorithm"); $BookTitles->insert("Introduction to PHP and Data structures"); $BookTitles->insert("Programming Intelligence"); $BookTitles->display();

• PHP array 中, 取得 index 或 key 的 time complexity 是？
  O(1)

• 以下的 PHP code example, 可以怎麼優化, 概念即可
  • Example

    <?php $odd = []; $odd[] = 1; $odd[] = 3; $odd[] = 5; $odd[] = 7; $odd[] = 9; $prime = []; $prime[] = 2; $prime[] = 3; $prime[] = 5; if (in_array(2, $prime)) { echo "2 is a prime"; } $union = array_merge($prime, $odd); $intersection = array_intersect($prime, $odd); $compliment = array_diff($prime, $odd);

  • Answer:

    <?php $odd = []; $odd[1] = true; $odd[3] = true; $odd[5] = true; $odd[7] = true; $odd[9] = true; $prime = []; $prime[2] = true; $prime[3] = true; $prime[5] = true; if (isset($prime[2])) { echo "2 is a prime"; } $union = $prime + $odd; $intersection = array_intersect_key($prime, $odd); $compliment = array_diff_key($prime, $odd);

• 以下的 PHP code example 當中, $compliment 屬於資料結構中 set 的哪一種 operation？
  • Example:

    <?php $odd = []; $odd[] = 1; $odd[] = 3; $odd[] = 5; $odd[] = 7; $odd[] = 9; $prime = []; $prime[] = 2; $prime[] = 3; $prime[] = 5; if (in_array(2, $prime)) { echo "2 is a prime"; } $union = array_merge($prime, $odd); $intersection = array_intersect($prime, $odd); $compliment = array_diff($prime, $odd);

  • Answer:
    complement operation

• 以下的 PHP code example 當中, $intersection 屬於資料結構中 set 的哪一種 operation？
  • Example:

    <?php $odd = []; $odd[] = 1; $odd[] = 3; $odd[] = 5; $odd[] = 7; $odd[] = 9; $prime = []; $prime[] = 2; $prime[] = 3; $prime[] = 5; if (in_array(2, $prime)) { echo "2 is a prime"; } $union = array_merge($prime, $odd); $intersection = array_intersect($prime, $odd); $compliment = array_diff($prime, $odd);

  • Answer:
    intersection operation

• 以下的 PHP code example 當中, $union 屬於資料結構中 set 的哪一種 operation？
  • Example:

    <?php $odd = []; $odd[] = 1; $odd[] = 3; $odd[] = 5; $odd[] = 7; $odd[] = 9; $prime = []; $prime[] = 2; $prime[] = 3; $prime[] = 5; if (in_array(2, $prime)) { echo "2 is a prime"; } $union = array_merge($prime, $odd); $intersection = array_intersect($prime, $odd); $compliment = array_diff($prime, $odd);

  • Answer:
    union operation

• 以下的 PHP code example 當中, $odd 跟 $prime 是資料結構中的哪一種？
  • Example:

    <?php $odd = []; $odd[] = 1; $odd[] = 3; $odd[] = 5; $odd[] = 7; $odd[] = 9; $prime = []; $prime[] = 2; $prime[] = 3; $prime[] = 5; if (in_array(2, $prime)) { echo "2 is a prime"; } $union = array_merge($prime, $odd); $intersection = array_intersect($prime, $odd); $compliment = array_diff($prime, $odd);

  • Answer:
    Sets

• 資料結構 sets 中, complement operation 的意思是？
  對兩個集合實施 intersection union operation 後, 輸出為兩個集合中不同的值

• 資料結構 sets 中, union operation 的意思是？
  對兩個集合實施 intersection union operation 後, 兩個集合有的其輸出都會有

• 資料結構 sets 中, intersection operation 的意思是？
  對兩個集合實施 intersection operation 後, 其值為兩個集合中的交集

• 以下的 PHP example 當中, ronaldo 算是什麼資料結構？
  • Example:

    <?php Class Player { public $name; public $country; public $age; public $currentTeam; } $ronaldo = new Player; $ronaldo->name = "Ronaldo"; $ronaldo->country = "Portugal"; $ronaldo->age = 31; $ronaldo->currentTeam = "Real Madrid";

  • Answer:
    struct

• 以下的 PHP example 當中, player1 跟 player2 算是什麼資料結構？
  • Example:

    <?php $ronaldo = [ "name" => "Ronaldo", "country" => "Portugal", "age" => 31, "currentTeam" => "Real Madrid" ]; $messi = [ "name" => "Messi", "country" => "Argentina", "age" => 27, "currentTeam" => "Barcelona" ]; $team = [ "player1" => $ronaldo, "player2" => $messi ];

  • Answer:
    struct

• PHP 的 associative array 事實上是透過哪個資料結構達成的？
  hash table
  

• 以下 PHP code example 的意思是？
  • Example:

    <?php $array = new SplFixedArray(100); for ($i = 0; $i < 100; $i++) $array[$i] = new SplFixedArray(100);

  • Answer:

    <?php $array = new SplFixedArray(100); for ($i = 0; $i < 100; $i++) // 使用 SplFixedArray 建立 multidimensional array $array[$i] = new SplFixedArray(100);

• 以下 PHP code example 的意思是？
  • Example:

    <?php $items = 5; $array = new SplFixedArray($items); for ($i = 0; $i < $items; $i++) { $array[$i] = $i * 10; } $array->setSize(10); $array[7] = 100;

  • Answer:

    <?php $items = 5; // 給予 SplFixedArray size $array = new SplFixedArray($items); for ($i = 0; $i < $items; $i++) { $array[$i] = $i * 10; } // 重新指定 size $array->setSize(10); $array[7] = 100;

• 以下 PHP code example 的意思是？
  • Example:

    <?php $items = 5; $array = new SplFixedArray($items); for ($i = 0; $i < $items; $i++) { $array[$i] = $i * 10; } $newArray = $array->toArray(); print_r($newArray);

  • Answer:

    <?php $items = 5; $array = new SplFixedArray($items); for ($i = 0; $i < $items; $i++) { $array[$i] = $i * 10; } // 將 SplFixedArray 轉化成 PHP Array $newArray = $array->toArray(); print_r($newArray);

• 以下 PHP code example 的意思是？
  • Example:

    <?php $array =[1 => 10, 2 => 100, 3 => 1000, 4 => 10000]; $splArray = SplFixedArray::fromArray($array); print_r($splArray);

  • Answer:

    <?php $array =[1 => 10, 2 => 100, 3 => 1000, 4 => 10000]; // 將原生 array 轉換成 SplFixedArray $splArray = SplFixedArray::fromArray($array); print_r($splArray);

• PHP 中, SplFixedArray 跟 PHP Array 最大的優勢是？
  SplFixedArray 使用的記憶體較少

• 以下 PHP code example 的意思是？
  • example

    <?php $items = 100000; $startMemory = memory_get_usage(); $array = new SplFixedArray($items); for ($i = 0; $i < $items; $i++) { $array[$i] = $i; } $endMemory = memory_get_usage(); $memoryConsumed = ($endMemory - $startMemory) / (1024*1024); $memoryConsumed = ceil($memoryConsumed); echo "memory = {$memoryConsumed} MB\n";

  • Answer

    <?php $items = 100000; // 取得記憶體使用量 $startMemory = memory_get_usage(); // 使用 SplFixedArray 建立 size 為 100000 的 array $array = new SplFixedArray($items); // 賦值 for ($i = 0; $i < $items; $i++) { $array[$i] = $i; } // 取得記憶體使用量 $endMemory = memory_get_usage(); $memoryConsumed = ($endMemory - $startMemory) / (1024*1024); $memoryConsumed = ceil($memoryConsumed); echo "memory = {$memoryConsumed} MB\n";

• 如何使用 PHP array 來表示以下 graph data structure? 概念即可
  • Example:
    
  • Answer:

    <?php $graph = []; $nodes = ['A', 'B', 'C', 'D', 'E']; foreach ($nodes as $xNode) { foreach ($nodes as $yNode) { $graph[$xNode][$yNode] = 0; } } $graph["A"]["B"] = 1; $graph["B"]["A"] = 1; $graph["A"]["C"] = 1; $graph["C"]["A"] = 1; $graph["A"]["E"] = 1; $graph["E"]["A"] = 1; $graph["B"]["E"] = 1; $graph["E"]["B"] = 1; $graph["B"]["D"] = 1; $graph["D"]["B"] = 1;

• 以下的 PHP example 的 size 是多少？

  • Example:

    <?php $array = []; $array[10] = 100; $array[21] = 200; $array[29] = 300; $array[500] = 1000; $array[1001] = 10000; $array[71] = 1971;

  • Answer:
    7

• 以下的 PHP example 的輸出是？

  • Example:

    <?php $array = []; $array[10] = 100; $array[21] = 200; $array[29] = 300; $array[500] = 1000; $array[1001] = 10000; $array[71] = 1971; foreach($array as $index => $value) { echo "Position ".$index." holds the value ".$value."\n"; }

  • Answer:

    <?php Position 10 holds the value 100 Position 21 holds the value 200 Position 29 holds the value 300 Position 500 holds the value 1000 Position 1001 holds the value 10000 Position 71 holds the value 1971

• 演算法中, O(n) 的意思是？
  執行一段程式的最大執行次數

• 演算法中, implementation 後做的 analysis 又稱為？
  empirical analysis

• 演算法中, implementation 前做的 analysis 又稱為？
  theoretical analysis

• 演算法中, Storage Complexity 的定義是？
  需要多少儲存空間可以輸出？

• 演算法中, Time Complexity 的定義是？
  需要幾步可以輸出？

• 資料結構中, Heap 是基於哪一個資料結構上？？
  Tree

• 以下圖片代表哪種資料結構？
  • 圖片:
    
  • Answer:
    Heap

• 以下圖片代表哪種資料結構？
  • 圖片:
    
  • Answer:
    Graph

• 資料結構中, Graph 相當於一對集合, 分別是哪兩個集合？？
  • vertices
  • edges

• 資料結構 Graph 中, 代表點的叫做？？
  vertices or nodes

• 資料結構 Graph 中, 代表方向的叫做？？
  edge or arc

• 資料結構中, Graph 又分為哪兩大類？
  • directed
  • undirected

• 資料結構中, Tree 的最頂端稱為？
  root

• 資料結構中, Tree 是屬於 liner 還是 nonliner?
  nonliner

• 以下圖片代表哪種資料結構？
  • 圖片:
    
  • Answer:
    Tree

• 資料結構中, Map 相當於 PHP 中的什麼型態的 array？？
  associative array

• 資料結構中, 從 queue 移除 item 的方法稱為？？
  dequeue

• 資料結構中, 增加新的 item 到 queue 的方法稱為？？
  enqueue

• 資料結構中, Queue 的特性是？
  FIFO

• 以下圖片代表哪種資料結構？
  • 圖片:
    
  • Answer:
    Queue

• 從 stack 資料結構移除資料的方法叫做？
  pop

• 從 stack 資料結構加資料進去的方法叫做？
  push

• 資料結構主要又分成哪兩大群組？

  • liner data structures
  • nonliner data structures

• 以下圖片代表哪種資料結構？

  • 圖片:
    
  • Answer:
    linked list

• 以下圖片代表哪種資料結構？

  • 圖片:
    
  • Answer:
    doubly linked list

• 以下圖片代表哪種資料結構？

  • 圖片:
    
  • Answer:
    stack

• Stack 資料結構有什麼特性？
  LIFO

# 參考資料

[PHP 7 Data Structures and Algorithms: Implement linked lists, stacks, and queues using PHP`, no English version](https://www.amazon.com/PHP-Data-Structures-Algorithms-Implement-ebook/dp/B01IF7NLDW)