###### tags: `資訊產業導論`
# info2021-homework2
> 貢獻者: 李馬克 Mark

## 第一題
:::info
簡單描述 Array 與 Linked List 的差別
:::

- Array
- 每個元素存在連續的 Memory space
- 因為是連續的 memory space，因此在查找元素可以很快的鎖定範圍，花費的資源會比較少
- Insert, Delete 需要確保 memory 的連續性，因此要對每個元素做調整，花費的資源也會比較多
- Linked List
- 每個元素不用存在連續的 Memory space
- 因會是不連續的 momory space，在查找元素時必須遍尋所有的節點，才可知道元素是不是存在其中，花費的資源會比較多
- Insert, Delete 只要針對 Node 指向的 memory address 做調整，就可完成，因此消耗資源少

## 第二題
:::info
反轉 Singly linked list
:::

//定義 Node 結構
class Node() {
    int value;
    Node nextNode;
    Node(int val) { this.value = value; }
}
// 遞迴版本
private Node reverseNodeRecursive(Node head) {

    // 透過遞迴找出最後一個 Node，此 Node 會是新的 Root Node
    if(head == null || head.nextNode == null) {
        return head
    }

    Node newNode = reverseNodeRecursive(head.nextNode)
    
    // 反轉下一個 Node 指向自己，此時會是一個 cycle
    head.nextNode.nextNode = head;
    // 因此讓目前的 Node 指向 null 即可斷掉 cycle
    head.nextNode = null;

    return newNode;
}

## 第三題
:::info
很大的 linked list 放入 遞迴中，有可能會發生 stack over flow，那如何解決嗎？
:::

用迭代可以解決，遞迴可能導致 stack overflow 是因為沒有 bound checking，導致同樣的函式被無線的調用，而韓個函式的调用都都會被放入 stack space 中，只有 return 後該函式才會被銷毀，而沒有 Bound checking 的遞迴函式調用會無限的被加入 stack 之中且不會輕易被銷毀，這就導致 stack overflow

## 第四題
:::info
能不能一樣採用遞迴但不會發生 stack over flow？
:::
- 在 JVM 中無法採用 tail recursion，JVM 為了維護整個 stack space，以便了解從哪個函數調用哪個函數。一個很好的例子將是 stack space tracking，有助於在某個功能中拋出異常時顯示整個call stack 的順序
- 但是如果是在 Kotlin 中，可以加上 tailRec annotation, 可以以尾呼叫優化方式編寫函數，但內部它將其轉換為迭代函數並運行
- 尾遞迴本質就是把遞迴轉為迭代

## 第五題
:::info
可以簡單說明一下該怎麼判斷一個 Singly linked list 存在 cycle？
:::
1. 建立一個 Hash set
2. 走過 Linked list 裡面的每個 Node
3. 檢查 Node 是否已經存在 Hash set
- 尚未存在則將 Node 加入 Hash set
- 反之，則存在 cycle

Time complexity: O(n)
Space complexity: O(n)

## 第六題
:::info
那是否可以知道是哪個 Node 開始產生 cycle 的呢？
:::

可以採用與題五相同方法，找到已經存在的 Node 即為產生 cycle node
Time complexity: O(n)
Space complexity: O(n)

## 第七題
:::info
在不改變 time complexity 的狀況下，減少 Space complexity？
:::

class Node() {
    int value;
    Node nextNode;
}

class Solution() {
    // 用 HashSet 找出產生 cycle 的 Node
    private Node beginCycleNode(Node head) {
        HashSet<Node> set = new HashSet();
        
        while(head != null) {
            if(set.contains(head)) {
                return head;
            } else {
                set.add(head);
                head = head.nextNode;
            }
        }
        
        return null;
    }
    
    // 找出"開始"、"產生 cycke"、"碰撞"此三個 Node 的距離關係
    private Node beginCycleNodeTwo(Node head) {
        Node fast = head;
        Node slow = head;
        
        while(slow != null && fast != null) {
            slow = slow.nextNode;
            fast = fast.nextNode.nextNode;
            
            if(slow == fast) {
                break;
            }
        }
        
        if (fast == null || fast.nextNode == null) {
            return null;
        }
        
        Node explpore = head;
        while(explore == slow) {
            explore = explore.nextNode;
            slow = slow.nextNode;
        }
        return explore;
    }
    
    public static void main(String[] args) {
        Node head = new Node(3);
        head.nextNode = new Node(2);
        head.nextNode.nextNode = new Node(0);
        head.nextNode.nextNode.nextNode = new Node(-4);
        head.nextNode.nextNode.nextNode.nextNode = head.nextNode;
        
        System.out.println(beginCycleNode(head).value);
        System.out.println(beginCycleNodeTwo(head).value);
    }

}

## 第八題
:::info
是否可以反轉一個有 cycle 的 Linked List?
:::

>If the linked list does not contain a cycle, then this partial function is injective (one-to-one), meaning that no two nodes map to the same successor. Injective functions can indeed be inverted, which is why you can reverse a regular linked list. However, if the list contains a cycle, then there are two nodes with the same successor, so the function is not injective and thus does not have an inverse. So no, you cannot reverse the linked list and expect to get another linked list, if the list has a cycle.

Linked list 算是一種映射函式，因此若任意反轉存在 cycle linked list，則會發生有某個 Node 會映射到兩個以上的 Node，因次會不符合 linked list 的定義

因此在此題需要先檢查 linked list 是否存在有否一個 Node 同時被兩個以上的 Node 指到，若是則不可反轉，反之即可反轉

- 可反轉：

- 不可反轉：

## 第九題
:::info
請 Coding up，如果是可反轉的 cycle list 回傳反轉的 Linked list，否則回傳 null
:::

class Solution() {
	public Node beginCycleNode(Node head) {
		Node slow = head;
		Node fast = head;

		while(slow != null && fast != null) {
			slow = slow.next;
			fast = fast.next.next;
			if(slow == fast) break;
        }

    if(fast == null || fast.next == null || slow == head) return reverseRecurtion(head, head);

    return null;
    }

    public Node reverseRecurtion(Node head, Node originHead) {
        if(head == null || head.next == null || head.next == originHead) return head;
        Node newRoot = reverseRecurtion(head.next);

        head.next.next = head;
        head.next = null;

        return newRoot;
    }
}

## 檢討
### Interviewer
- 是要簡答、討論或是寫程式碼要在更明確的表達，否則 Interviewee 會花太多時間在不用寫程式的地方
- 應有必要的檢驗和討論
- 英文的關鍵字沒有表達清楚
- 英文不夠流暢

### Interviewee
- 簡答題的回答時間普遍落在 1 分鐘到 1 分半，須練習能在 30 秒左右講到重點
- Node 與元素混用
- 英文的關鍵字沒有表達清楚
- 英文不夠流暢

## Reference
- https://stackoverflow.com/questions/5209734/is-it-possible-to-reverse-a-linked-list-that-contains-a-cycle
- https://medium.com/coding-blocks/tail-call-optimization-in-jvm-with-kotlin-ebdf90b34ec9