# 資訊科技產業專案設計 第二次作業
Written by `tardyon / 筆較慢`
:::warning
Youtube 的內建編輯器的模糊區域在 cut 的時候會緩慢移動而不是跳過去，不能用。
deface 會把聲音全部消除，要自己再從原影片提取補上
目前作法：
+ 利用 deface 生成 720p 的匿名影片(為了速度而降低畫質，6hrs -> 2hrs)
- `deface --scale 1280x720 <filename>`
+ 用 VLC Media Player 提取原影片的音軌
+ 用 Windows 內建的影片編輯器合併
:::
## 英語部分
:::info
不太確定該不該這麼做，總之還是先寫了台本。
Interviewee 的部分由於比較長，應該跟這邊寫的差了一些
<div style="width: 98%; height: 5px; background-color: #DFDFDF; margin:5px auto; border-radius: 3px; box-shadow: inset 1px 1px 1px #CCCCCC;"></div>
**Interviewer** = :male-teacher:
**Interviewee** = :evergreen_tree:
:::
### Problem 26. Remove Duplicates from Sorted Array
:male-teacher: **Hello, Tard. Welcome to the interview. There will be three problems. Here we go.**
:male-teacher: **So, here's your question: Given a sorted array of integers, eliminate all duplicate entries, return the shorten array.**
:evergreen_tree: Eliminate duplicates in the sorted array and return. Okay. So, for example, if the input is [1, 2, 2, 4, 4], I should return an array of length 3, which containes [1, 2, 4].
:male-teacher: **You're correct.**
:evergreen_tree: May I ask the range of the entries, and what is the maximum size of the array?
:male-teacher: **The entries will land from -100 to 100, and the maximum size of the array is 30,000 entries.**
:evergreen_tree: Got it. So, as a start, I would try to code it in the most naive way, just scan the array and detect duplicates, and copying the values to a new array. Can I assume that the memory is enough for me to declair an array with a length of 30,000 integers?
:male-teacher: **Well, why not? Sure you can.**
:evergreen_tree: Nice. So this is what I am going to do: First, create a array that is the same size as the input array. Then, scan through the array and detect the duplicates. As long as they are not duplicates, I will add it to the new array.
:male-teacher: **Okay. Can you describe how do you detect duplicates?**
:evergreen_tree: Since the given array is sorted, we know that any duplicates will be contiguous. So, the variable here, called `???`, memories the latest newest entry on the scan. If the current scanning is same as the variable, we know its a duplicate.
:male-teacher: **Seems simple, can you code it up?**
:evergreen_tree: Sure.
```c=
int *rmvdup(int *num, int size){
int ret = calloc(size, sizeof(int));
int next = 0, rem = -101;
for(int i = 0; i < size; ++i){
if(num[i] != rem){
rem = num[i];
ret[next++] = num[i];
}
}
return ret;
}
```
I think this would work. This solution, say `n` is the length of the input array, the time complexity is linear and so is the space complexity, both `O(n)`.
:male-teacher: **Simple and short. But for this kind of simple tasks, it seems quite inefficient to allocate such a huge memory. Do you think you can just modify the input array, that is passed as a pointer?**
:evergreen_tree: Then how would I deal with the vacancy space?
:male-teacher: **Push to the front. You don't need to care what the unused slots contains.**
:evergreen_tree: So, for the example input [1, 2, 2, 4, 4], I should modifu the array's first three entry to [1, 2, 4].
:male-teacher: **Right.**
:evergreen_tree: I think I can do it. So, I think its apparent that all of the remaining entries would either stay at the same place, or be shifted to the left. Also, the number of entries we removes equals to the shift length.
:male-teacher: **Makes sense.**
:evergreen_tree: So heres what I will do. First, Scan the array from the first entry, using the same memorizing technique to find duplicates. Whenever we find a duplicate, add 1 to the shift lengh -- So there has to be a variable tracking this, starting with zero.
:male-teacher: **Go on.**
:evergreen_tree: The shift length of each entry is identicle to how many entries had been eliminated before this entry. So, in each loop interation, we'll assume the next entry is not a duplicate, shift to its proper location, then examine it.
This way, the time complexity, is still `O(n)`, but the space complexity is now `O(1)`, only declairing these two integers and the loop variable.
:male-teacher: **Good, you did a great job. Lets move on to the next question.**
### Problem 190. Reverse Bits
:male-teacher: **Heres the second problem: Write a funtion so that, given a integer, reverse the bits, and return it. Thats all.**
:evergreen_tree: Okay, can I assume the said integer is a typical 32-bit integer?
:male-teacher: **Yes, you can.**
:evergreen_tree: Is the integer signed or unsigned?
:male-teacher: **Unsigned. In fact, please set the function so that the input and output both is a unsigned 32-bit integer.**
:evergreen_tree: Roger. So for this problem, my first thought is to treat it like reversing an array. So, swap the firt and the last, swap the second and second to the last, and so on.
:male-teacher: **It sure is doable for an array, but how would you deal with single bits?**
:evergreen_tree: I can use the bit-wise and operator to mask the bits I need, and shift it all around, joining it with the or operator.
:male-teacher: **Good. Do you think you can code it up?**
:evergreen_tree: Sure .
```c=
uint32_t reverse_bit(uint32_t n){
uint32_t ret = 0;
for(int i = 0; i < 16; ++i){
ret |= n & ((uint32_t)0x00000001 << i) << (((16 - i) << 1) - 1);
ret |= n & ((uint32_t)0x80000000 >> i) >> ((i << 1) - 1);
}
return ret;
}
```
I think I've done it. this solution works at `O(1)` time complexity and space complexity.
:male-teacher: **Well done, you've solve it. However, can you optimize it more, assuming this function will be calledenourmous amount of time?**
:evergreen_tree: Let me think about it. So I have to think of some constant time improvements.
:male-teacher: **Correct.**
:evergreen_tree: Well then, I would first try to break it down into smaller questions. Assuming the question is reversing a 2-bit integer, Swapping the first half and the second half will do the job.
:male-teacher: **Go on.**
:evergreen_tree: THen, Doubling the size for a 4-bit integer, `ABCD`.Swapping the first half and last half results in `CDAB`, and if we swap each 2-bit half too, we get the result `DCBA`. We can also use the swapping half recursively to get the result for every 2^n-bit size datas, just swap the bits, starting from 2-bit chunks, doubling the chunk size.
:male-teacher: **Sounds interesting, but how are you going to implement it so that is faster that the previous solution?**
:evergreen_tree: Since we're working on the same 32-bit integer, instead of doing the shifting on each pair, we can combine the shifting and performing it on the whole 32-bit range at one time. This way, we just need to shift the number twice for each size of chunks.
:male-teacher: **I see. Can you code it up?**
:evergreen_tree: Sure.
```c=
uint32_t revbit(uint32_t n){
n = (n & 0xAAAAAAAA >> 1) | (n & 0x55555555 << 1);
n = (n & 0xCCCCCCCC >> 2) | (n & 0x33333333 << 2);
n = (n & 0xF0F0F0F0 >> 4) | (n & 0x0F0F0F0F << 4);
n = (n & 0xFF00FF00 >> 8) | (n & 0x00FF00FF << 8);
return ((n >> 16) |(n << 16));
}
```
Done. Now, we just need to do ten shifts instead of approx. 100 for each function call, and with no arithmetic operations.
:male-teacher: **Well-done, lets move on to a tree problem.**
### Problem 538. Convert BST to Greater Tree
:male-teacher: **Your problem is this: Given the root of a Binary search tree, Transform it into a "Greater Tree" so that every key in the node of the BST is transformed into the sum of all other node which holds a greater key value.**
:evergreen_tree: Its sounds quite complicated, can you provide an example?
:male-teacher: **If the the BST contains three nodes that is `[2, 1, 4]` in order, you should transform it into `[6, 7, 4]`**
:evergreen_tree: Okay, so `[2, 1, 4]` get modified into `[6, 7, 4]`. Since its a BST, those having a greater key value must be either the entire right child, or the node's ancestors if any of them is a left-side children.
For example, the following tree:
the node with value $4$ has to add the sum of the entire right sub tree, so 4 become 4+5+6=15;
the node with value $2$ has to sum $3$ and $4$ since they are left-child ancestors, and the entire subtree of node $4$
So I know that the transformed value in node $4$ will also be used in the left subtree.
:male-teacher: **Good, now you've done the analysis, how would code it up?**
:evergreen_tree: I think I am going to do a depth first search with a recursive call. Also i would keep track of a number that sums up all traversed node, since if we start from the right, all node thats is finished traversing or traversing the left is definetely greater than the current traversing node.
:male-teacher: **Right. Start coding then.**
:evergreen_tree:
```c=
struct node{
int val;
struct node *left;
struct node *right;
}
struct node *transformBST(struct node *n, int *sum){
if(!n){
return;
}
// Work on right subtree
transformBST(n->right, sum);
// Modify current value, since the left subtree
// Needs it to perform the calculation
n->val += *sum;
*sum = n->val;
// Work on left subtree
transformBST(n->left, sum);
return;
}
struct node* transformBST(struct node *root){
if(!root){
return root;
}
int a = 0;
transform(root, &a);
}
```
:male-teacher: **Okay, what is the time and space complexity of this solution?**
:evergreen_tree: Since we traverse each node 1 time, its `O(n)`, and in the worst that all child is on the same size, the recursive call stack will be as deep as the node number, so I think its also `O(n)`
:male-teacher: **Good job, you've nailed it. Thanks for your time!**
## 中文部分
:::info
看了老師給的範例影篇之後，
想嘗試直接 On the go 解題，途中問自己問題，就沒有台本了
(而且打中文字好累)
:::
### Problem 202. Happy Number
給予一個 `int n`，檢差它是不是 Happy Number.
將每一個位數的平方相加，重複這個動作，如果途中出現 1，代表它是個 Happy Number
+ **思路:** 將計算途中出現的所有數字利用 hash map 記住，如果重複出現任何一個代表出現迴圈
### Problem 383. Ransom Note
### Problem 921. Minimum Add to Make Parentheses Valid
+ 作為 intervierew 原本想問一個 ｢這邊作為 counter 你宣告了兩個變數 `up` 跟 `move`，請問有沒有可能減為一個呢？｣，但試想不太到解法於是就刪除了。
- 或許我應該問這個問題，然後作為 intervieree 說明為什麼需要兩個？
+ 事後檢討，雖然在算法上跟時間/空間複雜度上感覺沒有可以 optimize 的空間，但由於這題可以用 stact 的方式解答，感覺可以要求 interviewee 直接實作一個 stack
+ 或者朝向減少檔案大小的方向要求
Sign in with Wallet
Connect another wallet