[請益] (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
--
原本的寫法就很直觀的是sliding window O(2N) = O(N)
我第一次寫這題也是這樣下手
怎麼感覺面試官只是要你寫出他要的最佳解
我自己是認為兩種解法差別只是在 r 在什麼時候做 +=1，但拆解開來是一樣的 我能理解他可能不想看到 for 裡面有 while，但是他給的理由是這樣寫是 O(N^2) 我就不能理解了
確實不可能是O(N^2)
他可能只是想講說你第一個解法在用while把l右移這部分
可以直接透過vector記他上次出現的idx一次就移到位
我看起來你第二個解法也是2N就是了
我改成下面那個他就給過= =
真的假的？ 底下那個不是2N嗎？
其他題方便分享一下大概是什麼方面的嗎？ 感謝
permutation 跟nms(object detection那個) 還有 kalman filter，後兩者我說我只知道概念不知道詳細演算法他就跳過不考了
第一種是跟第二種跑的迴圈數是一樣，第一種我覺得比較
好懂，因為就是遇到重複要把左邊界內縮到重複字元的位
置
這是n^2沒錯喔 複雜度是指成長速度 不是絕對的數字
用邏輯直接算出他的最多可能執行次數也是一種分析方法，跟是不是成長速度沒有關係
倒數第三句表示你可能不明白大公司為何考你刷題：面試官「
認定」你一開始就會給最佳解，否則表示你練習得不到位，只
求通過測資。不要問為什麼，因為「有人」做得到給最佳解，
既然有人做得到，為什麼工作機會要給做不到的你？
如果輸入是qwertaa這種字串不斷重複
確實你的第一個寫法是n^2。但我相信你可以跟ByteDance面
能解釋一下為什麼是 n^2 嗎？我是真不懂，實際測試也是時間差不多，leetcode 的測資應該還沒有那麼弱吧
試一定有能力跟其他大公司面試，剛好你碰到比較鐵頭的面
試官而已，祝你未來順利
有十分之n的位置的while會跑長度十分之n
乘起來是100分之n平方 還是n平方喔
但我的左界跟右界的更新次數都是O(N)，為什麼會是 O(N^2)? 你不能用乘法啊，你用 n/10 * n/10 代表左界超過右界繼續算下去，但這不會成立，set 是空的他就會跳出去了
worst case就是2N阿
這樣複雜度怎麼可能是N平方
heap大這是沒考慮到left不可能超過right吧
底下的寫法就上面的換種寫法不是嗎？ 哪裡來的N^2
另外hobnob大講的跟我理解的不同
通常是在面試過程中改進成最佳解才是一個好的面試官想
而且這兩個解根本一樣... 我只能猜說他覺得 for 裡面有 while 可能在實際寫 code 不是一個好習慣？
要的吧
面試官不一定是對的。
O(N)+1
應該是O(n)吧 同一個位置最多跑兩次阿
用amortized 去看就好啊 到底怎麼跑到N^2
面試官不一定是對的，但跟會影響面試結果的人吵只是自找麻
煩
我沒有真的跟他"吵"起來(我有忍住)，就有點像是：他說我錯->我解釋我是對的->他說我錯....無限循環 這種情況應該怎麼辦...
就是O(N) 你衰 運氣不好
n平方發生在面試官是白癡的時候 Bytedance就這？ n/10
其實真的不能說他是錯的，我有一直強調說 O(N^2) 是一個鬆的 bound，用我的分析方法可以壓到 O(N)
要乘的不是n/10是10 虧你還台大的 其他系去蹭？
我也有跟面試官無限循環的經驗
後來用例子說服他 他說錯的
但耗很多時間
我實際拿測資 dry run 他都能說我錯了該怎解Orz，他說我們對複雜度的理解不同= =
跟面試官吵沒意義，吵贏也可能被評溝通不良，不如趕快提
出第二種解法move forward
其實一開始是這樣的：我以為他要測我是不是真的理解複雜度怎麼估才故意 challenge 我 如果我直接換解法 move forward 我怕是扣分（代表我前面寫那個是沒把握亂寫的），結果吵到一半才發現他是真的覺得我錯
你是對的，但面試官最大，你的"最佳策略"應該是簡單常
嘗試，發現他無法理解就快速放棄，找他的智商能看懂的
做法，浪費時間是最不划算的，除非你也沒差這個 offer
但我要怎麼分辨他是真的不懂還是只是在挑戰我的分析QQ，我一開始以為他是要我解釋更清楚，結果辯到一半才發現不是
抖音一響
這個upper bound O(N^2)是什麼意思？
我用詞不太精確，應該說 Big O 數學上本來就可以估比較大，所以他說 O(N^2) 我沒說他錯，只是我跟他解釋可以分析到變成 O(N)
你是對的，但面試官才是對的
你的實作是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 走過該元素表示出 window
Best 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兩次，
考官的資結要去重修了，再者主考官提出的下面那種解法w
hile會執行到2N次，用hash記住最大可以縮到N次
認真回，他質疑你的while是n的時候，總operation也是
2n而已，他數學不好就指出來就行，解釋也是工作的一
環
我有解釋 while 裡面的 l+=1 總共最多執行 N 次，他說他知道，但他說複雜度分析就是外面 O(N)，裡面 O(N) 所以乘起來是 O(N^2) 最後他就說我跟他對複雜度的理解不同，我也不知道該怎麼解釋了
※ 編輯: NTUmaki (123.204.135.123 臺灣), 12/01/2022 05:44:12運氣不好無法 你看推文 面試官不是唯一不懂的
我喜歡第一種
第一種解法絕對是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 wind
ow 遇到這種其實也不用跟他吵 有時候寫出讓不懂的人看的
懂的code也是工作的一部分 除非你是單幹王
然後Bytedance的hiring bar本來就不高 只要你會講中文 通
常就過50% 剩下就刷題而已
感覺你沒上的話是好事
跟中國人面試挺痛苦的
這很講臉緣
while不是不能用，只是有人看到就倒蛋
就說考這種通常也只是背答案而已...不意外啦
應該說 其實迴圈用雙層而且兩個迴圈的條件邏輯不是一致
就會有可讀性的問題
難得這個版有討論純技術的串 推
是O(N)
monotonic queue / stack 之類的問題起手式就是 for + wh
ile ，或是某些區間問題用 priority queue + hash 也會這
樣寫吧…為啥看到 while 要倒彈
某樓真的知道bigO的含義嗎？bigO是雖然是粗估worst cas
e的狀況，但是第一種寫法的內迴圈也不是遍歷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)啊X
D 要寫成N^2除非傻傻跑完不break吧，原po就運氣不好碰到不
會算複雜度的面試官
就討論到這吧.. 我不認為這個面試官能力很差，他考的其他題目都蠻 critical 的，很多我都答不太出來，只是在複雜度那塊他特別堅持己見而已@@
※ 編輯: NTUmaki (123.204.135.123 臺灣), 12/02/2022 04:12:44跟他說別杠 杠就是你對
那個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都會這題....
96
[請益] Google面試時都不能停下來想嗎?前幾天phone interview啊.. 面試官剛出完題 就開始問... 面試官：你的解法應該要有個初始值，先寫下來吧 我：嗯....讓我想一下... (你才剛出完題欸)53
Backend 台外商 14 間面試紀錄剛剛不知道為啥一直不能編輯補充，只好重發。 謹以此文向 PHEj 大大還願，感謝他在臺灣工程師走出海外的的幫助與鼓勵。 TL;DR 無聲卡 SonicWall30
Re: [問卦] leetcode medium看完答案還是寫不出來看什麼題目吧 一些討論區的最佳解 簡化到失去可讀性 也失去題目的思維 要不看人題解 要不就是自己認真從頭到尾寫出來 對刷leetcode比較有用 依照本巨巨在矽谷面試別人的經驗 我準備的題目都是 馬上可以寫出暴力解 然後暴力解逐步優化 我個人最愛的就是01背包問題 因為暴力解超簡單 就一個東西只能放一次24
[請益] 面試白板考題目的時間複雜度剛剛編輯文章按到復原草稿 插入很多不必要東西 但用Pitt沒辦法編輯 所以刪除重po不好意思 以下代之前社團認識的學妹代po詢問![[請益] 面試白板考題目的時間複雜度](https://www.facebook.com/images/fb_icon_325x325.png "[請益] 面試白板考題目的時間複雜度")
11
[請益] 面試時聊到其他間的面試算大忌嗎？就是面試時， 想展現一下能力， 但可能面試官都沒問到優勢的地方 那可以說別間公司面試的專業的問題嗎 就是別間面試曾聊到的一個核心問題，當時給出了一個覺得很滿意的解法。8
Re: [討論] 軟體工作真的有需要刷題嗎?其實說實在話 就是你想進哪間公司的遊戲規則罷了 我認識很多很厲害的人 你問他們two sum他們不會很快的想到O(N)解，現實有多少人是在沒看過解法前想到呢？ 但很多專案其實要會的從來就不是到底是不是最佳解 確實很多大型軟體公司都拿題目當標準，如果想進就是乖乖刷，我印象中這幾天才有一位