在美國的軟體行業裡，要做 coding 面試算是很正常的事情，而這些 coding 面試大部份都是資料結構和演算法的內容，所以都是大學的必修課．但其實有許多題目還真的不是光念過課本就能想的到，那些題目還真的需要多練習．在市面上有許多網站會列出一些常見的面試考題，而我之前最常去的網站就是 Leetcode. 這網站不僅記載了許多考題，而且還有 online judge 可以直接測驗你的程式碼是否正確.
今天來聊聊這一題，在 Leetcode 網站上的第 73 題．我被問過一模一樣的題目，面試者連改都沒有改，而這一題也讓我體會到另一種空間複雜度的境界．
第 73 題的題目是指，給你一個 m x n 的矩陣，如果在第 (i,j) 的位置上出現 0 時，就要把 row i 和 column j 的元素全部變成 0．剛看到這個題目，覺得不會很難．最直覺的方法是你可以宣告兩個 Array 或 List 來記錄那些 row 和 column 裡面有 0 ，最後再依據 Array 或 List 的內容把相關 row 和 column 的內容變成 0．如果你是這樣想的，其實這方法也沒什麼不好，只是要多浪費一點空間，因為另外宣告了額外的 Array/List 來記錄那些 row, column 有 0 的元素存在，而且 Array/List 的大小會根據矩陣的大小而改變，因此在空間複雜度上就不是 constant 了，而是 O(m+n)．如果這時候面試官沒繼續要求的話，那基本上就過關了．但生活中有時很難會如此順利，面試官很可能會要求你在空間複雜度上做到 constant space．也就是說你可以用其他的空間，但是這些額外的空間不能隨著矩陣大小變化而改變．
既然是這樣規定的話，這題目就真的變得有相當的難度了．我自己在做這題目時也無法在五分鐘之內想到好的解答．為什麼是五分鐘呢 ? 因為一個面試通常是一小時，其中做 coding 考試的時候大約有三十分鐘，所以在五分鐘之內沒有想出正確答案的話，那就很難可以在剩下的時間把程度寫完在白板或電腦上．
後來，我參考了網路上其他人的解法，我找到一個蠻好的解法．基本上，這個解法要宣告兩個基本的變數，這是 constant space，而它把每個 row, column 有 0 的資訊直接記錄在輸入矩陣之中，因此，根本就不需要用到非 constant space 的空間了．
如果你用心把這個解法看完的話，你一定也會覺得這方法實在太妙了，而且保證你對空間複雜度的應用會有更高一層的體會．原來把 input parameter 的空間拿來做為暫存空間，也是一種省空間的好方法．
0 意見:
張貼留言