事情是這樣的，今天下午面了 ByteDance 2023 的缺 (Algorithm Engineer)
考了 leetcode 3. Longest Substring Without Repeating Characters
(https://reurl.cc/WqNV8k)
我的解法：
https://i.imgur.com/o5wrRMo.png
我原本寫上面那個解法，兩個差異就是 for 裡面放一個 while 跟只用一個 while
面試官說我的解法不是 O(N)，是 O(N^2)，跟他吵了半小時之後就把解改成下面的。
想問我是不是真的哪裡陷入誤區？
我原本以為他是想看我反應 & 如何解釋，吵到一半發現他是真的不認為我的解法正確
面試官的說法 & 我的回答：
Q1: 你這個 while 應該改成 if 才對，不然會是 O(N^2)
A1: 改成 if 的話會錯，因為我必須"一直"縮左界直到目前的 window 內沒有重複的字符
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)
Q3: 我知道你的意思，但是我們只看 while，是不是最糟跑到 O(N)? 然後 for 也是 O(N)，這樣分析是不是 O(N^2)
A3: 不是，你分析不能只看某一段 code，我是整個考慮進去所以壓的複雜度還是 O(N)
Q4: 這不是我要的最優解 (然後跳針回 Q2)
A4: 不然這樣講好了，你舉一個 worst case 例子給我我 dry run 給你看他不會是 O(N^2)
然後大概就是說類似這種 case s='qwertaa'，遇到第二個 a 的時候他說我的 while 會是 O(N)
A5: 但是遇到的時候 l 也不會超過 r，不會存在一個情況使得 while 會需要每次都跑 O(N)，他"總共"需要執行的次數最多就是 N
Q6: 我要的最優解是 O(N)，不是 O(2N) (然後繼續跳針回 Q2)，我覺得我們對算法複雜度的理解不一樣
A6: O(2N) 跟 O(N) 是一樣的 (然後他說他知道，但這不是他要的最優解)
接著大概就是一直重複跳針回 Q2 然後我一直用不同的方法去解釋跟他說這個是 O(N)
我直接請他舉一個 worst case 會是 O(N^2) 的例子我 dry run，他還是說我是 O(N^2), O(Nk), O(Nn) 之類的，就不是 O(N)
最後我就說總之你不想要 for 裡面有 while 的解對吧？然後就寫了下面那段 code 給他就下一題了..
如果他一開始就說不要用兩個迴圈寫應該就沒什麼問題，但他一直強調那個不是最優，而且是 O(N^2)
就跟他吵了半個小時...
我實際去 leetcode 跑了兩種算法，時間都差不多，到底哪裡有問題QQ

原本的寫法就很直觀的是sliding window O(2N) = O(N)我第一次寫這題也是這樣下手怎麼感覺面試官只是要你寫出他要的最佳解確實不可能是O(N^2)他可能只是想講說你第一個解法在用while把l右移這部分可以直接透過vector記他上次出現的idx一次就移到位我看起來你第二個解法也是2N就是了真的假的？ 底下那個不是2N嗎？其他題方便分享一下大概是什麼方面的嗎？ 感謝

第一種是跟第二種跑的迴圈數是一樣，第一種我覺得比較好懂，因為就是遇到重複要把左邊界內縮到重複字元的位置

這是n^2沒錯喔 複雜度是指成長速度 不是絕對的數字

倒數第三句表示你可能不明白大公司為何考你刷題：面試官「認定」你一開始就會給最佳解，否則表示你練習得不到位，只求通過測資。不要問為什麼，因為「有人」做得到給最佳解，既然有人做得到，為什麼工作機會要給做不到的你？

如果輸入是qwertaa這種字串不斷重複

確實你的第一個寫法是n^2。但我相信你可以跟ByteDance面試一定有能力跟其他大公司面試，剛好你碰到比較鐵頭的面試官而已，祝你未來順利

有十分之n的位置的while會跑長度十分之n乘起來是100分之n平方 還是n平方喔

worst case就是2N阿這樣複雜度怎麼可能是N平方heap大這是沒考慮到left不可能超過right吧

底下的寫法就上面的換種寫法不是嗎？ 哪裡來的N^2

另外hobnob大講的跟我理解的不同通常是在面試過程中改進成最佳解才是一個好的面試官想要的吧

面試官不一定是對的。

O(N)+1

應該是O(n)吧 同一個位置最多跑兩次阿

用amortized 去看就好啊 到底怎麼跑到N^2

面試官不一定是對的，但跟會影響面試結果的人吵只是自找麻煩

就是O(N) 你衰 運氣不好

n平方發生在面試官是白癡的時候 Bytedance就這？ n/10要乘的不是n/10是10 虧你還台大的 其他系去蹭？

我也有跟面試官無限循環的經驗後來用例子說服他 他說錯的但耗很多時間

跟面試官吵沒意義，吵贏也可能被評溝通不良，不如趕快提出第二種解法move forward

你是對的，但面試官最大，你的"最佳策略"應該是簡單常嘗試，發現他無法理解就快速放棄，找他的智商能看懂的做法，浪費時間是最不划算的，除非你也沒差這個 offer

抖音一響

這個upper bound O(N^2)是什麼意思？

你是對的，但面試官才是對的

你的實作是O(N)，除非是給他台階下，不然我不知道這O(N^2)哪裡來的XD

換個角度想，如果你進去公司遇到類似的問題，你會想跟這種人工作嗎？現在是o(n) 以後就是各種 design 問題，有得吵的。不要進去也是好事啦

是n沒錯 可能面試官討厭那種寫法

澄清一下上面那個不是在嗆你台大 是某h在那亂分析

其實很簡單啦 他要的只是程式碼上看起來的O(n) 不是實際執行上的O(n) 反正兩個loop看起來就很不O(n)

回應原Po 上面問題，其實就直接提問就好，請問面試官希望我證明這個做法是 O(N)，還是換一個寫法，如果期望只用一個迴圈的話，我也可以改寫成xx，但他本質上一樣

你在遠端嗎? 是的話可能他根本分心在別的事情

sliding window 複雜度 worst case 就是 2N，每個元素最多進出一次 window，r 走過該元素表示進 window，l 走過該元素表示出 windowBest Case 是 N ，就是你的 r 一路走到底都不用內縮l，最終你的 window 等於整個數列長度，那每個元素就是過一次所以不管怎麼樣這方法就是 O(N)演算法的複雜度基本看worst case，就像排序會說 NlgN不會因為 Best Case 可以到N 就說他是 N這題就算你用 hashmap 紀錄每個元素的位置來一次內縮L 到位，worst case 還是看你的字串每個字都一樣的時候，就是每個字進出一次，那複雜度還是 O(N) 沒有因為這樣比較快的說法只能說運氣佔面試很大一部分

2N吧，請他舉出一個n^2的例子啊面試官搞不好比你菜 找別家吧

可以理解一開始看到的時候會以為是O(n^2)但解釋半天都不懂也太扯…

這串講的用hash來記位置是不是都沒考慮到中間其他元素也要刪除

用 hashmap 記位置的話也不用 set 了每次 valid window 算一次 r-l+1 跟目前的 max取大的就好

沒看到詳細內容不敢斷定但樓上做法應該是錯的

那只好放個 ref 了 https://reurl.cc/rZv2OE

不用啊 每次都會更新到最新的 我剛ac沒問題

OK 看來確實是描述不清楚的問題抱歉

跟面試官僵持這個意義不大，討論一下沒共識就認定他的理解有問題然後直接照他要的給就好了

O(N) +1不過想想如果上了要跟這種人當同事 應該也是蠻痛苦的

2n無誤

會是英文表達不好？

O(2N）沒錯 遇到這種就運氣不好 面試官是中國人嗎？

可能面試官只背到用map記住最後一個character的位置的那個答案

敝司智障太多QQ

之前聽說抖音刷題都會考到Hard等級 原po面演算法工程師但是都遇到medium而已嗎？

太雷了吧 第一眼看不出是O(n) 問題就很大了吧

sliding window worse case就O(2n)

面試官的水準本來就不一定好 #1VsgnX0z (Oversea_Job)

你是對的

這面試官程度也太差 雙層迴圈就無腦覺得是n平方？

面試最氣的不是抽到難題，而是遇到雷包面試官==

說真的久沒刷題不熟沒差 好歹幫人面試前看看解法 原po這題寫法算很常見的了

爛面試官

不意外 中國一堆垃圾充斥各種公司 智障面試文化洪流下的豬 印度仔更不用說 無限繁衍的蛆蟲

字節跳動算了啦上不了市不知道未來在哪的中國欺上瞞下公司，臺灣人值得更好的。

跟這種人當同事 應該也是蠻痛苦的+1

阿就potential function 是r-l 所以每次增加常數(r+=1)位能不會低於0 大概這樣 叫面試官回去讀演算法吧

O(n)+1

很簡單啊，第一個寫法你自己覺得好讀嗎？

和他說：面試官先生，請不要直接數兩層迴圈就說他是N2所以才說面試要考LCS等級的DP，因為面試是雙向的，這樣才有機會意識到未來同事程度如何 :)

樓上應該收到很多履歷了吧

老實說，確實第二種比較好，就程式碼來說的話

好好笑 有人振振有詞說一堆 最後補出一個錯誤的結論

要求可讀性的話就不該扯複雜度，而且還亂扯

面試官演算法程度有點差xd 背進去之後忘記怎麼分析了吧

先說，第一種解法肯定不會是N^2，你又不是遍歷N兩次，考官的資結要去重修了，再者主考官提出的下面那種解法while會執行到2N次，用hash記住最大可以縮到N次

認真回，他質疑你的while是n的時候，總operation也是2n而已，他數學不好就指出來就行，解釋也是工作的一環

運氣不好無法 你看推文 面試官不是唯一不懂的

我喜歡第一種

第一種解法絕對是O(N)怎麼是O(N^2) 假設for迴圈有一次l跑滿 下一個r就不會跑了 那個l又不會reset, reset成0才是O(n^2)

O(N)

這面試官以前上演算法應該有被當掉吧 複雜度分析哪是看幾層迴圈去乘只能說你運氣不好

找工作就七分實力三分運氣，運氣差會遇到不專業但又愛硬拗的interviewer，這無解。

面試官未必是對的，但你們不適合這種情況沒上不是壞事

set操作不是logN嗎？這樣複雜度是O(NlogN)?

to 樓上 python 的 set 是 hash table 實作的 所以會是 O(1)

爭贏好像沒什麼優點

回樓上 爭贏沒有優點？啊就面試官觀念錯還不能討論喔以後工作只要主管說用A方法做 即使效率明顯低落 也繼續用A方法？什麼鬼觀念啊

看到一半就懶了...我也遇過類似情況 說真的對方就是圖個心裡乾淨 避免現實場景規則變化時 你code複雜度跟著改變不能說誰對誰錯 但這要爭是爭不完的 不如換個角度看 你們其實不適合共事 也就不用浪費時間吵了 XD

是說連這個也看不出來是O(N)當什麼Algorithm Engineer面試官 是不是文組沒修過演算法啊

面試官不理解 amortized 的概念吧 要在面試的時間內教會他不太可能只能說運氣不好

之後通常會有interview survey 記得寫上去

說真的 你都說服他了還跳針 沒上也好 共事起來應該很痛苦 還是其實跳針應對也是考察一環XDDD

也可以換個方法說服他 跟他說N2的情況 有N+N次 或是根據高斯定律N(N+1)/2 也是N2 但sliding window 的左右指標肯定不是每輪掃N次或是逐次增加 最多就同個元素被左右各碰到1次頂多2N

你挑戰的是BigO的定義，BigO本來就不細，迴圈數看是n^2就是n^2，他要的就是程式碼看上去就『不可能』是n^2，而不是『詳細』分析完才不是，很多時候沒有那種時間去分析可以程式碼看上去就不可能那就這樣做可以保底先註解，我已經接受1+1=5你是對的了，所以...

big 三兄弟(?) https://stackoverflow.com/a/12338937

笑死 上面某h頭腦都不帶出來還在大談

第一個while加上l<r的條件應該就夠好懂了吧這看上去就不會是n^2 你看不出來可以再看一眼

O(N) 面試官該回去複習algo END

面試官很明顯死背的 他可能根本不知道什麼是sliding window 遇到這種其實也不用跟他吵 有時候寫出讓不懂的人看的懂的code也是工作的一部分 除非你是單幹王然後Bytedance的hiring bar本來就不高 只要你會講中文 通常就過50% 剩下就刷題而已

感覺你沒上的話是好事

跟中國人面試挺痛苦的

這很講臉緣while不是不能用，只是有人看到就倒蛋

就說考這種通常也只是背答案而已...不意外啦

應該說 其實迴圈用雙層而且兩個迴圈的條件邏輯不是一致就會有可讀性的問題

難得這個版有討論純技術的串 推

是O(N)

monotonic queue / stack 之類的問題起手式就是 for + while ，或是某些區間問題用 priority queue + hash 也會這樣寫吧…為啥看到 while 要倒彈

某樓真的知道bigO的含義嗎？bigO是雖然是粗估worst case的狀況，但是第一種寫法的內迴圈也不是遍歷N，函數上表達還是線性的，根本不是看看你用兩個迴圈就是N^2這回事好嗎

我覺得整份程式碼很易讀乾淨，典型sliding window 題目，時間空間都O(N)，看來是面試官問題… 辛苦原PO

原來python set是hashtable實作不過這樣hashtable worst case是O(N)，複雜度是O(N^2)

在這個 case 基本上不會, 因為會不斷在 1 就被 remove除非找得到 N 個會發生 collision 但實際上不同的字

因為是字串，就算套兩層loop每次重掃也只會有255N=O(N)啊XD 要寫成N^2除非傻傻跑完不break吧，原po就運氣不好碰到不會算複雜度的面試官

跟他說別杠 杠就是你對

那個zanyking跟h開頭的要不要包一包去重修演算法啊

面試官在測試「聽話指數」跟「奴性」，一切都說得通了XD

辯論2N vs N^2 在面試勝算不大，要直接實際舉各兩個字串的例子去說明然後直接演算才有機會說服已經認為自己模糊的估算是對的人，某方面也是種溝通能力的考驗？

其實面試要challenge面試官是下策 且想要說服人不能只說說 要直接具體證明 只舉case某方面不夠嚴謹 除非反證法這種 且你怎知道舉的case一定是worst 還叫人舉 雖然這演算法通常圖解POC很容易觀察到worst case確保一定2n

我是覺得Q2A2當證明已經足夠了吧是面試官一直覺得有錯，發文者才請他舉反例證錯

面試官可能不想理解跟自己想法不同的作法。之前面有這種感受

要證l不會超過r啊 用講的誰都會講 我猜面試官懶得想 一個for一定是n 兩個for不考慮細節 直觀無腦看起來就n^2

那面試官要問為什麼l不會超過r而不是跳針吧XD合格的面試官對自己出的題常見做法應該都要足夠熟悉吧不然至少也要夠聰明去了解面試者想說什麼不多準備又不想認真聽別人說什麼也是挺恐怖的表現除非這樣的表示是公司期望展現的文化:)

Alex548我就反串啊，都說1+1=5是對的，選完不能崩潰嗎

人與人的交流比用程式碼跟電腦交流難太多了

可抱怨面試官不合格 跳針 不好溝通啦 但對通關沒幫助:)

algorithm engineer考這種也太水

https://i.imgur.com/8IeLrcV.png 連ChatGPT都會這題....

面試官沒修過演算法…話說這串也太多把worst case跟bigO混在一起談了吧，bigO純粹是upper bound跟worst case沒關係，worst case也可以用theta或omega表示

白癡面試官丟爆公司的臉...

面試爭論這題沒啥意義呀 這題都做爛了

面試官的癥結點應該是忘了set是hash而不是array所以查找只要big(1)吧…

面試不合就不要去工作

O(N) 沒錯，不過這要解釋起來可能不是那麼直覺，面試官也一時沒考慮清楚

chatGPT笑死

慘，面試官，在網路上被鞭到爆。

好啦吵贏了好棒棒 拿個reject開心嗎

bytedance本來就程度不怎麼樣, 不意外

下方寫法每次執行不保証r一定前進 其實就上面的變形也是2N

時間複雜度是O(n)沒錯，很典型的sliding window算法

這題如果用兩個WHILE 寫他應該爆炸 蠻可悲的中國人upper bound 根本到不瞭O(N^2) 你這句話反而給他信心直接留一句傻逼中國人斷線 跟hr回報換人面試就好

樓上 第一段程式碼 aaaaa 不會執行 n*(n-1)L=0在最外面 迴圈裡面L+=1 當然不可能跑到超過N次

d大要確定捏

https://imgur.com/a/u2MGQmj 碼的被ai戳 害老子去驗證垃圾ai跟我說會執行8*8=64次 貼代碼以後叫我有疑問提出提出以後給我當機 重新再問一次他娘的又變成O(n)了想到還是好氣 補個幹 幹

好像的是還有人不懂裝懂 嗆人去念演算法課本的結果自己錯得一蹋糊塗 可以去看#1X6gCUaz (Soft_Job)後面推文奇聞一定要共賞

不能純聊天？ 一定要leetcode爭這個？

還好你沒進去跟這樣的人當同事