電腦科學 ^ IT人生 ^ 公益課程

#23 Coding 面試 Leetcode #73 Set Matrix Zeroes

我打算把以前遇到的一些在面試時遇到的一些特別經驗或感想記錄在這電腦科學筆記裡,一方面,在面試時會遇到的問題大部份都是基礎的電腦科學題目,二方面也把這些過程記錄下來,當做是一種紀念吧!

在美國的軟體行業裡,要做 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 的空間拿來做為暫存空間,也是一種省空間的好方法.

Share:

0 意見:

張貼留言