---
tags: info2022-homework1
---

# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022)」作業 1
> 貢獻者: 旗忠一仁-someone
> 🧔: interviewer
> 👶: interviewee

> [模擬面試錄影(漢)](https://youtu.be/9wEl1LJ8-Uk)
> [模擬面試錄影(英)](https://youtu.be/-mvhE_K7FBg)
## [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/) / [142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/)

1. Practice speaking for long recording session
1. Rehearsal before recording, try to do the interview in one take
1. Wrong intonation for majority of the video
1. Not speaking clearly
1. [11:11](https://youtu.be/u8BifwrZlac?t=671) for byte addressable memory, assume at least 32-bit architecture, hence `>> 4` instead of `>> 2`
1. [19:55](https://youtu.be/u8BifwrZlac) Mistakes in code
`line 72` should be `head != fast`
`line 73 - 74` isn't assigning value to `head` and `fast`

Code (Linked List Cycle - failed in leetcode) :

bool hasCycle(struct ListNode *head)
{
        struct ListNode *dummy = malloc(sizeof(struct ListNode));
        while (head && head->next) {
                if (head->next == dummy) {
                        return  true;
                }
                struct ListNode *prev = head;
                head = head->next;
                prev->next = dummy;
        }
        return false;
}

Code (Linked List Cycle) :

bool hasCycle(struct ListNode *head)
{
        struct ListNode *tmp = malloc(sizeof(struct ListNode));
        while (head && head->next) {
                if (head->next == tmp) {
                        return  true;
                }
                struct ListNode *prev = head;
                head = head->next;
                prev->next = tmp;
        }
        return false;
}

Code (Linked List Cycle II) :

struct ListNode *detectCycle(struct ListNode *head)
{
        uintptr_t addr[400000] = {0};
        while (head) {
                if (addr[(uintptr_t)head%400000])
                        return head;
                addr[(uintptr_t)head%400000] = 1;
                head = head->next;
        }
        return NULL;
}

Code (Linked List Cycle II) :

struct ListNode *detectCycle(struct ListNode *head)
{
        struct ListNode *slow, *fast;
        slow = fast = head;
        while (fast && fast->next) {
                slow = slow->next;
                fast = fast->next->next;
                if (slow == fast) {
                        while (head != fast) {
                                head = head->next;
                                fast = fast->next;
                        }
                        return head
                }
        }
        return NULL;
}

---

## [64. Add Binary](https://leetcode.com/problems/add-binary/)
> 模擬面試錄影 (漢)

1. Talk faster
1. [14:37](https://youtu.be/rlCHl8ae_3I?t=878) Give alternative for more efficient division / modulo before introducing bitwise addition
Both division and modulo operates on a constant, optimize by multiplication by inverse

Code (Add Binary)

#define C2D(x) ((x) - '0')
#define D2C(x) ((x) + '0')

char * addBinary(char * a, char * b)
{
        int la = strlen(a), lb = strlen(b);
        int l = (la < lb ? lb : la) + 2;
        char *res = malloc(l);

        for (int i = 0; i < l - 1; ++i)
                res[i] = '0';
        res[--l] = '\0';

        char c = 0;
        while (l--) {                                                         
                char b1 = 0, b2 = 0;
                if (la)
                        b1 = C2D(a[--la]);
                if (lb)
                        b2 = C2D(b[--lb]);

                char xor = b1 ^ b2;
                res[l] = D2C(c ^ xor);
                c = (c & xor) | (b1 & b2);
        }
        return res + (res[0] == '0');
}

## Problem
[8. String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/)
question not well-defined (does not fully define what should be 0 and what should be a value)
whack-a-mole after the base code is written down (ignore edge case in interview)
how to deal with overflow (after adding value vs before adding value)

[1935. Maximum Number of Words You Can Type](https://leetcode.com/problems/maximum-number-of-words-you-can-type/)
Approach 1. Brute Force
Approach 2. Hash Map

[1508. Range Sum of Sorted Subarray Sums](https://leetcode.com/problems/range-sum-of-sorted-subarray-sums/)
Solution : Brute Force (+ qsort)
Followup : What if initially sorted (binary search)

---

## Attempts
### Attempt 1
> Recording

[718. Maximum Length of Repeated Subarray](https://leetcode.com/problems/maximum-length-of-repeated-subarray/)
1. Use text to explain approaches
1. Time are wasted explaining pointless code, elaborate better or type faster
[1:01](https://youtu.be/Bm1UXzt7_ng?t=61) function prototype
[2:50](https://youtu.be/Bm1UXzt7_ng?t=170) nested for loops
1. Bugs in code
[3:03](https://youtu.be/Bm1UXzt7_ng) `n1` -> `n2`
[5:49](https://youtu.be/Bm1UXzt7_ng) `arr[k]` -> `arr1[k]`, `arr[l]` -> `arr2[l]`
[12:01](https://youtu.be/Bm1UXzt7_ng?t=721) `len` -> `len[][]`
1. Become more familiar with programming terms in Chinese
1. Wrong example / explanation
[7:24](https://youtu.be/Bm1UXzt7_ng?t=445) Operation reduced is not from multiple non-consecutive subarrays, the correct way explanation of code is : `[1,2,3,4,5]` after `1` is evaluated, as `[1,2,3,4]` is the common subarray, when evaluating `2`, the result from `1` will be carry over.
1. Disable vim error bell
1. Question / Example could be explained better
1. Hesitate less when speaking, stop dragging words when speaking

### Attempt 2 (no interviewer)
> Recording

[237. Delete Node in a Linked List](https://leetcode.com/problems/delete-node-in-a-linked-list/)
1. Find something for interviewer
1. Description not in sync with actions
1. Missed opportunity to slip in additional information
Delete - Remove different use case
How remove without returning reference causes memory leaks
How to deal with memory leaks (Address Sanitizer, Garbage Collector, etc.)
1. [8:32](https://youtu.be/R8dUgL1bRa8?t=512) Elaborate on problems when modifying values of nodes
What will happen when a function do a sneaky change that is not apparent from the name
1. Larger Font

# 同儕檢討
### ****64. Add Binary****

- 可以在每段程式碼前加註解，像27-29行為初始化，可以加註
- 當下沒有解釋C2D實作
- [9:08](https://youtu.be/9wEl1LJ8-Uk?t=548) 解釋要怎麼解決頭是0的情況有點不清楚，重複聽才懂，寫法有點不直觀的感覺
- [9:57](https://youtu.be/9wEl1LJ8-Uk?t=597) 感覺一開始有點沒回答到interviewer的問題，我在聽的時候就一直在等interviewee解釋他的C2D，但沒有很快地給出答案
- [11:30](https://youtu.be/9wEl1LJ8-Uk?t=691) 這段時間滑鼠一直動跟一直移動輸入的地方，會躁起來
- [11:30](https://youtu.be/9wEl1LJ8-Uk?t=691) 迴圈的解釋我覺得沒解釋到甚麼，有點不知道在說甚麼的感覺，可以舉個例子更好
- [12:34](https://youtu.be/9wEl1LJ8-Uk?t=754) 解釋ASCII code我覺得不需要，主考官應該都會知道這些東西
- [13:00](https://youtu.be/9wEl1LJ8-Uk?t=812) 為了給更多解法結果自己卡了，有點太多
- [14:20](https://youtu.be/9wEl1LJ8-Uk?t=859) interviwer說會因為%跟/影響效率，我覺得有點誇張，我沒遇過改進效率是要把除法跟取餘數改成Binary的形式，轉問題的方式我覺得太硬，聽起來很怪，並且interviewee就突然打開畫圖軟件來解釋全加器，有點怪
- code會讓人有背答案的感覺
- 其實整體來說我覺得蠻棒的，說話速度不會太快，打code很舒服

### ****141. Linked List Cycle****
- 講話聲音被鍵盤聲蓋掉很多，加上有口音，沒辦法很好好地聽interviewee說甚麼
- 覺得一開始提出的修改Node的方法可以不用講，因為用這種方法就有點像是你自己修改題目，而不是去想解決方法