# Garmin BPM Junior Developer Testing

## Basic Java Part


請根據上圖，回答以下三小題：
1. 紅色的 interface 與 綠色 class 差異為
:::info
從關係圖可以看到，紅色彼此之間會使用 `extends` 去繼承彼此的 interface，而綠色則是使用 `implements`。
這個架構是代表物件導向中的 `工廠模式`，透過 `定義好規範 (interface)` 讓實際 `實現的類(Class)` 自行去寫出 `不同特性但相同功能` 的物件。
:::
1. 請解釋實線與虛線之間的差異
:::info
實線：繼承 (extends)，透過繼承父類別來不重複撰寫相同的程式碼邏輯或規範。
虛線：實現 (implements)，透過已經定義好的規範，撰寫其程式碼去實現該類的功能。
:::
1. 請盡可能解釋釋**所有**的綠色區塊作用以及其間差異
- List
- ArrayList
:::info

- 這是一個動態陣列，隨著元素不斷塞入，它會申請新的記憶體空間並刪除舊的陣列來進行存放。
- 它允許透過 `index` 獲取元素。
- 記憶體位置是 `連續的`。
- 建議使用場景：
- 資料不會被頻繁地進行 `插入` 或 `刪除` 等操作。
- 需要透過 `index`，而不是 `迭代` 快速獲取資料。
- 資料大小不會發生 `劇烈變化`
:::
- LinkedList
:::info

- 此資料結構中有許多 `獨立的節點 (物件)`，它使用 `指標` 和 `位址` 作為連結進行連街。
- 記憶體位置 `不連續`。
- 建議使用場景：
- 資料將被 `頻繁操作`，例如插入或刪除。
- `不需要`快速獲取數據。
- 資料大小 `尚未確認`。
:::
- Vector
:::info
- 它與 ArrayList `具有相同的功能`，但它側重於 `執行緒安全 (Thread-Safe)`。
- 由於執行緒安全的原因，其 `效能低於 ArrayList`。
- 在多執行緒場景下，可以利用 Vector 的 `synchronized 特性` 來 `防止資料競爭 (data race)`。
- 以下程式碼片段用來實證 ArrayList 與 Vector 兩者特性：

            import java.util.ArrayList;
            import java.util.Vector;
            import java.util.List;
            import java.util.concurrent.ExecutorService;
            import java.util.concurrent.Executors;
            import java.util.concurrent.TimeUnit;
            import java.lang.System;

            public class Test  {
                private static List<String> list = new ArrayList<String>();
                private static List<String> vList = new Vector<String>();

                public static void main(String[] args) throws Exception {
                    ExecutorService e = Executors.newFixedThreadPool(5);
                    e.execute(new WriterTask());
                    e.execute(new WriterTask());
                    e.execute(new WriterTask());
                    e.execute(new WriterTask());
                    e.execute(new WriterTask());

                    e.awaitTermination(5, TimeUnit.SECONDS);
                    System.out.println();

                    e.execute(new WriterTaskV());
                    e.execute(new WriterTaskV());
                    e.execute(new WriterTaskV());
                    e.execute(new WriterTaskV());
                    e.execute(new WriterTaskV());

                    System.out.println("Total elements in ArrayList is " + list.size() + ".");
                    System.out.println("Total elements in Vector is " + vList.size() + ".");
                }

                static class WriterTask implements Runnable {
                    @Override
                    public void run() {
                        long start = System.nanoTime();
                        for (int i = 0; i < 1000; i ++) {
                            list.add("a");
                        }
                        long end = System.nanoTime();
                        System.out.println("Worker finished the job of ArrayList in " + (end-start)/1000 + " micro seconds.");
                    }
                }

                static class WriterTaskV implements Runnable {
                    @Override
                    public void run() {
                        long start = System.nanoTime();
                        for (int i = 0; i < 1000; i ++) {
                            vList.add("a");
                        }
                        long end = System.nanoTime();
                        System.out.println("Worker finished the job of Vector in " + (end-start)/1000 + " micro seconds.");
                    }
                }
            }
            

- 實驗結果：

:::
- Stack
:::info
- Stack 是一個 LIFO 的資料結構，繼承自 `Vector`，也就是說他也有 `執行緒安全` 的特性。
- 從 `Vector` 可以看到，底層邏輯是使用 `陣列` 實現的。

                    public class Vector<E> extends AbstractList<E>vimplements List<E>, RandomAccess, Cloneable, java.io.Serializable
                    {
                        protected Object[] elementData;
                        protected int elementCount;
                        protected int capacityIncrement;
                    }

- 常用於實現字串反轉、計算機實現和瀏覽器瀏覽紀錄中使用。
- 若是 `不在乎執行緒安全`，則可以考慮 `ArrayDeque`，其 `性能更好`。
:::
- Queue
- PriorityQueue
:::info
- PriorityQueue 是使用 `Heap` 資料結構的特性去實現的隊列，也就是說順序的優先級不是 FIFO，而是 `元素的升/降序` 或是 `使用 Comparator` 來制定排序規則。
- 每次新增/刪除的時間複雜度為 `O(logn)`
- 常用於使用 `任務調度`、`事件處理` 和演算法中需要 `對元素進行排序` 的場景。
:::
- Deque
- ArrayDeque
:::info
- ArrayDeque 是一個 `雙向的隊列`，它可以實現 `FIFO` 或是 `LIFO` 的特性，其底層邏輯則是基於 `陣列` 來實現。
- 相較於 `Linked List` 效能更好。
- 不需要頻繁 `申請` 或 `釋放` 記憶體，可以更好利用 CPU 快取，提高訪問效率。
- 在不考慮執行緒安全且效能優先的情況下，ArrayDeque 是 `隊列` 和 `堆疊` 的首選。
:::
- Set
- HashSet
:::info
- HashSet 其實是使用 HashMap 所實現的，只不過在 value 的部分以 `固定的 Object 物件` 進行填充。
- 其功能主要用於 `去除重複的元素`。
- 其查找、插入與刪除的時間複雜度皆為 `O(1)`。
:::
- LinkedHashSet
:::info
- LinkedHashSet 是使用 LinkedHashMap 所實現的，其中這個資料結構會有 `雙向鏈結串列`，用來記錄彼此的 `順序`。
- 它既可以 `快速查找`、`插入` 和 `刪除`，也可以 `記錄元素插入的順序`。
- 其查找、插入與刪除的時間複雜度皆為 `O(1)`。
:::
- SortedSet
- TreeSet
:::info
- TreeSet 是使用 TreeMap 所實現的，資料結構則是使用 `紅黑樹` 來維護元素的順序。
- 它可以 `自動` 對集合中的元素進行 `排序`，主要是按照 `升降序` 或 `Comparator` 來制定排序規則。
- 其查找、插入與刪除的時間複雜度皆為 `O(n)`。
:::

## Coding Part

撰寫一個 Method 在傳入的字串陣列中，找最長的共有 prefix 字串，如果沒有共有的 prefix ，則回傳空字串即可。

> Example 1:

Input: strs = [“flower”,“flow”,“flight”]
Output: “fl”
Example 2:

> Example 2:

Input: strs = [“dog”,“racecar”,“car”]
Output: “”
Explanation: There is no common prefix among the input strings.

> Constraints:

0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lower-case English letters.

### 解題思路

看到每個字串都需要進行比較，我有想到兩個解法：

:::info
解法一：根據字串長度進行排序，每次迭代都以最短的字串來逐一進行比較，直到找到不同字元或最短字串到頭。
- 時間複雜度
- O(nm)~O(n^2)，n 為字串陣列數，m 為最短字串長度
- O(n^2) 排序最壞情況
- 空間複雜度
- O(1)

解法二：可以使用一般 web 中常見的 router 配對方式 —— Trie Tree。
Trie Tree 會將每個字元當作是一個節點，並且往後插入新的節點直到該字串結束，如此一來，只要是共用的字元就會被當作是我們的 Prefix，就可以方便我們找到答案。
- 時間複雜度
- 插入：O(nm)，n 為字串陣列數，m 為平均字串長度
- 查找：O(m)，m 為最長字串長度
- 空間複雜度
- O(nm)，n 為字串陣列數，m 為平均字串長度

我個人認為解法二在 `重複使用` 的場景下時間複雜度較低，所以使用 Trie Tree 解題。
:::

### 程式碼邏輯

import java.lang.StringBuilder;
import java.lang.System;

class Solution {
    
    // 字母大小
    public static final int ALPHABET_SIZE = 26;
    
    // Trie 節點
    public TrieNode root;
    
    // 字母對應 index
    public int indexs;
      
    // Trie node
    public class TrieNode {
        // 每個 TrieNode 都會對應 26 個字母
        public TrieNode[] children = new TrieNode[ALPHABET_SIZE];
      
        // 判斷是否為最終節點，如果 true 代表後續沒有節點
        public boolean isLeaf = false;
         
        // constructor
        public TrieNode() {
            for (int i = 0; i < ALPHABET_SIZE; i++)
                children[i] = null;
        }
    };
      

    // 如果該 node == null，直接插入該 key
    // 如果該 node 是最後的節點，isLeaf 標記成 true
    public void insert(String key) {
        TrieNode temp = root;
        int index = 0;
      
        for (int level = 0; level < key.length(); level++) {
            // 字元轉 index
            index = key.charAt(level) - 'a';

            // 如果 children == null，建立子 Trie Node
            if (temp.children[index] == null)
                temp.children[index] = new TrieNode();
      
            // 存入該字元的 index
            temp = temp.children[index];
        }
      
        // 標記最後為節點
        temp.isLeaf = true;
    }
      
    // 計算 Trie Node 中有幾個字母被記錄
    public int countChildren(TrieNode node) {
        int count = 0;
        for (int i=0; i<ALPHABET_SIZE; i++) {
            if (node.children[i] != null) {
                count++;
                indexs = i;
            }
        }
        return count;
    }
      
    // 解題函數
    public String longestCommonPrefix(String[] strs) {
        // 建立一個空 Trie Tree 準備儲存 String[]
        root = new TrieNode();
        
        // 迭代 String[]，將每個 String 存入 Trie Tree
        for (int i = 0; i < n; i++)
            insert(strs[i]);
      
        // 走訪節點來計算共同的前綴
        TrieNode temp = root;
        
        // 如果節點上只有一個字母，它可以記錄該字母是哪個 index，方便後續查找
        indexs = 0;
        
        // 字串拼接，效能高
        StringBuilder prefix = new StringBuilder();
      
        // 只要每次在該節點上，只有一個字母存在且 isLeaf == false，就代表這是共用前綴
        while (countChildren(temp) == 1 && temp.isLeaf == false) {
            temp = temp.children[indexs];
            prefix.append((char)('a' + indexs));
        }
        
        return prefix.toString();
    }
      
    // 執行
    public static void main(String args[]) {
        Solution s = new Solution();
        String arr1[] = {"flower","flow","flight"};
        String ans1 = s.longestCommonPrefix(arr1);
      
        if (ans1.length() != 0)
            System.out.println("The longest common prefix is "+ans1);
        else
            System.out.println("There is no common prefix");
            
        String arr2[] = {"dog","racecar","car"};
        String ans2 = s.longestCommonPrefix(arr2);
        
        if (ans2.length() != 0)
            System.out.println("The longest common prefix is "+ans2);
        else
            System.out.println("There is no common prefix");
    }
}

### 結果

The longest common prefix is fl
There is no common prefix

## Java Debug Part

請說明下列程式碼，可能會有的問題。

Problem A.

List<IHat> hats = new ArrayList<>();
hats.add(new Ushanka()); // that one has ear flaps
hats.add(new Fedora());
hats.add(new Sombrero());
for (IHat hat : hats) {
    if (hat.hasEarFlaps()) {
        hats.remove(hat);
    }
}

:::info
解釋：
Java 在使用 `foreach` 時，編譯器會將其轉換成 `Iterator` ，轉換如下：

Iterator it = hats.iterator();

while(it.hasNext()) {
    IHat str = (IHat)it.next();
    if (hat.hasEarFlaps()) {
        hats.remove(hat);
    }
}

如果在迭代的時候 remove 元素，就會發生 `ConcurrentModificationException`，如下：

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1013)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:967)
	at org.example.Main.main(Main.java:23)

那麼我們可以點擊錯誤訊息，往下追蹤是哪裡出問題：

// ArrayList.java:967
public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

// ArrayList.java:1013
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

原來是 `checkForComodification()` 這個函數，在我們走訪下一個元素的時候，會先去確認 `modCount` 與 `expectedModCount` 是否相同。若不同就會出錯。

這個 `modCount` 就是 ArrayList 這個 Collection 修改的次數，也就是說如果有 `新增/刪除` 操作，`Collection` 就會進行增加。

當我們在 add() 三次時使用 foreach，這時 `expectedModCount` 就會是 `3`，可是當我們迴圈中使用 `remove()` 時候 `modCount` 就會加一變成 `4`，所以才導致噴錯的問題。

唯一的解法是，不要使用 Collection 來新增/刪除元素，而是 iterator()。

以下是 `iterator.remove()` 的原始碼：

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet); // 刪除上一個元素
        cursor = lastRet; // 更新下一个元素的 INDEX
        lastRet = -1; // 清空上一个返回元素的 INDEX
        expectedModCount = modCount; // 更新 ArrayList 的 expectedModCount
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

可以發現 expectedModCount 會被更新，也就避免了 `ConcurrentModificationException` 的錯誤發生。
:::

:::info
Solution A.

List<IHat> hats = new ArrayList<>();
hats.add(new Ushanka()); // that one has ear flaps
hats.add(new Fedora());
hats.add(new Sombrero());

// Method 1.
hats.removeIf(hat -> hat.hasEarFlaps());

// Method 2. 
Iterator<IHat> it = hats.iterator();
while (it.hasNext()) {
    IHat hat = it.next();
    if (hat.hasEarFlaps()) {
        it.remove();
    }
}

其實 `hats.removeIf(hat -> hat.hasEarFlaps());` 是 `Method 2.` 的語法糖，原始碼如下：

default boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    boolean removed = false;
    final Iterator<E> each = iterator();
    while (each.hasNext()) {
        if (filter.test(each.next())) {
            each.remove();
            removed = true;
        }
    }
    return removed;
}

:::

Problem B.

selfie = person.shootASelfie();
try {
    selfie.show();
} catch (NullPointerException e) {}

:::info
解釋：
一般來說，selfie 前面應該要有該 `資料型別`，如果沒有，可以初步判斷它是 `class 內已經宣告的變數` 或是 `區域變數`。
然後，selfie 這個物件會使用函數 `show()`，代表說這個 selfie 不能是 null，不然會產生 `NullPointerException`。
:::

:::info
Solution B.

selfie = person.shootASelfie();
if (selfie != null)
    selfie.show();
else {
    // null 處理
}

:::

## ERD Part


請說明上圖 Entity 之間的關係

:::info
這個 ERD 設計類似 [IMGUR](https://imgur.com) 這種圖片分享平台。
- 主要有四個一對多關聯
- 一個相簿可以對應多個照片(或0個)
- 一個地點可以對應多個照片(或0個)
- 一個會員可以對應多個照片(或0個)
- 一個照片可以對應多個留言(或0個)
- 一個多對多關聯
- 照片可以有多個標籤(或0個)，而標籤而不局限於單一照片(或0個)

- 首頁
- 熱門照片 (瀏覽量、留言數)、最新照片(uploadDate)
- 搜尋
- 根據 photo title
- 根據 tag
- 根據 album title
- 根據 location name

- 會員管理 (管理會員資料)
- 新增
- 修改
- 獲取
- 刪除
- email 驗證
- 手機驗證
- 地址驗證
- Album (Album 內可以沒有照片)
- 根據 member_id
- 新增
- 修改
- 獲取
- 刪除 (裡面有沒有照片，跳出確定刪除通知)
- 觀看數更新 (MQ、Redis)
- Photo
- 添加 link 欄位，紀錄 cdn 位置
- 根據 album_id, member_id, location_id
- 新增
- 修改
- 獲取
- 刪除
- 照片隱私操作
- 觀看數更新 (MQ、Redis)
- Location
- 新增
- 修改
- 獲取
- 刪除
- Comment
- 根據 photo_id
- 新增
- 修改
- 獲取
- 刪除
- TagInPhoto
- 根據 photo_id
- 新增
- 修改
- 獲取
- 刪除
- Tag
- 新增
- 修改
- 獲取
- 刪除
:::

## SQL Part

承上題，請寫下以下需求的 SQL。

1. 請列出所有 Photo 的 title 以及 description.
:::info

    SELECT Title, Description
    FROM Photo;

:::
1. 請列出在 Album 名稱為 “2021 員工旅遊” 的所有照片.
:::info

    SELECT b.Title as Title, b.Description as Description
    FROM Album a
    LEFT JOIN Photo b ON a.photo_id = b.photo_id
    WHERE a.Title = '2021 員工旅遊';

因為 LEFT JOIN 可能會有`有相簿還沒上傳照片`的情況發生，如果要避免 Photo 是 null 的話，可以使用 INNER JOIN。

    SELECT b.Title as Title, b.Description as Description
    FROM Album a
    INNER JOIN Photo b ON a.photo_id = b.photo_id
    WHERE a.Title = '2021 員工旅遊';

:::
1. 請列出所有 member “John” 在 2021-1 月上傳且有留下 commet 的所有照片
:::info
這邊使用 INNER JOIN 代表，連接的右表是 NULL 的話就會被過濾，剛好可以找出有 COMMENT 的照片。

    SELECT b.Title as Title, b.Description as Description
    FROM Member a
    INNER JOIN Photo b ON a.member_id = b.member_id
    INNER JOIN Comment c ON b.photo_id = c.photo_id
    WHERE b.UploadDate = '2021-1' and a.Name = 'John';

:::
1. (時間允許再作答) 請列出 address 在汐止的 member，上傳的照片 location 在日本，並有打上 Tag 為 “家庭旅遊” 的總觀看數 (view)，並根據會員名稱分別列出。
:::info

    SELECT a.Name AS Name, SUM(b.View) AS View
    FROM Member a
    INNER JOIN Photo b ON a.member_id = b.member_id
    INNER JOIN Location c ON b.location_id = c.location_id
    INNER JOIN Photo_Tag d ON b.photo_id = d.photo_id
    INNER JOIN Tag e ON d.tag_id = e.tag_id
    WHERE a.Address = '汐止'
    AND c.Name = '日本'
    AND e.Title = '家庭旅遊'
    GROUP BY a.Name;

:::

## Keyword

下列有許多關鍵字，請勾選可以解釋的項目，稍候一起討論。
- [X] Spring Framework
- [ ] ExtJS
- [ ] Struts
- [ ] Sitemesh
- [X] React
- [X] Spring Boot
- [ ] SSRS
- [X] MongoDB
- [X] Elatic Search
- [ ] Quartz
- [ ] Grails
- [X] Vim
- [X] Intellj
- [X] Guava
- [ ] Apaache Common Libary
- [X] Refactor
- [X] Docker
- [X] K8S
- [X] Git
- [X] SVN