@@scott5227 class Solution { public: int maxScore(vector& nums) { vector stack; // Store indices in decreasing order // Fill the stack with indices of a decreasing sequence for (int i = 0; i < nums.size(); ++i) { while (!stack.empty() && nums[stack.back()] < nums[i]) { stack.pop_back(); // Pop smaller elements } stack.push_back(i); } // Prepare to calculate the sum int max_val = 0; int prev = 0; // The initial starting point (equivalent to chain([0], stack) in Python) // Iterate through stack, calculating (p2 - p1) * nums[p2] for (int i = 0; i < stack.size(); ++i) { int p2 = stack[i]; max_val += (p2 - prev) * nums[p2]; prev = p2; // Move to the next position } return max_val; } };
參考即可，FAANG的面試流程一直再變，考題方向可以參考，但一定不會一樣。這年頭coding 能力不是重點，AI都會寫code了，反而是軟體架構這些邏輯思維基本功夠不夠紮實，database、微服務、container、雲端架構這些有沒有實務經驗才是重點，大量刷leetcode準備tier 1公司的準備方式已經過時，能夠按照scenario、limitations 選擇最適合的solution才是最重要的。
非常感謝您的分享🙌
嗨，想請教一下，關於"邏輯思維基本功夠不夠紮實"跟"按照scenario、limitations 選擇最適合的solution"，這幾句話，除了leetcode外，有沒有其他具體一些的方式可以讓小弟參考一下？
@@查理-l2x
簡單來說
小到problem solving
大到system design
Its called systems design lol
@@查理-l2x 可能嘗試參與大專案或者小專案開放原始的貢獻，這個也是實際扎實的作法，參與貢獻的過程中會發現實務上很多可能因為能力或知識不足的狀況而無法突破的困境。
個人經驗就是從台灣直接到新加坡大廠 （有Amazon 實習經驗
要申請前有幾個點要考慮
1. Position是否有visa sponsor ( 新加坡近幾年對EP(work pass）的管制越來越嚴格了 我申請junior position面試通過之後 還要讓主管批簽證（也就是說有可能面試通過但不給簽證） HR也說通常只有很senior的position 現在在新加坡才給簽證
2. 事先打聽好position很重要
以影片中面試者的實力去考理論上 不要太衰能通過 但更重要的是你接受offer之後 這個position到底香不香 因為你是海外拿簽證 你的簽證會跟公司綁一起 新加坡在被遣散或離職之後 一個月時間內必須找到另一家公司願意為你辦簽 不然就要回台灣 所以你要確保這個公司的主管 生活等等是你想要的 不然你到時候會被迫跟這家公司綁到你拿到永居 非常痛苦
(至於履歷準備哪些 我覺得大部分有耐心看完的 應該都知道怎麼準備 就不多說了 上面兩點是我覺得學生們在準備時不會想到的）
感謝您詳細的回覆，這對想前進新加坡的朋友非常有幫助！
謝謝這部影片！資訊含金量好高！
感謝您的支持
推推，好節目先訂閱起來!
最近剛好也在準面DSA，看完之後覺得面試官點評含金量很高，讚! 感覺凱心琳會是一個不錯的面試官，那個面試節奏確實可以消除一些面試者的緊張，發揮平常狀態!
by the way, 凱心琳有解釋我對於空間複雜度的疑問，我想說怎麼會是O(1)。哈哈
感謝支持，還有訂閱凱心琳👍
7777
老哥也太快進入coding了吧
但感覺腦袋轉超快
感謝實際示範 幫助很大！許願有英文版～
感謝支持，之後也會有面試的影片（算法/系統設計），但英文怕大家比較難聽懂
想當初看到這題，我就直接跟面試官說可以做dp 然後可以斜率優化，複雜度O(n logn) 。面試官一臉懵的看我，然後我在那邊解釋可以把dp轉移當成一條直線，用動態凸包去維護。還教面試官什麼是動態凸包，然後嘗試在白板上實作李超線段樹。 還好後來有想到O(n)的解。 我真的是寫code不帶點log就渾身不舒服😂
大神🙌
這題可以用Greedy，不需要dp，一次遍歷O(N)就解決了。
放在本例中，具體流程就是 ： 指針從最後面的數（1）開始，往前遍歷遇到了比較大的數（10），更新一次結果res += (1) * 距離；然後指針再往前走，遇到比較大的（12）， 更新一次res += (10) * 距離；然後指針再往前走，直到超出0，更新最後一次res += (12) * 距離
seudo code大概是：int maxNum = sequence[len - 1], int res = 0; for (int i = len - 1; i >= 0; i--) { if (sequence[i] > maxNum) { res += 距離 * maxNum, 更新maxNum為sequence[i] } ;
感謝您詳細的說明🙌
面試時像影片裡面從燒雞複雜度開始，一步一步進階到線性時間，還是直接寫出最佳解會比較好（？
原來這就是googler的面試強度阿.....
暴力解的時間複雜度的部分有點怪怪的，
依照面試者的做法，遞迴式應該是T(n) = T(n-1) + T(n - 2) + T(n - 3) + T(n - 4) ... + T(1), T(1) = O(1)
這樣應該要是O(2^n) 這個等級。
Ian說應該是這樣👍
一開始會想到dp ，O(n^2)。然後感覺沒辦法在更好了，因為距離一直變set也不行。
感謝分享！
感謝支持
@@Jonathanwu_tech 偷偷問個心琳什麼時候會更新YT(X
@@HamuraSho這你可能要私訊問她了😅
@@Jonathanwu_tech 想詢問有關binary search, lower bound, upper bound的參考資料還有相關算法實作
不知道大大有相關資源嗎🙏
@@HamuraSho 我以前新手練習解一些資料結構演算法的題目，會看這兩個頻道的影片：Neetcode或是portfoliocourses
單純以石頭只會往前走的題目來看，思考了一下後，從目前位置→剩餘數的最大值（如遇到相同最大值時選最遠的），然後不斷重複直到終點，似乎就會是最大值了，只要跑一次
用嘴巴寫Code🥺🥺
乘法本質是加法，我也是想到直接比大小累加最大值就好
這樣沒有考慮到一種情況：後面數字大到，放棄目前的jump，拿來乘後面數字較賺。
@@dycan0716 反向遍歷，計算方法一樣
@@dycan0716 他說了取當前數組的最大值 也就是說後面已經沒有比他大的數了
這應該就是最優解了 我想了一陣子才想到 跳到某個數可以視為目前的位置到跳到的數全部轉變成跳到的數 例如[8,3,6,5,9] 跳到9就可以看成轉變成[8,9,9,9,9](第一個數不重要) 分數會加上9*4=36 所以不斷跳到數組最大數就是最賺的 這題應該是貪心算法
凱心琳 感覺沒有什麼技術背景。不知道他在google是做什麼的
訂閱了
感謝您
所以講解算法也不用全程用英文嗎
看面試官吧
monostack
How?
@@scott5227
class Solution {
public:
int maxScore(vector& nums) {
vector stack; // Store indices in decreasing order
// Fill the stack with indices of a decreasing sequence
for (int i = 0; i < nums.size(); ++i) {
while (!stack.empty() && nums[stack.back()] < nums[i]) {
stack.pop_back(); // Pop smaller elements
}
stack.push_back(i);
}
// Prepare to calculate the sum
int max_val = 0;
int prev = 0; // The initial starting point (equivalent to chain([0], stack) in Python)
// Iterate through stack, calculating (p2 - p1) * nums[p2]
for (int i = 0; i < stack.size(); ++i) {
int p2 = stack[i];
max_val += (p2 - prev) * nums[p2];
prev = p2; // Move to the next position
}
return max_val;
}
};
I need to correct it is monotonic stack
3205. Maximum Array Hopping Score I On leetcode
此為最佳時間複雜度 O(n)
傷腦筋QQ 我的code 一直被刪掉
不PO了 有興趣再私訊或者網路上找
我得說monotonic stack 蠻容易在題目出來時就辨識出來
而且算是面試基本題型，有要面試者可以多練練
應該是一個維護一個遞減序列就可以，因為小大變大大會更好。感覺dp練太多了哈哈
暴力解recursive 的 time complexity應該是n平方？
是n^n沒錯 每一個狀態有一個for迴圈是O(n) 然後深度是n 所以總共n^n
@@mfjww 謝謝，一開始沒想清楚，有n個branch，深度是n
這麼強 程度不太好演算法自學有辦法嗎
@@飛馬 可以的 多刷題 多打leetcode codeforces atcoder等比賽 賽候補題 會進步很快