owned this note
owned this note
Published
Linked with GitHub
# info2024-homework1
> 歐麥-Allmine
> R : Interviewer, E : Interviewee
> [模擬面試錄影: 英 1](https://youtu.be/JCztkkCTC5s)
> [模擬面試錄影: 中 2](https://youtu.be/HHSPSIeEaHw)
> [模擬面試錄影: 中 3](https://youtu.be/Lf1-rIJ7Paw)
# [LC 977. Squares of a Sorted Array (Easy)](https://leetcode.com/problems/squares-of-a-sorted-array/description/)
> Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
## 面試過程
R: Thank you for joining this interview. We noticed your expertise in classic algorithms and would like to discuss their applications with you. Given your background in communications, we often calculate SINR (信雜比) by squaring the absolute values of channel fading gain to determine user signal power. With equal transmission power, sorting these squared values helps us compare signal quality among users.
Please address the problem in the shared Google Docs. Feel free to ask any questions.
E: Sure, could you please clarify what kind of input I'll be working with?
R: You can assume that the starting address of an integer array and the size of the array are given.
Also, the size of the returned array should be stored in the variable pointed to by returnSize.
`int* sortedSquares(int* nums, int numsSize, int* returnSize) {...}`
E: Ok,so the input is an sorted array, and the ouput is the sorted squared arry, is that correct?
R: Yes
E: Do I need to consider the case where numsSize is zero?
R: No, you can assume that numsSize will always be greater than 1.
E: Got it. Let me go through this problem with an example.
If the input is a sorted array like `[-1, 0, 3, 4]`, after squaring each element and sorting them, the output should be `[0, 1, 9, 16]`.
Is that correct?
R: Yeah, that's exactly right.
E: So my initial approach is to use a for loop to square each element in the array, and then apply a sorting algorithm like quicksort to sort the squared values
R: That sounds reasonable, can you analyze the time and space complexity of this approach?
E: Sure. The for loop takes O(n) time to sqare each element, and the quicksort algorithm takes O(nlgn) time to sort.Hence the total time complexity is O(n+nlgn).
For space complexity, only quicksort takes average space complexiy of O(lgns).
R: Well, can you propose a solution with O(n) in time complexity
E: Sure, I would use a two-pointer technique for this. Since the largest squared value would be at either end of the array, the main idea is to use left and right pointers. We compare the squared values of elements at these pointers, and place the larger one at the end of the result array. We then move the pointer inward accordingly.
R: OK, please go ahead and implement this approach
E:
```c==
int* sortedSquares(int* nums, int numsSize, int* returnSize)
{
*returnSize = numsSize;
int* ans = malloc(numsSize * sizeof(int));
int left = 0;
int right = numsSize - 1;
for (int i = numsSize - 1; i >= 0; i--)
{
int l_square = nums[left] * nums[left];
int r_square = nums[right] * nums[right];
if (r_square >= l_square)
{
ans[i] = r_square;
right--;
}
if (r_square < l_square)
{
ans[i] = l_square;
left++;
}
}
return ans;
}
```
R: Good. Can you perform some test cases to verify your solution?
E: (測試測資)
R: Great job! This brings us to the end of the interview. Thank you for your time and effort.
# [LC 206. Reverse Linked List (easy)](https://leetcode.com/problems/reverse-linked-list/description/)
> Given the “head” of a singly linked list, reverse the list, and return the reversed list.
## 面試過程
R: 感謝你的時間，接下來由我主持這場面試。我注意到您的成績單上顯示修過資料結構和實作經驗，相信對**鏈結串列**相當熟悉。今天我們將實作一個瀏覽器的瀏覽歷史功能，並使用鏈結串列來儲存瀏覽紀錄。透過反轉鏈結串列，可以實現回到上一頁的操作。因此，藉此機會與你探討這個題目。請您在事先分享的 Google Docs 上進行回答，如果在過程中有任何想法或疑問，請隨時記錄下來方便後續討論。
E: 好, 我想問一下只需考慮單向的鏈結串列嗎?
R: 考慮單向的就好。
E: 好, 那我想簡單帶個例子, 如果輸入的linked list是`[1,2,3]`, 經反轉後輸出為`[3,2,1]`, 這樣的理解正確嗎?
R: 沒錯, 同時提醒一下, 輸入的linked list可能為空
E: 好, 我的想法是採用雙指針pre和cur持續右移, 直到cur為NULL, 就可以回傳pre。
R: 恩, 你的方法聽起來沒有太大的問題
E: 那我接著實現這部分的程式碼,
```c==
struct ListNode
{
int val;
struct ListNode* next;
}
struct ListNode* reverList( struct ListNode* head)
{
struct ListNode* cur = head, *pre = NULL, *temp;
while(cur)
{
temp = cur->next;
cur->next = pre;
pre=cur;
cur=temp;
}
return pre;
}
```
R: 可以請你用測資測試一下嗎?
E: (test case)
R: 想請問一下這個方法的時間和空間複雜度?
E: 時間複雜度是O(n),因為cur必須走完整個linked list；
而空間複雜度是O(1), 因為不需要額外的空間
R: 恩, 那還有時間複雜度同等級的解法嗎?
E: 有, 可以使用遞迴的方式
```c==
struct listnode
{
int val;
struct listnode* next;
}
struct ListNode* reverse( struct ListNode * pre, struct ListNode* cur)
{
if(cur==NULL) return pre;
struct ListNode* temp = cur->next;
cur->next = pre;
reverse(cur,temp);
}
struct ListNode* reverseList( struct ListNode* head)
{
struct ListNode* cur = head;
return reverse(NULL,cur)
}
```
R: 好的, 今天的面試到這邊結束, 謝謝你的參與。
# [LC 24. Swap Nodes in Pairs (medium)](https://leetcode.com/problems/swap-nodes-in-pairs/description/)
## 面試過程
R: 感謝您的時間，接下來由我來主持這場面試。我注意到您的履歷上有通信網路的修課紀錄，今天我們將模擬一個網路數據傳輸的系統，數據以鏈結串列的形式儲存，每個節點代表一個數據包。由於某些網路協議會交換相鄰數據包順序來檢查網路延遲或糾正錯誤，我們需要實作一個功能來交換兩兩相鄰的數據包節點，並確保數據的完整性。藉此機會與您交流，請您在事先分享的 Google Docs 上進行回答，過程中如果有任何想法或疑問，請隨時記錄下來以便後續討論。
E: 想問一下,如果是奇數個節點, 最後一個節點位置需要更動嗎 ?
R: 不用, 僅需交換偶數個相鄰的節點。
E: 好的, 如果輸入的鏈結串列是`[1,2,3]`, 則輸出應該要為`[2,1,3]`, 這樣的理解正確嗎?
R: 對的
E: 以intput `[1,2,3]`為例子,我的想法是宣告一個dummy node在頭節點前面,統一化交換節點的操作,然後宣告一個cur變數指向dummy node,cur右方的兩個節點一組,進行交換,並在交換完成後,將cur右移兩個node交換下一組node。
如果遇到偶數個節點，當cur->next等於NULL停止,若是奇數個節點則當cur->next->next等於NULL,就可以停止,並回傳交換完成後的頭節點。
R: 聽起來沒有太大的問題, 可以請你實作你的想法嗎
E:
```c==
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head) {
typedef struct ListNode ListNode;
ListNode* dummy = malloc(sizeof(ListNode));
dummy->next = head;
ListNode* cur = dummy,*temp1;
while(cur->next!=NULL && cur->next->next!=NULL)
{
temp1 = cur->next;
cur->next = cur->next->next;
temp1->next = temp1->next->next;
cur->next->next = temp1;
cur = temp1;
}
head = dummy->next;
free(dummy);
return head;
}
```
**分析複雜度**
時間複雜度:O(n), 空間複雜度:O(1)
R: 方便請你用測資說明程式碼如何運行嗎?
E: (測試測資)
R: 聽起來沒有什麼問題, 那你有辦法用遞迴的方式來寫這題嗎?
E: 可以，遞迴的邏輯跟原本迭代差不多，但因為遞迴能自動更新頭節點，因此不須額外宣告一個dummy node
```c==
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head) {
typedef struct ListNode ListNode;
if(head == NULL || head->next==NULL) return head;
ListNode* temp2 = head->next;
head->next = swapPairs(temp2->next);
temp2->next = head;
return temp2;
}
```
R: 好的,今天的面試到這邊結束,感謝你的時間.
---
# 初步自評
- [ ] 針對 interviewer 的檢討:
* 共同問題
* 一句話講太久才換氣, 聽起來會有點壓迫
* 三題測試題, 題目包裝不夠
* 在interviewee實作時, interviewer沒有任何的提示或引導
* Linked-list 鏈結串 "**列**", 有時發成串"**鍊**"，時而咬字不夠清楚 (interviewee也有同問題)
* 英文1
* [4:28](https://youtu.be/JCztkkCTC5s?t=268) 應該請interviewer針對qsort, 解釋時間和空間複雜度, 聽起來很像是用背的
- [ ] 針對 interviewee 的檢討:
* 共同問題
* 不必要的手勢有點多...
* 發音習慣將重音放在最後,例如`input/output`的`t`應該為氣音, 需改進, 例: current [[ˈkʌr.ənt](https://dictionary.cambridge.org/zht/%E8%A9%9E%E5%85%B8/%E8%8B%B1%E8%AA%9E-%E6%BC%A2%E8%AA%9E-%E7%B9%81%E9%AB%94/current)], temp [[temp](https://dictionary.cambridge.org/zht/%E8%A9%9E%E5%85%B8/%E8%8B%B1%E8%AA%9E-%E6%BC%A2%E8%AA%9E-%E7%B9%81%E9%AB%94/temp)], next [[nekst](https://dictionary.cambridge.org/zht/%E8%A9%9E%E5%85%B8/%E8%8B%B1%E8%AA%9E-%E6%BC%A2%E8%AA%9E-%E7%B9%81%E9%AB%94/next)], etc.
* [英文1](https://youtu.be/JCztkkCTC5s)
* 英語對話不熟練, 太多次贅詞, 例: so
* [2:41](https://youtu.be/JCztkkCTC5s?t=161) 在說明approach同時, 應該用pseudo code撰寫程式邏輯, 代替只用comment
* [7:25](https://youtu.be/JCztkkCTC5s?t=445), [7:55](https://youtu.be/JCztkkCTC5s?t=475) 是 move "**inward**", 不是 "**inwardly**"
* [中文2](https://youtu.be/HHSPSIeEaHw)
* [1:14](https://youtu.be/HHSPSIeEaHw?t=74) NULL的發音應為 [[nʌl](https://dictionary.cambridge.org/zht/%E7%99%BC%E9%9F%B3/%E8%8B%B1%E8%AA%9E/null)]
* [2:01](https://youtu.be/HHSPSIeEaHw?t=121) 用`temp`儲存`cur->next`的 "**節點**", 而非 "**位置**"
* [4:30](https://youtu.be/HHSPSIeEaHw?t=270) `pre`移動到`cur` "**指向的節點**"，而非移動到`cur` "**的位置**"，同理 [4:35](https://youtu.be/HHSPSIeEaHw?t=275) 移動到`temp` "**指向的節點**"
* [8:25](https://youtu.be/HHSPSIeEaHw?t=505) 不應該說 "一路跑到最後的 `NULL`", 改成 "`cur` **持續右移存取整個鏈結串列的節點**"
* [中文3](https://youtu.be/Lf1-rIJ7Paw)
* [1:26](https://youtu.be/Lf1-rIJ7Paw?t=86) NULL的發音應為 [[nʌl](https://dictionary.cambridge.org/zht/%E7%99%BC%E9%9F%B3/%E8%8B%B1%E8%AA%9E/null)]
* [4:14](https://youtu.be/Lf1-rIJ7Paw?t=254) 說明完初步approach後, 應該再補上pseudo code, 寫下程式碼的運行邏輯
* [13:35](https://youtu.be/Lf1-rIJ7Paw?t=815) 文字敘述錯誤,應說明 "如果傳入**指針為空**`NULL`" , 而不是傳入 "**空集合**"
* [14:48](https://youtu.be/Lf1-rIJ7Paw?t=888) 應寫作`swap(3)=3`才符合`swap(3)等於3`的意思
Google Drive
Gist
Clipboard
Sign in with Wallet
