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

事情是這樣的，今天下午面了 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



--