---
# System prepended metadata

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

---

---
tags: info2023
---

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者:乾喇 - Ganla
> 🐶：interviewer - Nick
> 🍺 : interviewee

## [27. Remove Element](https://leetcode.com/problems/remove-element/description/)
> [錄影](https://youtu.be/iEurNDtOOZA)
### 模擬面試過程
> 🐶：嗨你好乾喇！我是 Nick ，目前在 XX 部門擔任 XX 職位，今天我有幾個問題想要跟你討論一下，過程中有問題都可以直接發問沒問題的。
> 🍺: 好的。
> 🐶：我們公司是做自然語言處理的，那你應該知道，我們接受到一段輸入的時候，會對裡面的文字做一些前處理，那如果有一些贅字例如 "嗎" 這種會影響語義的詞，那麼我們勢必會對這些輸入做一些刪減，那刪減的同時，我們也想保留這些贅字出現的次數，遇到這種問題你要怎麼解決
> 🍺:(Repeat) 嗯，那我想確認一下我理解的對不對，如果一段文字中，出現了某個特定的字，我們要把它移除並且記錄移除的次數，我可以假設該文字存在一個 `array` 中嗎?
> 🐶：可以呀，你可以對你的文字做任何預設
> 🍺:(Example)那我想再確認一下，移除後文字的排列保持不變對嗎？例如: 我想睡覺，移除"想" 後變成 "我睡覺"
> 🐶：沒錯，你的假設並沒有錯
> 🍺:(Approach)那我會嘗試用這種思路解決，第一個是另外開一個 `array`， `iterate` 輸入數組，如果不是特定的字的話就放進新的 `array` 中，這樣只需要 `iterate` 一次數組，就可以完成
> 🐶：聽起來十分合理，可以的話歡迎把你剛剛思路 code 出來
> 🍺:(Code) 好的，我確認一下，可以使用 python 來解題嗎?
> 🐶：可以的
> 🍺:

```python
    def removeElement(self, nums: List[int], val: int):
        duplicate = 0
        ans = []
        for i in range(0,len(nums)):
            if nums[i] != val:
                ans.append(nums[i])
            else:
                duplicate+=1
                
        return duplicate, ans

```
> 🍺: 這裡我給幾個例子 (自行舉例)，input 以及 output 是這樣 (建表)
> 🐶：你認為這種情況，如果額外開一個 array 紀錄答案，什麼時候會出現問題？
> 🍺: 如果輸入過大的話，那麼額外開一個 array 的開銷可能會讓記憶體配置出現問題，並且因為並不能事前知道新配置的 array 大小，所以每次 append 都會讓 array 長度變動，這樣的配置記憶體動作可能會帶來不小的 overhead
> 🐶：你說的對，那這樣要怎麼改善?
> 🍺: 如果要避免上述情況，那我們可以在同一個數組中做操作，那具體方法呢，我想用一個 index 來記錄要變更的位置，假設要刪除的字跟當前比對的字不同，也就是當前的字不是要刪除的字，那就變更 array 中 index 的字，並且把 index +=1，這樣就可以省記憶體空間的同時，做到刪除指定的字了

```python
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        index = 0
        for i in range(0,len(nums)):
            if nums[i] != val:
                nums[index] = nums[i]
                index+=1
                
        return index
```
> 🍺: 以下我給幾個例子 ...
> 🍺: 回傳 index 有幾個好處，例如我要對原本的數組做刪減，這適用於贅字過多的情況，不然重新配置 array 的記憶體空間也是一個淺在的 overhead
> 🐶：好的，我大致了解你的想法了，這一關你做得很好，我們下一次面試見。
> 🍺: 謝謝你 nick，今天面談很開心，下次見!


## [26. Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/)
> [錄影](https://youtu.be/iEurNDtOOZA&t=610s)
### 模擬面試過程
> 🐶：嗨你好乾喇！我是 Nick，準備好第二次面試了嗎？
> 🍺: 好久不見 Nick，我準備好了!
> 🐶：好那我這邊有一個問題想要問你，還記得上次我提過的贅字刪除嗎，這次是另一種情況，如果今天輸入的句子已經經由轉碼轉乘 ascii ，並且透過 ascii 的排序排好了，那這種情況下，並且我們要的是分析出現過的 ascii ，所以這種情況，不同的 ascii 我只希望保留一個而已，這樣你要怎麼把重複出現的 ascii 刪除？
> 🍺:(Repeat) 好的，那我一樣假設　ascii set 存在 array 中，並且假設他已經轉成對應整數且 sort 過了
> 🍺:我先舉幾個例子，以理解我是否正確，如果有錯在麻煩 nick 糾正我一下
> 🐶：好哇沒問題
> 🍺: (Example) 畫 input output ...
> 🐶：你理解的沒問題
> 🍺: (Approach) 那我想這樣解這題，考慮到有重複的問題，我先用一個變數，我們叫他 tmp 好了，來記錄 array 中的第一個值，那從 index = 1 開始 iterate 這個數組，這個 index 代表下次要更新數組的位置，過程中只要發現 array[index] 中的值和 tmp 不同，那代表他是不重複的值，那麼我們就可以更新該數組中 index 的位置，並且對 index+=1，然後更新 tmp 做為下一個比較對象。
> 🐶： 請你寫出來吧
> 🍺: (Code)
```pyhton
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        tmp = nums[0]
        index = 1
        for i in range(1,len(nums)):
            if tmp != nums[i]:
                nums[index] = nums[i]
                index+=1
                tmp = nums[i]
        return index
```
> 🍺:那以下我給幾個例子來測試我寫的是否正確 ( Test )
> 🐶：那請你分析一下，這個 function 的時間複雜度以及空間複雜度吧
> 🍺:由於只要 iterate 這個 array 一次，假設 array 的大小是 n， 時間複雜度自然是 O(n), 並且因為沒有額外的記憶體配置，所以空間複雜度是 O(1)
> 🐶：好的，看起來沒有問題，我們今天問題就到這裡，下次見!
> 🍺:感謝你 nick，下次見!

## [80. Remove Duplicates from Sorted Array II](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/)
> [錄影](https://youtu.be/QkVf_qgsq_g)
### 模擬面試過程
> 🐶: Hi Good morning Ganla, ready for your final interview?
> 🍺: Absolutely! I'm ready.
> 🐶: So here's the thing: our company deals with natural language processing. Last time, we mentioned that our engineers wanted to find out how many unique ASCII characters are in our input. This time, we want to analyze UTF-8 encoding as our input. We also want to find out how many unique UTF-8 codes are in our input. However, as you know, Mandarin is a special language, and some phrases appear like '走走' or '看看'. When we analyze these inputs, we want to give the repeated UTF-8 codes a second chance. That is to say, each unique element appears at most twice in our input UTF-8 code. OK, the problem description is complete. Is there anything that is unclear?
> 🍺: (Repeat) Ummm, if the given input is (這邊自行舉例), then if one appears more than two times, we remove the excess occurences. In other words, within a single input, each character can appear at most twice. Am I understanding this correctly?
> 🐶: Yes, you understand it correctly.
> 🍺: (Example) (給 input 以及 output 確認)
> 🍺: (Approach) I would like to iterate this string and use a value which calls "flag" to chceck whether a words occurs twice in a row, while iterating the loop, if a unseen word appears, we use a temp value to record it and set flag to 0, and keep iterating, if this value appears again, than we set value flag to 1, and keep iterating, if this value appears once again, because flag's value is 1 which means this value already appears twice in a row, than we remove this element and keep iterating until the repeat element is not in the array.
> 🐶: OK, seems fine, feel free to code it up.
> 🍺: (Code) ...
```python
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:        
        flag = 0
        index = 1
        cmp = nums[0]

        for i in range(1,len(nums)):
            if (cmp == nums[i]):
                if (flag == 0):
                    flag = 1
                    nums[index] = nums[i]
                    index+=1
                    continue

                if (flag != 1):
                    continue
            
            if (cmp != nums[i]):
                flag = 0
                nums[index] = nums[i]
                cmp = nums[i]
                index+=1
                continue
            
        return index
```
> 🍺: (TEST)
> 🐶: Can you anaylize your approach?
> 🍺: In case of time complexity, because we simply iterate this array onece, hence its O(n) if lenght of array if n, and because we did not allocate any memeory to record any other elements in array, thus space complecity is O(1). 
> 🐶: OK! Good job, we end the interview here, thanks for enrolling, if there's other question feel free to contact me anytime, bye.

---

## 他評01
### Interviewer
#### 優點
- 滿有互動感的
#### 可改進的地方
- 切換時常常會有黑頻的問題
### Interviewee
#### 優點
- 畫面清晰乾淨
- 有確認題目的正確姓
#### 可改進的地方
- 可以跟面試官多一點互動