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

看板Soft_Job作者 (西木野真姬)時間1年前 (2022/11/30 17:23), 1年前編輯推噓106(108推 2噓 149→)
留言259則, 96人參與, 1年前最新討論串1/3 (看更多)
事情是這樣的，今天下午面了 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 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.204.135.123 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1669800213.A.900.html
推
11/30 17:35, 1年前 , 1F
原本的寫法就很直觀的是sliding window O(2N) = O(N)
11/30 17:35, 1F
→
11/30 17:35, 1年前 , 2F
我第一次寫這題也是這樣下手
11/30 17:35, 2F
→
11/30 17:36, 1年前 , 3F
怎麼感覺面試官只是要你寫出他要的最佳解
11/30 17:36, 3F
我自己是認為兩種解法差別只是在 r 在什麼時候做 +=1，但拆解開來是一樣的 我能理解他可能不想看到 for 裡面有 while，但是他給的理由是這樣寫是 O(N^2) 我就不能理解了
→
11/30 17:41, 1年前 , 4F
確實不可能是O(N^2)
11/30 17:41, 4F
推
11/30 17:50, 1年前 , 5F
他可能只是想講說你第一個解法在用while把l右移這部分
11/30 17:50, 5F
→
11/30 17:50, 1年前 , 6F
可以直接透過vector記他上次出現的idx一次就移到位
11/30 17:50, 6F
→
11/30 17:52, 1年前 , 7F
我看起來你第二個解法也是2N就是了
11/30 17:52, 7F
我改成下面那個他就給過= =
→
11/30 18:00, 1年前 , 8F
真的假的？ 底下那個不是2N嗎？
11/30 18:00, 8F
→
11/30 18:01, 1年前 , 9F
其他題方便分享一下大概是什麼方面的嗎？ 感謝
11/30 18:01, 9F
permutation 跟nms(object detection那個) 還有 kalman filter，後兩者我說我只知道概念不知道詳細演算法他就跳過不考了
推
11/30 18:08, 1年前 , 10F
第一種是跟第二種跑的迴圈數是一樣，第一種我覺得比較
11/30 18:08, 10F
→
11/30 18:08, 1年前 , 11F
好懂，因為就是遇到重複要把左邊界內縮到重複字元的位
11/30 18:08, 11F
→
11/30 18:08, 1年前 , 12F
置
11/30 18:08, 12F
推
11/30 18:22, 1年前 , 13F
這是n^2沒錯喔 複雜度是指成長速度 不是絕對的數字
11/30 18:22, 13F
用邏輯直接算出他的最多可能執行次數也是一種分析方法，跟是不是成長速度沒有關係
→
11/30 18:23, 1年前 , 14F
倒數第三句表示你可能不明白大公司為何考你刷題：面試官「
11/30 18:23, 14F
→
11/30 18:23, 1年前 , 15F
認定」你一開始就會給最佳解，否則表示你練習得不到位，只
11/30 18:23, 15F
→
11/30 18:23, 1年前 , 16F
求通過測資。不要問為什麼，因為「有人」做得到給最佳解，
11/30 18:23, 16F
→
11/30 18:23, 1年前 , 17F
既然有人做得到，為什麼工作機會要給做不到的你？
11/30 18:23, 17F
推
11/30 18:24, 1年前 , 18F
如果輸入是qwertaa這種字串不斷重複
11/30 18:24, 18F
推
11/30 18:25, 1年前 , 19F
確實你的第一個寫法是n^2。但我相信你可以跟ByteDance面
11/30 18:25, 19F
能解釋一下為什麼是 n^2 嗎？我是真不懂，實際測試也是時間差不多，leetcode 的測資應該還沒有那麼弱吧
→
11/30 18:25, 1年前 , 20F
試一定有能力跟其他大公司面試，剛好你碰到比較鐵頭的面
11/30 18:25, 20F
→
11/30 18:25, 1年前 , 21F
試官而已，祝你未來順利
11/30 18:25, 21F
推
11/30 18:26, 1年前 , 22F
有十分之n的位置的while會跑長度十分之n
11/30 18:26, 22F
→
11/30 18:27, 1年前 , 23F
乘起來是100分之n平方 還是n平方喔
11/30 18:27, 23F
但我的左界跟右界的更新次數都是O(N)，為什麼會是 O(N^2)? 你不能用乘法啊，你用 n/10 * n/10 代表左界超過右界繼續算下去，但這不會成立，set 是空的他就會跳出去了
推
11/30 18:30, 1年前 , 24F
worst case就是2N阿
11/30 18:30, 24F
→
11/30 18:30, 1年前 , 25F
這樣複雜度怎麼可能是N平方
11/30 18:30, 25F
→
11/30 18:34, 1年前 , 26F
heap大這是沒考慮到left不可能超過right吧
11/30 18:34, 26F
推
11/30 18:36, 1年前 , 27F
底下的寫法就上面的換種寫法不是嗎？ 哪裡來的N^2
11/30 18:36, 27F
推
11/30 18:37, 1年前 , 28F
另外hobnob大講的跟我理解的不同
11/30 18:37, 28F
→
11/30 18:38, 1年前 , 29F
通常是在面試過程中改進成最佳解才是一個好的面試官想
11/30 18:38, 29F
而且這兩個解根本一樣... 我只能猜說他覺得 for 裡面有 while 可能在實際寫 code 不是一個好習慣？
→
11/30 18:38, 1年前 , 30F
要的吧
11/30 18:38, 30F
推
11/30 18:41, 1年前 , 31F
面試官不一定是對的。
11/30 18:41, 31F
→
11/30 18:43, 1年前 , 32F
O(N)+1
11/30 18:43, 32F
還有 187 則推文
還有 11 段內文
→
12/02 11:04, 1年前 , 220F
個字串的例子去
12/02 11:04, 220F
→
12/02 11:04, 1年前 , 221F
說明然後直接演算才有機會說服已經認為自己模糊的
12/02 11:04, 221F
→
12/02 11:04, 1年前 , 222F
估算是對的人，
12/02 11:04, 222F
→
12/02 11:04, 1年前 , 223F
某方面也是種溝通能力的考驗？
12/02 11:04, 223F
→
12/02 11:44, 1年前 , 224F
其實面試要challenge面試官是下策 且想要說服人不能只
12/02 11:44, 224F
→
12/02 11:44, 1年前 , 225F
說說 要直接具體證明 只舉case某方面不夠嚴謹 除非反證
12/02 11:44, 225F
→
12/02 11:44, 1年前 , 226F
法這種 且你怎知道舉的case一定是worst 還叫人舉 雖然
12/02 11:44, 226F
→
12/02 11:44, 1年前 , 227F
這演算法通常圖解POC很容易觀察到worst case確保一定2n
12/02 11:44, 227F
→
12/02 13:02, 1年前 , 228F
我是覺得Q2A2當證明已經足夠了吧
12/02 13:02, 228F
→
12/02 13:03, 1年前 , 229F
是面試官一直覺得有錯，發文者才請他舉反例證錯
12/02 13:03, 229F
→
12/02 13:20, 1年前 , 230F
面試官可能不想理解跟自己想法不同的作法。之前面有這
12/02 13:20, 230F
→
12/02 13:20, 1年前 , 231F
種感受
12/02 13:20, 231F
→
12/02 13:22, 1年前 , 232F
要證l不會超過r啊 用講的誰都會講 我猜面試官懶得想 一
12/02 13:22, 232F
→
12/02 13:22, 1年前 , 233F
個for一定是n 兩個for不考慮細節 直觀無腦看起來就n^2
12/02 13:22, 233F
→
12/02 14:15, 1年前 , 234F
那面試官要問為什麼l不會超過r而不是跳針吧XD
12/02 14:15, 234F
→
12/02 14:17, 1年前 , 235F
合格的面試官對自己出的題常見做法應該都要足夠熟悉吧
12/02 14:17, 235F
→
12/02 14:17, 1年前 , 236F
不然至少也要夠聰明去了解面試者想說什麼
12/02 14:17, 236F
→
12/02 14:18, 1年前 , 237F
不多準備又不想認真聽別人說什麼也是挺恐怖的表現
12/02 14:18, 237F
→
12/02 14:28, 1年前 , 238F
除非這樣的表示是公司期望展現的文化:)
12/02 14:28, 238F
推
12/02 15:07, 1年前 , 239F
Alex548我就反串啊，都說1+1=5是對的，選完不能崩潰嗎
12/02 15:07, 239F
→
12/02 15:50, 1年前 , 240F
人與人的交流比用程式碼跟電腦交流難太多了
12/02 15:50, 240F
→
12/02 15:53, 1年前 , 241F
可抱怨面試官不合格 跳針 不好溝通啦 但對通關沒幫助:)
12/02 15:53, 241F
推
12/02 19:46, 1年前 , 242F
algorithm engineer考這種也太水
12/02 19:46, 242F
推
12/02 19:53, 1年前 , 243F
連ChatGPT都會這題....
12/02 19:53, 243F
推
12/03 03:15, 1年前 , 244F
面試官沒修過演算法…話說這串也太多把worst case跟bigO
12/03 03:15, 244F
→
12/03 03:15, 1年前 , 245F
混在一起談了吧，bigO純粹是upper bound跟worst case沒
12/03 03:15, 245F
→
12/03 03:15, 1年前 , 246F
關係，worst case也可以用theta或omega表示
12/03 03:15, 246F
推
12/03 12:33, 1年前 , 247F
白癡面試官丟爆公司的臉...
12/03 12:33, 247F
→
12/03 19:49, 1年前 , 248F
面試爭論這題沒啥意義呀 這題都做爛了
12/03 19:49, 248F
推
12/03 20:02, 1年前 , 249F
面試官的癥結點應該是忘了set是hash而不是array所以
12/03 20:02, 249F
→
12/03 20:02, 1年前 , 250F
查找只要big(1)吧…
12/03 20:02, 250F
推
12/03 21:28, 1年前 , 251F
面試不合就不要去工作
12/03 21:28, 251F
推
12/03 22:03, 1年前 , 252F
O(N) 沒錯，不過這要解釋起來可能不是那麼直覺，面試
12/03 22:03, 252F
→
12/03 22:03, 1年前 , 253F
官也一時沒考慮清楚
12/03 22:03, 253F
推
12/04 15:57, 1年前 , 254F
chatGPT笑死
12/04 15:57, 254F
推
12/04 21:27, 1年前 , 255F
慘，面試官，在網路上被鞭到爆。
12/04 21:27, 255F
噓
12/05 13:29, 1年前 , 256F
好啦吵贏了好棒棒 拿個reject開心嗎
12/05 13:29, 256F
→
12/05 13:36, 1年前 , 257F
bytedance本來就程度不怎麼樣, 不意外
12/05 13:36, 257F
推
12/05 20:20, 1年前 , 258F
下方寫法每次執行不保証r一定前進 其實就上面的變形也是2N
12/05 20:20, 258F
推
12/05 21:26, 1年前 , 259F
時間複雜度是O(n)沒錯，很典型的sliding window算法
12/05 21:26, 259F
‣ 更多 NTUmaki 的文章
文章代碼(AID): #1ZXo4La0 (Soft_Job)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共3篇)
‣ 更多 NTUmaki 的文章
文章代碼(AID): #1ZXo4La0 (Soft_Job)