# 2022q1 Homework1 (quiz1)
contributed by <`arthurchang09`>
## Q1
### 解題

void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    struct hlist_head *h = &map->ht[hash(key, map->bits)];
    struct hlist_node *n = &kn->node, *first = h->first;
    AAA;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    BBB;
}

1. AAA 是 `n->next = first` 。 由下方的 `first->pprev = &n->next` 以及 `h->first = n` 可判斷是要將新的節點插入開頭，因此 AAA 的 `next` 指向原本第一個節點。
2. BBB 是 n->pprev = &h->first 。由 1. 可知次將新節點插入開頭，由於 `hlist` 是雙向的，要將節點之 `pprev` 指回前一個節點，在此便是指回開頭。又 `pprev` 是指標的指標，因此是指向 `h->first` 之位址，

### 解釋上述程式碼運作原理
* map_init()
初始化整個 hash table之 `map_t` 及各個 `hlist_head` ，並將每個 `hlist_head` 初始化為 `null` 。

digraph G{

    rankdir=LR;
    node[shape=record];
    m [label = "map|<h0>ht[0].first|<h1>ht[1].first|<h2>ht[2].first|<other>..."];
    null;
    m:h0:e->null
    m:h1:e->null
    m:other:e->null
    
}

* find_key()
查詢某個數值是否在 hash table 中並回傳位址。透過指定的 hash function 找到 `map` 中對應的 `hlist_head` ，接著走訪整個 linked list ，使用 `container_of` 巨集，找到整個 `hash_key` 的位址並取出值比較，若相符則回傳此位址。若無則回傳 `null` 。

* map_get()
呼叫 `find_key` 的 function 。透過 `find_key` 找到欲找的結點並回傳其值之指標，或者回傳 `null` 。

* map_add()
新增 `hash_key` 節點。先呼叫 `find_key()` 查詢節點是否存在。若否，則在其對應的 `hlist_head` 的開頭新增節點。

* map_deinit()
透過逐一走訪 `map` 中所有的 `hlist_head` 釋放整個 `hash table`，使用 `container_of` 找到對應 `hash_key` 的位址後釋放記憶體空間。最後釋放 `map` 的空間。

## Q2
針對 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)，以下是可能的合法 C 程式實作:

#include <stddef.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    if (COND1) {
        /* Remove all duplicate numbers */
        while (COND2)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}

此題之目標是要刪除值重複的節點， COND1 答案必然包含檢查當前節點的值是否和下一個節點的值相等，即 `head->value == head->next->value` 。然而，下一個節點可能為 `NULL` ，代表 linked list 已經走到結尾，直接 `head->next->value` 可能導致錯誤，因此要先判斷 `head->next` 是否為 `NULL` 。因此 COND1 為 `head->next && head->value == head->next-value` 。

while 迴圈的目的是要跳過所有值重複的節點，因此其條件和 COND1 相同，為 `head->next && head->value == head->next-value` 。

### 嘗試避免遞迴，寫出同樣作用的程式碼

struct ListNode {
  int val;
  struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head) {
  if (!head)
    return NULL;
  struct ListNode *node = NULL, *prev = NULL;
  int same_val = 0;
  for (node = head; node;) {
    if (node->next && node->val == node->next->val) {
      if (!prev) {
        head = node->next;
        same_val = 1;
        prev = NULL;
      } else {
        prev->next = node->next;
        same_val = 1;
        prev = node;
      }
    } else if (same_val) {
      same_val = 0;
      if (!prev) {
        head = node->next;
        prev = NULL;
      } else {
        prev->next = node->next;
        prev = node;
      }
    } else {
      prev = node;
    }

    node = node->next;
  }
  return head;
}

## Q3
針對 LeetCode 146. LRU Cache，以下是 [Least Recently Used (LRU)](https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)) 可能的合法 C 程式實作:

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;
    
typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

LRUCache *lRUCacheCreate(int capacity)
{   
    LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
    obj->count = 0;
    obj->capacity = capacity;
    INIT_LIST_HEAD(&obj->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_LIST_HEAD(&obj->hheads[i]);
    return obj;
}
    
void lRUCacheFree(LRUCache *obj)
{       
    LRUNode *lru, *n;
    MMM1 (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}   

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM2 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM3 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            lru->value = value;
            return;
        }
    }

    if (obj->count == obj->capacity) {
        lru = MMM4(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else {
        lru = malloc(sizeof(LRUNode));
        obj->count++;
    }
    lru->key = key;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    lru->value = value;
}

MMM1 可看出來是包含四個參數，其目的是走訪整個 linked list ，並釋放每個 node 的記憶體空間，因此需要 list_entry 這個巨集。又因為要醜訪並刪除、釋放記憶體空間，需要額外之指標，因此 MMM1 為 `list_for_each_entry_safe` 。

MMM2 和 MMM3 皆是走放整個 linked list 且無刪除動作，另外要透過 `hlink` 找到所在節點的 `LRUNode` 位址，需要使用 `list_entry` ，因此 MMM2 、 MMM3 皆為 `list_for_each_entry` 。

## Q4
針對 LeetCode 128. Longest Consecutive Sequence，以下是可能的合法 C 程式實作:

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

struct seq_node {
    int num;
    struct list_head link;
};                                                                                                                                                            
            
static struct seq_node *find(int num, int size, struct list_head *heads)
{   
    struct seq_node *node;
    int hash = num < 0 ? -num % size : num % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (node->num == num)
            return node;
    }
    return NULL;
}

int longestConsecutive(int *nums, int n_size)
{
    int hash, length = 0;
    struct seq_node *node;
    struct list_head *heads = malloc(n_size * sizeof(*heads));

    for (int i = 0; i < n_size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (int i = 0; i < n_size; i++) {
        if (!find(nums[i], n_size, heads)) {
            hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size;
            node = malloc(sizeof(*node));
            node->num = nums[i];
            list_add(&node->link, &heads[hash]);
        }
    }

    for (int i = 0; i < n_size; i++) {
        int len = 0;
        int num;
        node = find(nums[i], n_size, heads);
        while (node) {
            len++;
            num = node->num;
            list_del(&node->link);

            int left = num, right = num;
            while ((node = find(LLL, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            while ((node = find(RRR, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            length = len > length ? len : length;
        }
    }

    return length;
}

在第三個 `for` 迴圈中， left 和 right 分別以 num 為中心，向左或向右搜尋 hash table 中搜尋連續的數字並移除掉該節點，並更新最長長度，直到找不到連續的數值之節點，再移到下一個陣列中元素進行搜尋。注意到在 46 行中已經先刪除了一個節點 `num` ，且接下來兩個 `while` 迴圈會逐步刪除數字是連續之節點，即 `num - 1` 、 `num - 2` ... 和 `num + 1` 、 `num + 2` ... ，因此 `left` 和 `right` 要先進行加或減。 LLL 為 `--left` ， RRR 為 `++right` 。