這個第一個做法一看就很簡單不會是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 可見不要跟面試官爭 沒有好下場的 -- ※ 發信站: 批踢踢實業坊(pttsite.org.tw), 來自: 114.36.59.14 (臺灣) ※ 文章網址: https://pttsite.org.tw/Soft_Job/M.1670044767.A.CB1 ※ 編輯: brucetu (114.36.59.14 臺灣), 12/03/2022 13:42:39