第一場：2018年12月30日（周日），北京時間早上五點。
寫在最前面：好不容易五點爬了起來圍觀mock，結果早上周賽睡過去了，唉。orz。
面試官：wisdompeak，同學：littleRainRain
第一題：有個花圃矩陣 grid，size 是n * m，花圃上面的一個點，坐標是(x, y)上面可能有花，可能沒有花（沒有花的話，矩陣上的值為0）。如果一個Q(x,y)上有花的話，grid[x][y] = W， W代表這朵花的香氣，隨著距離這朵花越來越遠，花的香氣會逐漸減弱，減弱的關系和兩個點的曼哈頓距離成正比，比如在點 P(x1, y1)，能聞到在點Q的花的香味是 f = W / (abs(x- x1) + abs(y-y1))。輸入一個P點的坐標(px, py)，求在這個P點，能聞到花的香味最重的點坐標。
題解：直接二維矩陣遍歷就行。只有一點需要注意的就是曼哈頓距離為0的時候，0不能做除數，怎么處理要問面試官，不要自己yy。
follow-up，能不能讓算法更快一點？（其實我覺得這個問法不是特別的優秀，第一次聽到了比較容易懵逼，如果我是面試者的話下面不知道該怎么接。直接問具體條件有什么變化，還是新增了什么條件么）
我第一次聽到follow-up有點懵逼，我還以為難道bfs能解...但是迅速的否認了自己的想法，想象一下如果有個點距離給出的P點非常非常遠，但是它的W非常非常大，這個點也有可能是candidate。
后來面試官解釋了一下，假設這個花圃上面就幾朵花呢？然后調用query方法N次，如何加速這個算法（言下之意是這個矩陣是一個稀疏矩陣）
ok，那我們開始預處理下矩陣，把有花的坐標點給存下來，存成一個數組，假設叫flowerCoor，然后每次query的時候就從flowerCoor里面取花的坐標，然后計算。
?
第二題：leetcode 837 New 21 Game
https://leetcode.com/problems/new-21-game/description/
面試官化簡了一下這個題，他的問題是桌面上有10張撲克牌，代表[1, 10]這個區間的數字，玩家一開始有個基礎分數 score， 游戲開始，score 代表現在點數，如果 score < 17， 那么莊家隨機翻一張牌，累加score；如果 score 在[17, 21] 這個區間中，就代表莊家win；如果 score > 21 就代表玩家win。求玩家 win 的概率。
前面怎么討論的我有點記不清了，但是妹子說了一句“這個題有點遞歸的意思”，然后就開始遞歸做。遞歸可以做。（不知道如果遞歸寫全對的話，下面follow-up會不會擴大規模考 dp。不過想不到 dp不知道是 hired 還是 weak hired 了）
lc遞歸會超時，我加了記憶化遞歸也超時了 :( ，lc給的是 dp 解法。
mock的時候群里小伙伴有人說這題和 688 很像：https://leetcode.com/problems/knight-probability-in-chessboard/description/
?
第三題：leetcode 636?Exclusive Time of Functions
https://leetcode.com/problems/exclusive-time-of-functions/description/
第三題有點類似資源搶占調度的一道題。
?task 1:? start,? 0
?task 2:? start,? 2
?task 2:? end,? 3
?task 1:? end,? 4
?task 2:? start,?6
?task 2:? end,? 7
start, end just mean get schecduled, like process to CPU, only one cpu, so if task2 started, task 1 paused。
要求返回每個task占用cpu的時間。返回map也好，數組也好，都行。
用stack解，我還沒仔細想。我估計應該是用一個變量或者pair存某個任務被中斷的時間？
?
第四題：leetcode 528. Random Pick with Weight
https://leetcode.com/problems/random-pick-with-weight/description/
群主給的就是有 N 個人種，每個人種的占比，實現一個算法，這個算法每次都會返回一個人種，在調用K（K是一個很大的數）次的情況下，所有的返回值的比例滿足人種的占比。
given possibility like
chinese? 22%
american:? 5%
indian: 21%
...
各個概率之和保證為1，隨機選一個,要求符合概率,如按22.333% sample chinese..
?
妹子一開始想的有點類似于基數了，就是比如說chinese占了22%，American占了 5%，那我搞一個 100 個人的數組，前 22 個元素 代表 chinese， 23 ～ 28 個元素代表 american。然后 1 ～ 100 內隨機一個隨機數，求得。然后面試官反問，如果占比不是整數呢，比如 22.345676798878888%這種，那是不是要開一個巨大的數組存這些數。于是這個思路走進死胡同了。群里有小伙伴說，如果有個 0 ～ 1 的隨機數發生器就好了。我們可以這么思考，就是我們把概率數組求前綴和，然后隨機一個 0 ～ 1 的數，在前綴和數組中二分這個數字就可以了。
題解：前綴和 + 二分。
?
、encodeURI()、encodeURIComponent()區別詳解)
