# 2021 年「資訊科技產業專案設計」課程作業 5
contributed by < `老藍 - OBlue` >
- [作業要求](https://hackmd.io/@sysprog/info2021/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Finfo2021-homework5)
----
[pramp](https://www.pramp.com/dashboard#/)
## Dec 22, 2021 10:00 PM
### [1. Shortest Cell Path](https://www.pramp.com/challenge/Y56aZmaj9Ptmd9wV9xvL)
In a given grid of 0s and 1s, we have some starting row and column sr, sc and a target row and column tr, tc. Return the length of the shortest path from sr, sc to tr, tc that walks along 1 values only.
Each location in the path, including the start and the end, must be a 1. Each subsequent location in the path must be 4-directionally adjacent to the previous location.
It is guaranteed that grid[sr][sc] = grid[tr][tc] = 1, and the starting and target positions are different.
If the task is impossible, return -1.
```
input:
grid = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 1, 1, 1]]
sr = 0, sc = 0, tr = 2, tc = 0
output: 8
(The lines below represent this grid:)
1111
0001
1111
grid = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 0, 1, 1]]
sr = 0, sc = 0, tr = 2, tc = 0
output: -1
(The lines below represent this grid:)
1111
0001
1011
```
### 想法
coordinate - 座標
grid node - 網格點
* BFS ?
* 處理分 normal and special case 然後遞迴解。
1. 知道 row & column 的長度，才能處理 special case(不能走 4 個方向的 grid node)
### ANS
Finding a shortest path is typically done with a breadth first search. Here, nodes are locations on the grid with value 1, and two nodes are neighbors if they are 4-directionally adjacent.
The breadth first search algorithm is given a source in the graph, and it explores all nodes distance 0 from the source, then all nodes distance 1, then all nodes distance 2, and so on. The algorithm records the node’s distance when it visits, and that way we can determine the shortest path in the graph to some target node.
By visiting nodes in order from distance to the source, this ensures that if we find the target word, we found it at the least possible distance and thus the answer is correct.
```python
function shortestCellPath(grid, sr, sc, tr, tc):
queue = Queue()
queue.add((sr, sc, 0))
seen = new HashSet()
seen.add((sr, sc))
while queue:
r, c, depth = queue.popfront()
if r == tr and c == tc: return depth
for (nr, nc) in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1 and (nr, nc) not in seen:
queue.append((nr, nc, depth + 1))
seen.add((nr, nc))
return -1
```
Time Complexity: O(R*C), where R, C are the number of rows and columns in grid. We might visit every square in the grid. It’s worth noting that typically in a breadth-first-search, the time complexity is O(V+E) where V = R * C is the number of nodes in the graph, and E is the number of edges. Since E <= 4*V, this is O(V+E) = O(V) = O(R * C).
Space Complexity: O(R*C), the space to store queue and seen.
### Award Budget Cuts (peer)
The awards committee of your alma mater (i.e. your college/university) asked for your assistance with a budget allocation problem they’re facing. Originally, the committee planned to give N research grants this year. However, due to spending cutbacks, the budget was reduced to newBudget dollars and now they need to reallocate the grants. The committee made a decision that they’d like to impact as few grant recipients as possible by applying a maximum cap on all grants. Every grant initially planned to be higher than cap will now be exactly cap dollars. Grants less or equal to cap, obviously, won’t be impacted.
Given an array grantsArray of the original grants and the reduced budget newBudget, write a function findGrantsCap that finds in the most efficient manner a cap such that the least number of recipients is impacted and that the new budget constraint is met (i.e. sum of the N reallocated grants equals to newBudget).
Example:
```
input: grantsArray = [2, 100, 50, 120, 1000], newBudget = 190
output: 47 # and given this cap the new grants array would be
# [2, 47, 47, 47, 47]. Notice that the sum of the
# new grants is indeed 190
```
### Dec 22, 2021 檢討
interviewer -> er
interviewee -> ee
這次坦白說慘不忍睹（看錄影真的很想找洞躲起來），整理以下幾點
* peer 是印度人，平常有在練習英文聽力，但是印度腔真的沒辦法。
* 印度先生還說 Your English is weak.（只有這句聽的最清楚）
* 溝通上出了很大問題，在當 er 時，我沒辦法很好的引導 ee 到自己答案的方向。
* 我們有聊自己目前的研究領域，但是溝通問題太大沒有很好的做成 Behavior Question 。
* Jserv 有提到不要停頓超過 15s 沒有在溝通，這次沒有做很好，一直都在想。
但是我學到了
* 因為我聽不懂 Award Budget Cuts 的問題，印度先生將問題轉換成分糖果，簡化的方式很值得學習。
* 更加確信如果未來目標要在外商工作，我必須花更多精力在英文上面。
* 表達的事情要更加精確。
## Sat, Jan 1, 2022, 8:00 PM
[2021info Hw5 REACTO 老藍(OBlue) Jan 1, 2022 part1](https://youtu.be/6i1yTL0tRxA)
[2020info Hw5 REACTO 老藍(OBlue) Jan 1, 2022 part2](https://youtu.be/qkrPXskEZTA)
---
### [Award Budget Cuts](https://www.pramp.com/challenge/r1Kw0vwG6OhK9AEGAyWV)
題目太長，轉換問題。
Here is another way to say this question.
Today I want to separate candies for each class. Every class has many students.
Here is a limitation. The candies can not be greater than the number of students in each class.
Candies can be cut into decimals.
### [Array Quadruplet](https://www.pramp.com/challenge/gKQ5zA52mySBOA5GALj9)
Given an unsorted array of integers arr and a number s, write a function findArrayQuadruplet that finds four numbers (quadruplet) in arr that sum up to s. Your function should return an array of these numbers in an ascending order. If such a quadruplet doesn’t exist, return an empty array.
Note that there may be more than one quadruplet in arr whose sum is s. You’re asked to return the first one you encounter (considering the results are sorted).
Explain and code the most efficient solution possible, and analyze its time and space complexities.
```
Example:
input: arr = [2, 7, 4, 0, 9, 5, 1, 3], s = 20
output: [0, 4, 7, 9] # The ordered quadruplet of (7, 4, 0, 9)
# whose sum is 20. Notice that there
# are two other quadruplets whose sum is 20:
# (7, 9, 1, 3) and (2, 4, 9, 5), but again you’re
# asked to return the just one quadruplet (in an
# ascending order)
```
### Sat, Jan 1, 2022 檢討
interviewer -> er
interviewee -> ee
這次遇到的是新加坡人，會說一點中文，在溝通上輕鬆許多，一開始是用英文，但是我在說方面的表達不好，所以後面就用中文來進行 mock interview。
這次我覺得 peer 是蠻標準型的，值得學習的地方他在當 ee/er 很注重溝通， ee 時會問我的初步想法，並請我直接打在白板上，中間幾乎沒有停頓超過 15s ，積極的把我引導到他的解法上！
比較可惜的是，他只專注在題目上，我也沒有去聊到個人經驗，應該這次比較可惜的部分。
我覺得這次在我在當 ee 時，表現比較可圈的點是我一直在說我的想法，譬如 Array Quadruplet 這題，我突然想到是不是可以轉化成 strongly connected graph ，呈現我了解一些 graph 的知識，或許可以引導 er 出 graph 的題目。但是這題用 [strongly connected graph](https://en.wikipedia.org/wiki/Strongly_connected_component) 顯然不是好辦法，因為 edge 太多，且每個 node 都要走過。
之後是 er 給出一些提示，讓我意識到這題應該是 [1.two sum](https://leetcode.com/problems/two-sum/) 的延伸 [18. 4Sum](https://leetcode.com/problems/4sum/) ，但是這之前我只有寫過 two sum（用 hash table 解決）。他要求 space complexity 只能是 O(1)，所以可以用兩個 pointer 來實現，但是我一開始沒有意識到可以用兩個 pointer ，所以這題還是花了很多時間。
需改進：
* 多聊聊自己的作品。
* 題目要練習多一點，光是找到題目解法就 1hr(連 coding 都沒)，上次看面 meta 的學長一題 REACTO 只需要 10~15mins，認識到自己還差得遠。
* 英文要再練習。
## JAN, 08, 2022
feat. `勞贖(Mouse)`
[399. Evaluate Division](https://leetcode.com/problems/evaluate-division/)
[198. House Robber](https://leetcode.com/problems/house-robber/)
[2020info Hw5-1 REACTO](https://www.youtube.com/watch?v=hxaY3MfQaDg&t=4s)
[2020info Hw5-2 REACTO](https://www.youtube.com/watch?v=X2GVebnkMAw)
在這次模擬面試中，我利用了前面兩次模擬面試的經驗，在當 interviewer 時積極的跟**勞贖**討論，並學習到站在 interviewer 的角度來思考。
* interviewer 會想知道 interviewee 是如何思考的，雖然在短短的幾小時內要去認識一個人是有難度的。
* 在這個高度分工的時代，找到一個適合團隊且可以討論的同事是很重要的一件事。能有邏輯性的講述自己的想法，以及如何尋找解決問題的技巧都是非常重要的事情。
這次要檢討的還是老問題(英文、題目練習太少........)，特別是我在當 interviewee 時，因為有人在看我寫 code，我會沒有辦法在 15s 內就給出很有建設性的答案，也沒辦法專心思考，一直需要 interviewer 給提示。
我可能要多練習 DP ，在這 3 次中我可以推敲出題目使用的其中一個解題技巧，但是在 programming 上還是太慢了，總結下來有三點要多練習。
1. 英文
2. 多練習題目並嘗試先思考後自問自答，可以在 15s 內給出有建設性的答案
3. 收集作品，在 interview 時，盡量的表達自己
Sign in with Wallet
Connect another wallet