---
# System prepended metadata

title: 2023 年「資訊科技產業專案設計」作業 1

---

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 奇諾-Cino
🧔：interviewer 👶：interviewee
> [中文影片](https://www.youtube.com/watch?v=NSkmwm80SW4)
> [英文影片](https://www.youtube.com/watch?v=t9BU5bpO8jo)

## 面試過程-中文
🧔：你好，感謝你接受敝公司的面試邀請，我看過你的簡歷，你是因為喜歡遊戲進而想要實際參與遊戲開發過程，所以決定來面試敝公司的對吧？
👶：是的，我在大學時期也有嘗試寫過幾個小遊戲。

### [1282. Group the People Given the Group Size They Belong To](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/)
🧔：既然如此，在談及工作內容之前，我們先交流一下在遊戲開發上的想法。以常見的多人匹配系統為例，假設玩家可以自由選擇匹配人數，伺服器端將玩家的人數要求依照提交時間先後順序放入數列當中，你能否做出一個系統讓所有玩家匹配到希望匹配人數的團體中呢？
👶：恩...我先舉個例子，假設我今天拿到：
```
input: [1, 2, 2, 1]
output: [[0], [1, 2], [3]]
```
每個玩家所在的團體的人數等於玩家自己要求的匹配人數對吧？
但是可能出現團體湊不全，或者多重答案。
🧔：形容的很棒，我們就先忽略掉湊不全的問題，你就列出一種答案就好。
👶：好的，那麼我會使用map來解決這個問題。
🧔：請你具體解釋一下。
👶：用key代表要求的匹配人數，value代表group，將玩家一個個放入對應的group當中，一旦滿人了就將group放到result裡面，並清空map原本的group。
🧔：好，那請你實作看看
```cpp
vector<vector<int>> groupThePeople(vector<int> & groupSizes) {
	// map {key = req: value = group}
	map<int, vector<int>> mp;
	// res vector<vector<int>>
	vector<vector<int>> res;
	// for loop
	for (int i = 0; i < groupSizes.size(); i++) {
		// size
		int size = groupSizes[i];
		// add player id into group
		mp[size].push_back(i);
		// if group full
		if (mp[size].size() == size) { // 這行影片中打錯了!!!!
			// add group into result
			res.push_back(mp[size]);
			// group clear
			mp[size].clear();
		}
	}
    return res;
}
```
🧔：我們拿之前你提出的範例來驗證看看吧。
(code tracing...)
🧔：你能評估這段程式碼的時間複雜度和空間複雜度嗎？
👶：時間複雜度是$O(n)$，空間複雜度是$O(n)$
🧔：恩...不太對，c++的map類別是一顆紅黑樹，而不是雜湊函數。
👶：咦?是這麼一回事嗎？那麼時間複雜度應該是$O(nlogn)$才對囉？
🧔：如果你要用雜湊函數，可以試試unordered_map，跟map的差別在於它沒有排序，但是檢索的時間複雜度是$O(1)$。
👶：好的，我會回去查查看。

### [2140. Solving Questions With Brainpower](https://leetcode.com/problems/solving-questions-with-brainpower/description/)
🧔：另外還想問你一個關於遊戲數值規劃的問題，現今的遊戲常常推出限定活動道具，假設公司設計好一整季的活動安排，每個活動所能獲取的資源量都相等，但限定道具的取得成本不一，價值(強度等等)也不一，玩家可以預付資源取得道具，但是在還清成本之前不能再次取得道具，公司想用一套系統去計算每種活動安排最大可獲得的價值，對此你有甚麼看法。
👶：既然每個活動的資源量都相同，那就以此為標準化單位假設:
```
input = [(1, 2), (3, 4), …]
output = the most gain can get
```
每次活動都可以選擇取得道具或跳過道具，一旦選擇取得道具就要跳過相應的活動次數。這樣設計的邏輯你覺得如何。
🧔：恩，差不多是這樣。
👶：既然如此，每次活動都有兩個分支，利用遞迴函數function去比較兩種選擇的優劣，函數回傳在該次活動之後所能得到的最大價值(gain)，如此一來function(0)就會是答案了。
🧔：好，那請你把它實作出來。
```cpp
long long innerFunction(vector<vector<int>> & events, int e, int N) {
    // end if e not in events
    if (e >= N) {
        return 0;
    }
    // compare buy or skip
    long long point = max(events[e][0] + innerFunction(events, e + events[e][1] + 1, N), 
                            innerFunction(events, e + 1, N));
    //return
    return point;
}

long long mostPoints(vector<vector<int>> & events) {
    // call function(0)
    return innerFunction(events, 0, events.size());
}
```
🧔：但是你這個程式碼當i越大，被重複計算越多次，你有甚麼解決方法嗎？
👶：既然每次計算f(i)都不會改變回傳值，不如分配一個空間將f(i)的結果儲存起來，重複讀取就好了吧。
🧔：聽起來你似乎有想法了。但這邊我有個建議，你有辦法將遞迴給拿掉嗎？
👶：有趣，所有的回傳值都是由後面活動推導而出的，那不然乾脆從最後一個活動計算起。
🧔：你試著寫寫看。
```cpp
long long getMostPoint(vector<vector<int>> & events) {
	int N = events.size();
	// dp [index = event, value = mostpoint]
	long long* dp = new long long[N+1] ();
	// for
	for (int i = N -1; i >= 0; i--) {
		//compare buy or skip
		dp[i] = max(events[i][0] + dp[min(i+events[i][1]+1, N], dp[i+1]);
	}
	return dp[0];
}

```
👶：如此一來，時間複雜度就從原本的$O(2^n)$降到$O(n)$。空間複雜度看似變成$O(n)$，但考慮到每次遞迴的空間成本，之前的程式碼甚至可能stack overflow。
🧔：恩，時間也差不多了，很高興能和你討論這些議題，也還請留意一下電子信箱，如果有需要你參加第二次面試，我們會在下星期通知你，祝你有個美好的假期。
👶：我也十分樂在其中，也感謝貴公司給了我這次的機會，期待貴公司的通知。
## 面試過程-英文
### [9. Palindrome Number](https://leetcode.com/problems/palindrome-number/description/)
🧔：Hello, welcome to the interview.I'm Brid, a software engineer. Nice to meet you.
👶：Hi, I'm Cino, a new graduate from National Cheng Kong University. Nice to meet you too. 
🧔：Okay, let's start our discussion. Do you know palindrome numbers?
👶：Uh...I'm not quite sure. Can you give me an example?
🧔：Okay, palindrome means the words that reads the same backwards and forwards.
👶：Do you mean like racecar or rotator?
🧔：Yes, you got it. So, palindrome numbers are the number which are palindrome, like 11 or 121.
👶：But how about negative numbers?
🧔：That a good question. Negative numbers are not palindrome number because minus sign doesn't exist at the end of the number.
👶：Okay. I got the point.
🧔：Today, you need to create a function which parameter is an integer x, and the function has to return true or false depands on whether integer x is a palindrome number or not. Any questions?
👶：Uh..., so if I input a number 121, it will return true, right?
🧔：Yes, of course.
👶：And if I input 123, it return false.
🧔：Absolutely.
👶：Okay, in this case, I will try to convert the input to string first. Then, I can use two pointers to compare front and bottom charactors. If they are different, I will return false, otherwise, the pointers will step close to the middle, and compare the charactors again.
🧔：Sounds great. Let's start coding.
```cpp
bool isPalindrome(int x) {
	// convert x to string
	string str = x.to_string();
	// imple right, left
	int right = str.size() - 1, left = 0;
	// compare
	while (left < right) {
		if (str[left] != str[right])
			return false;
		left ++;
		right --;
	}
	return true;
}

```
👶：Let's make an example. If I input 12321 into the fuction, then...
👶：And the time complexity is $O(n)$, space complexity is $O(n)$ since we create a copy string of x.
🧔：It do work, but I think there is a possible way to remove the converting, can you try it?
👶：Okay, maybe we can create an integer 'y', then copy unit digits one by one to 'y', after copying the while digits of x, 'y' will become the reverse of x.
```cpp
bool isPalindrome(int x) {
	// convert x to string
	string str = x.to_string();
	// imple right, left
	int right = str.size() - 1, left = 0;
	// compare
	while (left < right) {
		if (str[left] != str[right])
			return false;
		left ++;
		right --;
	}
	return true;
}

```
🧔：Well done, and that the whole interveiw today. Keep an eye out for the schedule of the next interveiw. Hope your have a nice day.
👶：Thank you, you too.

---

## 第二次作業-他評01
### Interviewer
- [ ] 優點
[0:00](https://www.youtube.com/watch?v=NSkmwm80SW4?t=0): 在開頭的地方很尊重面試者，和面試者小聊一下也是面試中認識一個人重要的環節，面試模擬這樣感覺也比較真實。
[0:24](https://www.youtube.com/watch?v=NSkmwm80SW4?t=24): 將題目包裝成實際應用不使用原題 讚

- [ ] 可以改進的部分
[12:05](https://www.youtube.com/watch?v=NSkmwm80SW4?t=605): 這邊既然提到unordered map，其實可以繼續問說在本題的情況下，剛剛你是用map實作，現在有了unordered map你會在兩者之間選擇哪種作法? 考量的點是什麼? 

### Interviewee
- [ ] 優點
* Reacto做得詳細
* 先利用comment部分說明自己的想法approach，在實際寫code的方式值得學習
* [5:13](https://www.youtube.com/watch?v=NSkmwm80SW4?t=313): 編寫程式邊說明做的很棒，不會只念自己在打的東西
* 實作速度快

- [ ] 可以改進的部分:
* [13:51](https://www.youtube.com/watch?v=NSkmwm80SW4?t=831): 問完「對不對」應該給面試官時間確認理解是否正確。

## 第二次作業-他評02
### Interviewer
- [ ] 優點
* 出題包裝很用心，擬真實際面試情境
* 和 interviewee 的對談和問題討論都展現出面試「溝通」的本質，不會很像考試，而像在針對該情境交換想法

### Interviewee
- [ ] 優點
* 解題節奏很快且通順，先註記再完成程式的方法很棒
* 能夠一邊寫程式一邊講解，中間幾乎沒有卡住，讓人很享受解題過程

- [ ] 可以改進的部分
* 第二題直接使用 long long 去定義，範圍可以先問 interviewer 取得

## 第二次作業-他評03
### Interviewer
- [ ] 優點
* 從實際的應用情境描述出題很棒，不只考驗面試者解決問題的能力，還能測試面試者定義問題的能力
* 引導面試者進行 REACTO 的流程很棒

### Interviewee
- [ ] 優點
* 解題過程流暢，能夠一邊撰寫程式碼，一邊解釋自己的想法
* 口齒清晰、語速適中
* 在討論 map/unordered_map 的複雜度時，在被面試官糾正後，能夠及時反應，並給出正確答案，顯示面試者具有臨場反應能力
- [ ] 可以改進的部分
* 在 Google Docs 上使用 Arial 字型呈現程式碼看起來較為凌亂不易閱讀，可以加上一些空行，並改用其他等寬字型如 Roboto Mono、Comfortaa、Verdana
* 第三題似乎想嘗試使用註解寫 pseudocode 來解釋想法，但寫得太像程式碼，有太多不必要的細節，應該聚焦在更高層次的想法