# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 毛氈苔-Sundew
> 影片: [第一題(漢語)](https://www.youtube.com/watch?v=9sIqcF-WjIk)
> 影片: [第二題(英語)](https://www.youtube.com/watch?v=74lfAdLQGbQ)
> 影片: [第三題(漢語)](https://www.youtube.com/watch?v=wooQhV0scPo)
> 🐇:Interviewee
> 🧔:Interviewer
## 125. Valid Palindrome
**面試過程**
🧔: 歡迎來到我們公司面試，等你準備好後就開始吧!
🐇: OK 我準備好了
🧔: 你收到的題目是關於Palindrome，中文稱為回文，那你要做的事情是接收一個String然後判斷他是不是Palindrome
🐇: "看題目敘述+重新講述題目"
🧔: 沒錯喔!
🐇: OK 大概了解了，那最直覺想到的作法是使用額外的空間去反轉字串，接著從字串起點一一比較
> 影片: [第一題(漢語)](https://www.youtube.com/watch?v=9sIqcF-WjIk)
```cpp
/// Solution 1
bool Solver(string input)
{
if(input.size()==0)
return true;
string reverse_s = "";
//reverse string time O(n), space O(n)
for(int i=input.size()-1;i>=0;--i)
{
reverse_s+=input[i];
}
//i => input
//j => reverse_s
//a,,a_ => input
//_a,,a => reverse_s
//O(n)
for(int i=0,j=0;i<input.size()&&j<reverse_s.size();++i,++j)
{
while(i<input.size()&& !isalnum(input[i]))++i;
while(j<reverse_s.size()&&!isalnum(reverse_s[j])++j;
//not palindrome
if(tolower(input[i])!=tolower(reverse_s[j]))
return false;
}
//time O(n), space O(n)
return true;
}
```
🧔: 那你可以改成不用額外的空間嗎? 不只增加時間O(n)外也多使用O(n)的空間了
🐇: 好的，那我會改變的方式是比較的方式，不是從字串的起點，而是從前與後做比較，直到i>=j為止
🐇: 那時間複雜度一樣是O(n), 但空間複雜度就變成O(1)了
```cpp
//solution 2
bool Solver(string input)
{
if(input.size()==0)
return true;
//i => input
//a,,a_ => input
//O(n)
for(int i=0,j=input.size()-1;i<j;++i,--j)
{
//,_a
//a_,
// j
// i
while(i<j&& !isalnum(input[i]))++i;
while(i<j&&!isalnum(input[j])--jj;
//not palindrome
if(tolower(input[i])!=tolower(input[j]))
return false;
}
//time O(n)
return true;
}
```
## 21. Merge Two Sorted Lists
> 影片: [第二題(英語)](https://www.youtube.com/watch?v=74lfAdLQGbQ)
>
🧔:Hi, I am **David**, welcome to our company for interview. I will give you a question about "Merge two sorted list". Because we often need to sort up customer's data, I want you to deal with the already sorted data.
🐇: OK. thanks David, I am ready now.
🧔: Great, as you can see from the google doc, the input always be **sorted list**. In this case, you only need to merge two sorted list. Given the input "1,2,4" and "1,3,5" will return "1,1,2,3,4,5".
🐇: q1 about empty list, q2 about has to be same order?
🧔: q1 not gonna happen, q2 don't need to care about.
🐇: My naive thought will be try to merge list2 into list1 by checking list1's value over and over again. which can be simply time O(n^2), because we try to use insertion sort to insert the list2 value into list1.
🐇:So my second though will be using Head&Rear solution I called it. it's just simple linked-list.
```cpp
//Part 1
class ListNode{
public:
int val;
ListNode* next;
}
ListNode* Merge2SortedList(ListNode* list1, ListNode* list2)
{
//no empty list
ListNode* dummy = new ListNode();
ListNode* tail = dummy;
while(list1&&list2)
{
if(list1->val<=list2->val)
{
tail->next = list1;
list1 = list1->next;
}
else
{
tail->next = list2;
list2 = list2->next;
}
}
//because two list size maybe different
if(list1)
{
tail->next= list1;
}
if(list2)
{
tail->next = list2;
}
//m equal to list1 size
//n equal to list2 size
//time O(m+n), space O(1)
return dummy->next;
}
```
🧔: OK, I think your solution is great. But I want to give a more interesting question, But ours time is limited, just try to answer it by your thought.
The follow up question is Try to merge with k sorted list.
🐇: ehhh, my naive apporach will try to use merged sort. Because we had done a question about merged two sorted list, and using merged sort time complexity is O(nlogn). But using merged sort will have side effect that is additional stack space and spend constant time at merge.
```cpp
//second part
//
list1 = [1,2,4], list2 = [1,3,4], list3 = [3], list4 = [5]
return = [1,1,2,3,3,4,4]
list1_2 = [1,1,2,3,4,4]
list3_4 = [3,5]
[1,1,2,3,3,4,4,5]
ListNode* Merge2SortedList(ListNode* list1, ListNode* list2)
{
//no empty list
if(!list1)
{
return list2;
}
if(!list2)
return list1;
ListNode* dummy = new ListNode();
ListNode* tail = dummy;
while(list1&&list2)
{
if(list1->val<=list2->val)
{
tail->next = list1;
list1 = list1->next;
}
else
{
tail->next = list2;
list2 = list2->next;
}
}
//because two list size maybe different
if(list1)
{
tail->next= list1;
}
if(list2)
{
tail->next = list2;
}
//m equal to list1 size
//n equal to list2 size
//time O(m+n), space O(1)
tail =dummy->next;
delete dummy;
return tail ;
}
ListNode* Merge(vector<ListNode*>& Lists,int left,int right)
{
if(right-left==0)
{
return Lists[left];
}
int mid = (left+right)/2;
//Left side merge
ListNode* LeftLists = Merge(Lists,left,mid);
//right side merge
ListNode* RightLists = Merge(Lists,mid+1,right);
return Merge2SortedList(LeftLists,RightLists);
}
ListNode* MergedKLists(vector<ListNode*>& Lists)
{
if(Lists.size()==0)
return nullptr;
return Merge(Lists,0,Lists.size()-1);
}
//Lists[0],Lists[1].size() =n
//time nklog(k), space (logk)
```
## 74. Search a 2D Matrix
> 影片: [第三題(漢語)](https://www.youtube.com/watch?v=wooQhV0scPo)
🧔: Hi Sundew, 等等你的電腦應該會收到一份共用的Google Doc, 我們接下來會在這份文件上嘗試去解Coding problem，你準備好後我會跟你說明題目
🐇: OK
🧔: OK，你的題目是Search target in 2D Matrix, 我希望你幫我確認Target Element是否存在於Matrix之中。每個Row都是已經Sorted過的Array，那input也保證每一個row的第一個數字比前一個row的最後一個數字來的大, 所以可以看到範例的樣子... 但我們想要你能在Big o(log(m\*n))的時間
🐇: 好，我大致上了解，那我想在確保我了解題目，所以我們的目的就是在這個每個Row已經Sorted的情況下，以及每個Row的第一個數字一定大於在他前面的每一個row的最後一個數字對嗎，所以就是Column本身也算Sort過
🧔: 沒錯，你可以這麼了解
🐇: OK 那我想先說一下最直覺的想法就是暴力解，先Loop 每個Row的第一個元素，找出值會落在哪個Row上，接著再去loop 這個Row的每個元素去找出是不是存在。 那時間複雜度就會是O(n+m) 因為最糟就是要走m再走n 但這樣線性的搜尋不符合要求所以我想到的是使用Binary search
🧔: 那你要實作看看Binary search的作法嗎
🐇: 沒問題 我馬上開始
```cpp
bool Search2DMatrix(vector<vector<int>>& input,int target)
{
int left = 0,right = input.size()-1;
int mid_row = (left+right)/2;
while(left<=right)
{
if(input[mid_row][0] == target)
return true;
else if(target>input[mid_row][0])
{
left = mid_row+1;
}
else
{
right = mid_row-1;
}
mid_row = (left+right)/2;
}
//row_index
left = 0,right = input[mid_row].size()-1;
int mid_col = (left+right)/2;
while(left<=right)
{
if(input[mid_row][mid_col] == target)
return true;
else if(target>input[mid_row][mid_col])
{
left = mid_col+1;
}
else
{
right = mid_col-1;
}
mid_col= (left+right)/2;
}
//time O(log(m)+log(n)) = O(log(m*n))
//space O(1)
return false;
}
```
🐇: 時間複雜度的話是log(m)+log(n) 所以會是log(m\*n)的複雜度。
🧔: OK 聽起來沒問題，但你可以精簡你的程式碼嗎，讓它更好讀一點。
🐇: 沒問題，我會從計算mid的方式改變
```cpp
bool Search2DMatrix(vector<vector<int>>& input,int target)
{
int n = input[0].size();
int m = input.size();
int left = 0,right = m*n-1;
int mid = (left+right)/2;
int mid_row = mid/n;
int mid_col = mid%n;
while(left<=right)
{
if(input[mid_row][mid_col] == target)
return true;
else if(target>input[mid_row][mid_col])
{
left = mid+1;
}
else
{
right = mid-1;
}
mid = (left+right)/2;
mid_row = mid/n;
mid_col = mid%n;
}
return false;
}
```
🧔: OK，雖然中間都有一些typo，但還是OK的。
🐇: 謝謝! 掰掰
## 初步檢討
- 拜託，英文口說加油==
- 面試官其實沒甚麼用，應該要完整說明題目，並在過程適時引導(因為我錄發現我卡住其實都是重錄(第一題很明顯，但第二跟三認為這樣不叫做有練習與誠實面對自己))
- 雖然都有按照REACTO的方式，但在撰寫程式碼過程其實會忘記當初怎麼表達的。
- 解釋事情上必須在更努力，要練習精簡(Concise)
- 多練習解題(都只有做在校專案而已)
- 過多比手畫腳
## 改善方案
- 利用機會與人溝通，表達清楚自己想講的
- 英文口說.....
- 多練習解題，只透過學校是不夠的
- 在解釋事情時可以直接寫在google doc上，不用一直比手畫腳
---
## 第二次作業-他評 01
### interviewer
- [ ] 優點
* 咬字清楚
* 有延伸題目到不同的情境
- [ ] 可改進地方:
* 可能需要將題目轉換一下，才不會讓interviewer一聽到關鍵字就知道今天要考的題目是什麼
### interviewee
- [ ] 優點
* 註解很清楚
* 咬字清楚
* 打字速度快
- [ ] 可改進地方:
* 第一題的第一個解法，將字串翻轉後直接比對兩字串是否相同即可`return input == reverse_s`
* isalnum的用法可能要與interviewer做一下簡短的說明
* 第二題的部分程式可以更精簡:
```cpp
if (list1) {
tail->next = list1;
}
if (list2) {
tail->next = list2;
}
// 上面的兩個 if 敘述可以改成:
tail->next = list1 ? list1 : list2;
```
* 第三題程式碼可再精簡
```cpp
bool Search2DMatrix(vector<vector<int>> &input, int target)
{
int n = input[0].size();
int m = input.size();
int left = 0,right = m * n - 1;
int mid, mid_row, mid_col;
while (left <= right) {
mid = (left + right) / 2;
mid_row = mid / n;
mid_col = mid % n;
if (input[mid_row][mid_col] == target)
return true;
if (target > input[mid_row][mid_col]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
```
Sign in with Wallet
Connect another wallet