Re: [請益] (ByteDance 面試) 兩種不同寫法的複雜度分析

看板Soft_Job作者brucetu (sec)時間1年前 (2022/12/03 13:19)推噓11(11推 0噓 21→)

留言32則, 13人參與討論串2/3 (看更多)

這個第一個做法一看就很簡單不會是N^2 如果是我會這樣嘗試跟面試官解釋字串abccba L R R一直往右跑 L視條件往右跑但L永不超過R 所以R最多右移N次 L也最多右移N次複雜度應該是2N 以上面為例 abccba L R 此時S={a,b,c} 這時候發現s[r]=c, 與S內的字元重複, L開始往右移直到沒有重複即 abccba L R 此時S={}, L一共位移3次之後R繼續往右走, 如遇重複則L要操作右移但整個演算法跑完L最多不會移動超過N次所以應該是O(N) 不知道這樣有沒有達到你(面試官)的要求? 如果面試官還是認為你錯你該做的是聽他的建議改成下面這樣因為你沒有能力解釋到他懂面試官本來就有高手有白癡有時候人的盲點就是覺得這個東西很簡單所以在跟對方解釋的時候一兩句話帶過以為對方一點就通其實你的跟他的對答方式有一點溝通不良例如 Q1: 你這個 while 應該改成 if 才對，不然會是 O(N^2) A1: 改成 if 的話會錯，因為我必須"一直"縮左界直到目前的 window 內沒有重複的字符這時候你應該跟他討論的是你的寫法不會是O(N^2)而不是if不if的問題如我前面說的很多人在跟對方解釋溝通的時候語焉不詳一兩句話帶過以為對方懂他意思面試官講這句話其實真正的意思是 "你的這段code看起來有兩個迴圈應該是O(N^2) 可能要把while改成if還是怎麼樣看看" 他的意思不是在說 "你把while改成if就會O(N) pass" 所以你回他 "改成 if的話會錯" 整個討論已經偏掉這就是為什麼溝通很重要也很困難常常有人開會討論半天沒重點就是因為兩個人都不把話完整講清楚一直互相誤導第二個QA Q2: 但你這個 for 是 O(N)，while 也是 O(N)，乘起來是 O(N^2)，我要 O(N) 的解 A2: 我的 l 不會超過 r，兩者都是最多從 0 跑到 N (l+=1 總共最多跑 N 次)，是分開的不能用乘法而且複雜度分析的本來就是 upper bound，你要說 O(N^2) 也對，但我的分析方法可以壓到 O(N) 我看你的回答馬上就懂你要表達的意思有點程度的工程師應該都懂但是顯然你遇到的面試官是一個白癡這時候你不能用這麼跳步驟快速簡單講重點的方式來跟他解釋你應該在學校也遇過那種明明很簡單但是他就聽不懂一定要一步一步來才能聽懂的同學吧? 你現在遇到的就是那樣的人啊你想要過他這關只有兩個辦法 1.他說的都是對的弄懂他需求滿足他需求就好了 2.你的解釋溝通技巧超好講到他能懂基本上走路線1比較安全如果你當初快速搞懂他只是不要那個while 然後兩三下改好code 他還會覺得你好溝通寫code快速熟練呢還不用浪費力氣跟他解釋半天再補充一點 Q6: 我要的最優解是 O(N)，不是 O(2N) (然後繼續跳針回 Q2)，我覺得我們對算法複雜度的理解不一樣其實你後來給的下面那個解worst還是2N啊 abcdefgg 可見不要跟面試官爭沒有好下場的 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.59.14 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1670044767.A.CB1.html ※ 編輯: brucetu (114.36.59.14 臺灣), 12/03/2022 13:42:39

推

et84121

12/03 15:02, 1年前 , 1^F

12/03 15:02, 1^F

推

art1

12/03 19:00, 1年前 , 2^F

12/03 19:00, 2^F

推

viper9709

12/03 20:35, 1年前 , 3^F

12/03 20:35, 3^F