<font color="#8A2BE2">[面試筆記]</font> 程式白板題
===

## [邏輯]
### 費波那契數列
---
0, 1, 1, 2, 3, 5, 8, 13, 21...

f(0)=0
f(1)=1 = 1
f(2)=1 = 1
f(3)=4 = f(2)+f(1)
f(4)=5 = f(3)+f(2)

//遞迴寫法
var fib = function (steps) {
  
  var fibNum = [0, 1];
  //Your code
  if (steps === 0) {
    return 0
  }
  if (steps === 1) {
    return 1
  }
  else
    return fib(steps-1) + fib(steps-2)
}

fib(1)

//迴圈寫法
var fib = function (steps) {
  
  var fibNum = [0, 1];
  //Your code
  for(let i=2; i<=steps; i++) {
    //i=2 [0, 1, 0+1 ]   = [0,1,1]
    //i=3 [0,1,1, 1+1]   = [0,1,1,2]
    //i=4 [0,1,1,2, 1+2] = [0,1,1,2,3]
    fibNum[i] =  fibNum[i-1] + fibNum[i-2]  
  }
  console.log(fibNum[steps])
  return fibNum[steps]
}

fib(10)

[連結1 tony大大](https://hackmd.io/@tony-hackmd/rksS1UiEO#練習四：寫一個能回傳-n-個--的函式1)
[連結2:](https://riverye.com/2020/03/11/從排斥寫程式到轉職成為工程師/)

### a 陣列和 b 陣列相乘變 c 陣列
---
a=[1,2,3] b=[4,5,6] c=[5,6,0,8,8] (類似這樣)

[1,2,3]
[4,5,6]

let c = []

[連結1:](https://www.1111.com.tw/1000w/fanshome/discussTopic.asp?cat=FANS&id=244344)
[連結2:](https://riverye.com/2020/03/11/從排斥寫程式到轉職成為工程師/)

### two sum題
---
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

[連結:](https://leetcode.cn/problems/two-sum)

## [DS]
### 遞迴 Recursion

//遞迴寫法
var fib = function (steps) {
  
  var fibNum = [0, 1];
  //Your code
  if (steps === 0) {     //Base Case if i===0 回傳
    return 0
  }
  if (steps === 1) {     //Base Case if i===1 回傳
    return 1
  }
  else                   //Recursive Case 
    return fib(steps-1) + fib(steps-2)
}

fib(1)

:::success
:::

### 堆疊 Stack
堆疊存放這麼多資訊很佔記憶體空間，每個函式呼叫都會佔用記憶體空間，當堆疊疊越高，表示電腦存放了很多函式呼叫資訊

這時可以用 for loop改寫

//迴圈寫法
function greet2(name){
    console.log("how are you, ", name, "?")
}
function bye(){
    console.log("ok bye!")
}
function greet(name){
    console.log("hello, ", name, "!")
    greet2(name)
    console.log("getting ready to say bye...")
    bye()
}

greet("maggie")

堆疊示意
| Step1 | Step2 | Step3 | Step4 |
| ------------------ | ----------------- | --------- | --------- |
| | | | |
| greet2函式 | | bye函式 | |
| greet函式 | greet函式 | greet函式 | greet函式 |
| | | | |
| 印出greet2，從堆疊拿出 | | 印出bye函式，從堆疊拿出 | |

//遞迴寫法
function f(x)
    if(x ==1) {
        return 1
    }
    else
        return x * f(x-1)

f(5)

### 佇列 Queue

### 雜湊表 Hash Table
| | 雜湊表(平均情況) | 雜湊表(最差情況) | 陣列 | 鏈結串列 |
|:---------- |:---------------- |:---------------- |:-----------------------------------------------------:| -----------------------------------:|
| 元素的存放 | | | 一個接一個連續排列 | 分散在各處 |
| 存取方式 | | | 隨機存取 | 循序存取 |
| 讀取 | O(1) | O(n) | O(1) | O(n) |
| 插入 | O(1) | O(n) | 需要搬移插入點之後的所有元素，沒有空間會發生錯誤 O(n) | 只要更改元素的指向位置 O(1) |
| 刪除 | O(1) | O(n) | 只要更改元素的指向位置 O(1) | 刪除完元素後，後續元素往前移動 O(n) |

將字串對應到數字

[1.49, 0.79, 2.49, 0.67, 1.47]
Apple(編號1.49), Banan(編號0.79), Cherry(編號2.49),.....

每次要找Apple會直接抓到index值，所以是O(1)

但是 Collision碰撞，會是
[1.49, 0.79, 2.49, 0.67, 1.47]
Apple(編號1.49), Banan(編號0.79), Cherry(編號2.49),.....
Avocado(編號1.49)

:::danger
這時候就需要使用鏈結串列
A| Apple(1.49)->Avocado(0.7)
B| Banan(0.79)
C| Cherry(2.49)
D|
:::

### 鏈結串列 Linked List
| | 陣列 | 鏈結串列 |
|:---|:---:|---:|
|元素的存放|一個接一個連續排列|分散在各處|
|存取方式|隨機存取|循序存取|
| 讀取 | O(1) | O(n) |
| 插入 | 需要搬移插入點之後的所有元素，沒有空間會發生錯誤 O(n) | 只要更改元素的指向位置 O(1) |
| 刪除 | 刪除完元素後，後續元素往前移動 O(n) | 只要更改元素的指向位置 O(1) |

備註：鏈結串列 雖然刪除是O(1)但是查訪需要O(n)

#### 解釋：
元素可以存在記憶體中任何一個空位，會紀錄下存放位置，透過存放位置找到鏈結串列的每一個元素

#### 應用：

1. 鏈結串列可能用在某些網站為了賺瀏覽量，一頁只顯示一個項目，例如10大電影，使用者必須一頁一頁的點擊『下一頁』去瀏覽整個資訊
2. 服務生將新訂單寫入，廚師只要取出最前端的訂單
2. 紀錄每天花費記帳程式，月底才需要檢視

#### 缺點：
當沒有需要依序讀取整個元素的話，使用鏈結串列就比較浪費時間了

#### 優點：
插入的資料多，讀取的資料少的資料適合使用

[連結hiskio:](https://blog.hiskio.com/leetcode-interview/)

## [AL]

### 線性搜尋 Linear Search

function test() {
  let data = [8, 2, 3, 10, 6]
  let index = linearSearch(data, 10)
  console.log("資料所在的位置", index)
}

//線性搜尋
function linearSearch(arr, target) {
  for(let i=0; i<arr.length; i++) {
    if(arr[i] === target) {
      return i
    }
  }
  return -1
}

test()

### 二元搜尋 Binary Search

function test() {
  let data = [2, 3, 6, 8, 10]
  let index = binarySearch(data, 5)
  console.log("資料所在的位置", index)
}

//二元搜尋法
function binarySearch(arr, target) {
  let startIndex=0
  let endIndex=arr.length-1

  while(endIndex >= startIndex ) {//黃金交叉，當index走交叉過對方
    let midIndex=Math.floor((startIndex+endIndex/2))
      if(target === arr[midIndex]){ //比對找到了，回傳資料是陣列中的第幾格元素
    return midIndex  
    }
      else if( target>arr[midIndex]) { //要找的資料比中間的數字大
        startIndex = midIndex+1
      }
      else{ //要找的資料比中間的數字小
        endIndex = midIndex-1
      } 
  }
  //while迴圈跑完沒搜到該值
  return -1
}

test()

### 氣泡排序 Bubble Sort
第一輪 i=3
[8,5,10,6] //j=0 8vs5 8比5大，8換至右方
[5,8,10,6] //j=1 8vs10 8比5小，不動
[5,8,10,6] //j=2 10vs6 10比6大，10換至右方
[5,8,6,10] //完成


 function bubbleSort(arr) {
   for(let i=arr.length-1; i>=1; i--) {
     for(let j=0; j<i; j++) {
       if(arr[j] > arr[j+1]) {  //如果順序不對，交換
         let temp = arr[j]
         arr[j] = arr[j+1]
         arr[j+1] = temp
       }
     }
   }
   console.log(arr)
 }

bubbleSort([8,5,10,6])

時間複雜度O(n^2)

### 選擇排序 Selection Sort
#### 解釋：
每次頭到尾走過一遍，找出該值方入。n個項目每次花費n次。不錯的演算法，但速度不快

#### 應用：
1. 紀錄每位歌手播放次數的記錄表，依播放次數高到低來排序
2. 排序電話簿裡面的姓名
4. 依照日期排序電子郵件

舉例
| | 播放次數 | |
|:---|:---:|---:|
| RADIOHEAD | 156 |
| SHAKIRA | 30 |
| John Legend | 94 | |
| Bruno Mars | 88 | |
| Taylor Swift | 61 | |
| Ladygaga | 111 | |

<br>

Step1 從頭到尾找出播放次數最多，是RADIOHEAD 花費O(n)
Step2 建立新的表格，把RADIOHEAD放入
| | 播放次數 | |
|:---|:---:|---:|
| RADIOHEAD | 156 |

<br>

Step1 從頭到尾找出播放次數最多，是Ladygaga 花費O(n)
Step2 新的表格，把Ladygaga放入
| | 播放次數 | |
|:---|:---:|---:|
| RADIOHEAD | 156 |
| Ladygaga | 111 | |

一直重複

#### 缺點：
時間複雜度O(n^2)
#### 優點：
簡單

### 快速排序 Quick Sort
差：O(n^2)
平均：O(nlogn)

步驟：
1. 挑選一個基準值(pivot)
2. 將陣列分割成兩個陣列：值小於pivot的放左，值大於pivot的放右
3. 遞迴呼叫快速排序法處理兩個子陣列

舉例 三個元素：
[33,15,10]

1. 選pivot 33
2. [15,10] 33, []
3. [10,15] 33, []
4. [10,15,33]

### 合併排序 Merge Sort
最差情況 O(nlogn)
平均情況 O(nlogn)

## [JS]
### var、let、const 區別
---
[連結:](https://hackmd.io/@YmcMgo-NSKOqgTGAjl_5tg/Hkp8PZalv)

### undefine 和 null 的差別
---

var box1 
console.log(box1)    //undefined，有宣告這變數，但沒值
 
console.log(box2)    //not defined，沒宣告這個變數

[連結:](https://hackmd.io/@tony-hackmd/rksS1UiEO)

### == 和 === 差別
---

//== : 不會比較型態
//=== : 會比較型態

//常用在判斷數字跟字串的內容是否相等
console.log(1 == '1');    //true
console.log(1 === '1');    //false

### a++ 和 ++a 差別
---

//a++跟++a的區別 
var a = 0
a = a + 1
console.log(a)    //1
a++               //會先將a值賦於左邊a在計算
++a               //會先執行a = a + 1在將值給左邊

###### tags: `[面試]`