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

這個第一個做法一看就很簡單不會是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

可見不要跟面試官爭 沒有好下場的

--