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

[NTUmaki (西木野真姬)]

事情是這樣的，今天下午面了 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
推 me356500: 原本的寫法就很直觀的是sliding window O(2N) = O(N)
→ me356500: 我第一次寫這題也是這樣下手
→ me356500: 怎麼感覺面試官只是要你寫出他要的最佳解
我自己是認為兩種解法差別只是在 r 在什麼時候做 +=1，但拆解開來是一樣的
我能理解他可能不想看到 for 裡面有 while，但是他給的理由是這樣寫是 O(N^2) 我就不能理解了
→ me356500: 確實不可能是O(N^2)
推 me356500: 他可能只是想講說你第一個解法在用while把l右移這部分
→ me356500: 可以直接透過vector記他上次出現的idx一次就移到位
→ me356500: 我看起來你第二個解法也是2N就是了
我改成下面那個他就給過= =
→ me356500: 真的假的？ 底下那個不是2N嗎？
→ me356500: 其他題方便分享一下大概是什麼方面的嗎？ 感謝
permutation 跟nms(object detection那個) 還有 kalman filter，後兩者我說我只知道概念不知道詳細演算法他就跳過不考了
推 doranako: 第一種是跟第二種跑的迴圈數是一樣，第一種我覺得比較
→ doranako: 好懂，因為就是遇到重複要把左邊界內縮到重複字元的位
→ doranako: 置
推 heap5566: 這是n^2沒錯喔 複雜度是指成長速度 不是絕對的數字
用邏輯直接算出他的最多可能執行次數也是一種分析方法，跟是不是成長速度沒有關係
→ hobnob: 倒數第三句表示你可能不明白大公司為何考你刷題：面試官「
→ hobnob: 認定」你一開始就會給最佳解，否則表示你練習得不到位，只
→ hobnob: 求通過測資。不要問為什麼，因為「有人」做得到給最佳解，
→ hobnob: 既然有人做得到，為什麼工作機會要給做不到的你？
推 heap5566: 如果輸入是qwertaa這種字串不斷重複
推 hobnob: 確實你的第一個寫法是n^2。但我相信你可以跟ByteDance面
能解釋一下為什麼是 n^2 嗎？我是真不懂，實際測試也是時間差不多，leetcode 的測資應該還沒有那麼弱吧
→ hobnob: 試一定有能力跟其他大公司面試，剛好你碰到比較鐵頭的面
→ hobnob: 試官而已，祝你未來順利
推 heap5566: 有十分之n的位置的while會跑長度十分之n
→ heap5566: 乘起來是100分之n平方 還是n平方喔
但我的左界跟右界的更新次數都是O(N)，為什麼會是 O(N^2)?
你不能用乘法啊，你用 n/10 * n/10 代表左界超過右界繼續算下去，但這不會成立，set 是空的他就會跳出去了
推 watashino: worst case就是2N阿
→ watashino: 這樣複雜度怎麼可能是N平方
→ watashino: heap大這是沒考慮到left不可能超過right吧
推 me356500: 底下的寫法就上面的換種寫法不是嗎？ 哪裡來的N^2
推 watashino: 另外hobnob大講的跟我理解的不同
→ watashino: 通常是在面試過程中改進成最佳解才是一個好的面試官想
而且這兩個解根本一樣... 我只能猜說他覺得 for 裡面有 while 可能在實際寫 code 不是一個好習慣？
→ watashino: 要的吧
推 s06yji3: 面試官不一定是對的。
→ ken1325: O(N)+1
推 NTHUlagka: 應該是O(n)吧 同一個位置最多跑兩次阿
推 ok8752665: 用amortized 去看就好啊 到底怎麼跑到N^2
推 toole: 面試官不一定是對的，但跟會影響面試結果的人吵只是自找麻
→ toole: 煩
我沒有真的跟他"吵"起來(我有忍住)，就有點像是：他說我錯->我解釋我是對的->他說我錯....無限循環
這種情況應該怎麼辦...
推 gaymarriage: 就是O(N) 你衰 運氣不好
推 NTHUlagka: n平方發生在面試官是白癡的時候 Bytedance就這？ n/10
其實真的不能說他是錯的，我有一直強調說 O(N^2) 是一個鬆的 bound，用我的分析方法可以壓到 O(N)
→ NTHUlagka: 要乘的不是n/10是10 虧你還台大的 其他系去蹭？
→ watashino: 我也有跟面試官無限循環的經驗
→ watashino: 後來用例子說服他 他說錯的
→ watashino: 但耗很多時間
我實際拿測資 dry run 他都能說我錯了該怎解Orz，他說我們對複雜度的理解不同= =
推 nek0t1m: 跟面試官吵沒意義，吵贏也可能被評溝通不良，不如趕快提
→ nek0t1m: 出第二種解法move forward
其實一開始是這樣的：我以為他要測我是不是真的理解複雜度怎麼估才故意 challenge 我
如果我直接換解法 move forward 我怕是扣分（代表我前面寫那個是沒把握亂寫的），結果吵到一半才發現他是真的覺得我錯
推 BBSealion: 你是對的，但面試官最大，你的"最佳策略"應該是簡單常
→ BBSealion: 嘗試，發現他無法理解就快速放棄，找他的智商能看懂的
→ BBSealion: 做法，浪費時間是最不划算的，除非你也沒差這個 offer
但我要怎麼分辨他是真的不懂還是只是在挑戰我的分析QQ，我一開始以為他是要我解釋更清楚，結果辯到一半才發現不是
推 ABuJiuHaoBun: 抖音一響
推 s06yji3: 這個upper bound O(N^2)是什麼意思？
我用詞不太精確，應該說 Big O 數學上本來就可以估比較大，所以他說 O(N^2) 我沒說他錯，只是我跟他解釋可以分析到變成 O(N)
→ linnom: 你是對的，但面試官才是對的
※ 編輯: NTUmaki (123.204.135.123 臺灣), 11/30/2022 19:12:24
推 s06yji3: 你的實作是O(N)，除非是給他台階下，不然我不知道這O(N^2
→ s06yji3: )哪裡來的XD
推 johnny94: 換個角度想，如果你進去公司遇到類似的問題，你會想跟這
→ johnny94: 種人工作嗎？
→ johnny94: 現在是o(n) 以後就是各種 design 問題，有得吵的。不要
→ johnny94: 進去也是好事啦
推 a731977: 是n沒錯 可能面試官討厭那種寫法
推 NTHUlagka: 澄清一下上面那個不是在嗆你台大 是某h在那亂分析
推 SHANGOYANYI: 其實很簡單啦 他要的只是程式碼上看起來的O(n) 不是
→ SHANGOYANYI: 實際執行上的O(n) 反正兩個loop看起來就很不O(n)
推 BBSealion: 回應原Po 上面問題，其實就直接提問就好，請問面試官
→ BBSealion: 希望我證明這個做法是 O(N)，還是換一個寫法，如果期望
→ BBSealion: 只用一個迴圈的話，我也可以改寫成xx，但他本質上一樣
推 Gaogaigar: 你在遠端嗎? 是的話可能他根本分心在別的事情
推 jackfantasy: sliding window 複雜度 worst case 就是 2N，每個元
→ jackfantasy: 素最多進出一次 window，r 走過該元素表示進 window
→ jackfantasy: ，l 走過該元素表示出 window
→ jackfantasy: Best Case 是 N ，就是你的 r 一路走到底都不用內縮
→ jackfantasy: l，最終你的 window 等於整個數列長度，那每個元素就
→ jackfantasy: 是過一次
→ jackfantasy: 所以不管怎麼樣這方法就是 O(N)
→ jackfantasy: 演算法的複雜度基本看worst case，就像排序會說 NlgN
→ jackfantasy:  不會因為 Best Case 可以到N 就說他是 N
→ jackfantasy: 這題就算你用 hashmap 紀錄每個元素的位置來一次內縮
→ jackfantasy:  L 到位，worst case 還是看你的字串每個字都一樣的
→ jackfantasy: 時候，就是每個字進出一次，那複雜度還是 O(N) 沒有
→ jackfantasy: 因為這樣比較快的說法
推 jackfantasy: 只能說運氣佔面試很大一部分
推 kevin9527: 2N吧，請他舉出一個n^2的例子啊
推 kevin9527: 面試官搞不好比你菜 找別家吧
推 hank8451: 可以理解一開始看到的時候會以為是O(n^2)
→ hank8451: 但解釋半天都不懂也太扯…
→ watashino: 這串講的用hash來記位置是不是都沒考慮到中間其他元素
→ watashino: 也要刪除
推 jackfantasy: 用 hashmap 記位置的話也不用 set 了
→ jackfantasy: 每次 valid window 算一次 r-l+1 跟目前的 max取大的
→ jackfantasy: 就好
→ watashino: 沒看到詳細內容不敢斷定
→ watashino: 但樓上做法應該是錯的
推 jackfantasy: 那只好放個 ref 了 https://reurl.cc/rZv2OE
推 me356500: 不用啊 每次都會更新到最新的 我剛ac沒問題
→ watashino: OK 看來確實是描述不清楚的問題
→ watashino: 抱歉
推 genius945: 跟面試官僵持這個意義不大，討論一下沒共識就認定他的
→ genius945: 理解有問題然後直接照他要的給就好了
推 tallest: O(N) +1
→ tallest: 不過想想如果上了要跟這種人當同事 應該也是蠻痛苦的
推 hijamoya: 2n無誤
→ jerry771210: 會是英文表達不好？
中文面試
推 GinginDenSha: O(2N）沒錯 遇到這種就運氣不好 面試官是中國人嗎？
從用詞跟口音來看應該是中國人沒錯
推 hijamoya: 可能面試官只背到用map記住最後一個character的位置的
→ hijamoya: 那個答案
推 steven95421: 敝司智障太多QQ
推 h30306: 之前聽說抖音刷題都會考到Hard等級 原po面演算法工程師但
→ h30306: 是都遇到medium而已嗎？
推 Lin25K: 太雷了吧 第一眼看不出是O(n) 問題就很大了吧
推 sasoman: sliding window worse case就O(2n)
→ peter98: 面試官的水準本來就不一定好 #1VsgnX0z (Oversea_Job)
推 sarsman: 你是對的
推 BigCockman: 這面試官程度也太差 雙層迴圈就無腦覺得是n平方？
→ sarsman: 面試最氣的不是抽到難題，而是遇到雷包面試官==
→ BigCockman: 說真的久沒刷題不熟沒差 好歹幫人面試前看看解法 原
→ BigCockman: po這題寫法算很常見的了
推 holebro: 爛面試官
推 GinginDenSha: 不意外 中國一堆垃圾充斥各種公司 智障面試文化洪流
→ GinginDenSha: 下的豬  印度仔更不用說 無限繁衍的蛆蟲
推 CodingDuck: 字節跳動算了啦
→ CodingDuck: 上不了市不知道未來在哪的中國欺上瞞下公司，臺灣人
→ CodingDuck: 值得更好的。
推 viper9709: 跟這種人當同事 應該也是蠻痛苦的+1
推 hank55663: 阿就potential function 是r-l 所以每次增加常數(r+=1)
→ hank55663: 位能不會低於0 大概這樣 叫面試官回去讀演算法吧
推 paul800526: O(n)+1
→ MoonCode: 很簡單啊，第一個寫法你自己覺得好讀嗎？
推 pichubaby: 和他說：面試官先生，請不要直接數兩層迴圈就說他是N2
推 pichubaby: 所以才說面試要考LCS等級的DP，因為面試是雙向的，這樣
→ pichubaby: 才有機會意識到未來同事程度如何 :)
推 MoonCode: 樓上應該收到很多履歷了吧
推 Lhmstu: 老實說，確實第二種比較好，就程式碼來說的話
推 f12sd2e2aa: 好好笑 有人振振有詞說一堆 最後補出一個錯誤的結論
推 sarsman: 要求可讀性的話就不該扯複雜度，而且還亂扯
推 yumekanau: 面試官演算法程度有點差xd 背進去之後忘記怎麼分析了
→ yumekanau: 吧
推 sxy67230: 先說，第一種解法肯定不會是N^2，你又不是遍歷N兩次，
→ sxy67230: 考官的資結要去重修了，再者主考官提出的下面那種解法w
→ sxy67230: hile會執行到2N次，用hash記住最大可以縮到N次
噓 handsomeLin: 認真回，他質疑你的while是n的時候，總operation也是
→ handsomeLin: 2n而已，他數學不好就指出來就行，解釋也是工作的一
→ handsomeLin: 環
我有解釋 while 裡面的 l+=1 總共最多執行 N 次，他說他知道，但他說複雜度分析就是外面 O(N)，裡面 O(N) 所以乘起來是 O(N^2)
最後他就說我跟他對複雜度的理解不同，我也不知道該怎麼解釋了
※ 編輯: NTUmaki (123.204.135.123 臺灣), 12/01/2022 05:44:12
推 yyhsiu: 運氣不好無法 你看推文 面試官不是唯一不懂的
推 s06yji3: 我喜歡第一種
推 louisfghbvc: 第一種解法絕對是O(N)怎麼是O(N^2) 假設for迴圈有一
→ louisfghbvc: 次l跑滿 下一個r就不會跑了 那個l又不會reset, reset
→ louisfghbvc: 成0才是O(n^2)
推 A4P8T6X9: O(N)
推 aa06697: 這面試官以前上演算法應該有被當掉吧 複雜度分析哪是看幾
→ aa06697: 層迴圈去乘
→ aa06697: 只能說你運氣不好
推 jobintan: 找工作就七分實力三分運氣，運氣差會遇到不專業但又愛硬
→ jobintan: 拗的interviewer，這無解。
推 hidog: 面試官未必是對的，但你們不適合
→ hidog: 這種情況沒上不是壞事
推 dani1992: set操作不是logN嗎？這樣複雜度是O(NlogN)?
推 xdlow: to 樓上 python 的 set 是 hash table 實作的 所以會是 O
→ xdlow: (1)
推 gonna01: 爭贏好像沒什麼優點
推 Alex548291: 回樓上 爭贏沒有優點？啊就面試官觀念錯還不能討論喔
→ Alex548291: 以後工作只要主管說用A方法做 即使效率明顯低落 也繼
→ Alex548291: 續用A方法？什麼鬼觀念啊
→ Ekmund: 看到一半就懶了...我也遇過類似情況 說真的對方就是圖個
→ Ekmund: 心裡乾淨 避免現實場景規則變化時 你code複雜度跟著改變
→ Ekmund: 不能說誰對誰錯 但這要爭是爭不完的 不如換個角度看 你們
→ Ekmund: 其實不適合共事 也就不用浪費時間吵了 XD
推 Alex548291: 是說連這個也看不出來是O(N)當什麼Algorithm Engineer
→ Alex548291: 面試官 是不是文組沒修過演算法啊
推 can18: 面試官不理解 amortized 的概念吧 要在面試的時間內教會他
→ can18: 不太可能
→ can18: 只能說運氣不好
推 stkoso: 之後通常會有interview survey 記得寫上去
推 gamania0258: 說真的 你都說服他了還跳針 沒上也好 共事起來應該很
→ gamania0258: 痛苦 還是其實跳針應對也是考察一環XDDD
推 Kimheeche: 也可以換個方法說服他 跟他說N2的情況 有N+N次 或是根
→ Kimheeche: 據高斯定律N(N+1)/2 也是N2  但sliding window 的左右
→ Kimheeche: 指標肯定不是每輪掃N次或是逐次增加  最多就同個元素被
→ Kimheeche: 左右各碰到1次頂多2N
推 zanyking: 你挑戰的是BigO的定義，BigO本來就不細，迴圈數看是n^2
→ zanyking: 就是n^2，他要的就是程式碼看上去就『不可能』是n^2，而
→ zanyking: 不是『詳細』分析完才不是，很多時候沒有那種時間去分析
→ zanyking: 可以程式碼看上去就不可能那就這樣做可以保底
推 zanyking: 先註解，我已經接受1+1=5你是對的了，所以...
推 lovdkkkk: big 三兄弟(?) https://stackoverflow.com/a/12338937
推 olmrgcsi: 笑死 上面某h頭腦都不帶出來還在大談
→ stkoso: 第一個while加上l<r的條件應該就夠好懂了吧
→ stkoso: 這看上去就不會是n^2 你看不出來可以再看一眼
推 SRmoisTEH: O(N) 面試官該回去複習algo END
→ baobomb: 面試官很明顯死背的 他可能根本不知道什麼是sliding wind
→ baobomb: ow 遇到這種其實也不用跟他吵 有時候寫出讓不懂的人看的
→ baobomb: 懂的code也是工作的一部分 除非你是單幹王
→ baobomb: 然後Bytedance的hiring bar本來就不高 只要你會講中文 通
→ baobomb: 常就過50% 剩下就刷題而已
推 devilkool: 感覺你沒上的話是好事
推 quickey: 跟中國人面試挺痛苦的
推 kingofsdtw: 這很講臉緣
→ kingofsdtw: while不是不能用，只是有人看到就倒蛋
推 abccbaandy: 就說考這種通常也只是背答案而已...不意外啦
→ peter98: 應該說  其實迴圈用雙層而且兩個迴圈的條件邏輯不是一致
→ peter98: 就會有可讀性的問題
推 kuochuwon: 難得這個版有討論純技術的串 推
推 sunhextfn: 是O(N)
推 drysor: monotonic queue / stack 之類的問題起手式就是 for + wh
→ drysor: ile ，或是某些區間問題用 priority queue + hash 也會這
→ drysor: 樣寫吧…為啥看到 while 要倒彈
→ sxy67230: 某樓真的知道bigO的含義嗎？bigO是雖然是粗估worst cas
→ sxy67230: e的狀況，但是第一種寫法的內迴圈也不是遍歷N，函數上
→ sxy67230: 表達還是線性的，根本不是看看你用兩個迴圈就是N^2這回
→ sxy67230: 事好嗎
推 vir09700929: 我覺得整份程式碼很易讀乾淨，典型sliding window 題
→ vir09700929: 目，時間空間都O(N)，看來是面試官問題… 辛苦原PO
推 dani1992: 原來python set是hashtable實作
→ dani1992: 不過這樣hashtable worst case是O(N)，複雜度是O(N^2)
推 lovdkkkk: 在這個 case 基本上不會, 因為會不斷在 1 就被 remove
→ lovdkkkk: 除非找得到 N 個會發生 collision 但實際上不同的字
推 seanwu: 因為是字串，就算套兩層loop每次重掃也只會有255N=O(N)啊X
→ seanwu: D 要寫成N^2除非傻傻跑完不break吧，原po就運氣不好碰到不
→ seanwu: 會算複雜度的面試官
就討論到這吧.. 我不認為這個面試官能力很差，他考的其他題目都蠻 critical 的，很多我都答不太出來，只是在複雜度那塊他特別堅持己見而已@@
※ 編輯: NTUmaki (123.204.135.123 臺灣), 12/02/2022 04:12:44
推 lance8537: 跟他說別杠 杠就是你對
推 Alex548291: 那個zanyking跟h開頭的要不要包一包去重修演算法啊
推 snailpon: 面試官在測試「聽話指數」跟「奴性」，一切都說得通了XD
推 Awenwen: 辯論2N vs N^2 在面試勝算不大，要直接實際舉各兩
→ Awenwen: 個字串的例子去
→ Awenwen: 說明然後直接演算才有機會說服已經認為自己模糊的
→ Awenwen: 估算是對的人，
→ Awenwen: 某方面也是種溝通能力的考驗？
→ kiki86151: 其實面試要challenge面試官是下策 且想要說服人不能只
→ kiki86151: 說說 要直接具體證明 只舉case某方面不夠嚴謹 除非反證
→ kiki86151: 法這種 且你怎知道舉的case一定是worst 還叫人舉 雖然
→ kiki86151: 這演算法通常圖解POC很容易觀察到worst case確保一定2n
→ a27417332: 我是覺得Q2A2當證明已經足夠了吧
→ a27417332: 是面試官一直覺得有錯，發文者才請他舉反例證錯
→ peter9s3b: 面試官可能不想理解跟自己想法不同的作法。之前面有這
→ peter9s3b: 種感受
→ kiki86151: 要證l不會超過r啊 用講的誰都會講 我猜面試官懶得想 一
→ kiki86151: 個for一定是n 兩個for不考慮細節 直觀無腦看起來就n^2
→ a27417332: 那面試官要問為什麼l不會超過r而不是跳針吧XD
→ a27417332: 合格的面試官對自己出的題常見做法應該都要足夠熟悉吧
→ a27417332: 不然至少也要夠聰明去了解面試者想說什麼
→ a27417332: 不多準備又不想認真聽別人說什麼也是挺恐怖的表現
→ a27417332: 除非這樣的表示是公司期望展現的文化:)
推 zanyking: Alex548我就反串啊，都說1+1=5是對的，選完不能崩潰嗎
→ leolarrel: 人與人的交流比用程式碼跟電腦交流難太多了
→ kiki86151: 可抱怨面試官不合格 跳針 不好溝通啦 但對通關沒幫助:)
推 gofigure: algorithm engineer考這種也太水
推 XDucka: https://i.imgur.com/8IeLrcV.png  連ChatGPT都會這題....
推 s8952889: 面試官沒修過演算法…話說這串也太多把worst case跟bigO
→ s8952889: 混在一起談了吧，bigO純粹是upper bound跟worst case沒
→ s8952889: 關係，worst case也可以用theta或omega表示
推 Gorilla1234: 白癡面試官丟爆公司的臉...
→ acgotaku: 面試爭論這題沒啥意義呀  這題都做爛了
推 youtuuube000: 面試官的癥結點應該是忘了set是hash而不是array所以
→ youtuuube000: 查找只要big(1)吧…
推 gsrr: 面試不合就不要去工作
推 xluds24805: O(N) 沒錯，不過這要解釋起來可能不是那麼直覺，面試
→ xluds24805: 官也一時沒考慮清楚
推 masturbateee: chatGPT笑死
推 ManOfSteel: 慘，面試官，在網路上被鞭到爆。
噓 Murasaki0110: 好啦吵贏了好棒棒 拿個reject開心嗎
→ integritywei: bytedance本來就程度不怎麼樣, 不意外
推 bitcch: 下方寫法每次執行不保証r一定前進 其實就上面的變形也是2N
推 nicepeter: 時間複雜度是O(n)沒錯，很典型的sliding window算法
推 daddy29: 這題如果用兩個WHILE 寫他應該爆炸 蠻可悲的中國人
→ daddy29: upper bound 根本到不瞭O(N^2) 你這句話反而給他信心
→ daddy29: 直接留一句傻逼中國人斷線 跟hr回報換人面試就好
推 daddy29: 好像是我傻逼了,你第一段代碼真的是O(n^2)
→ daddy29: 用aaaaaaa 去算的話 你原本代碼執行 O(n * (n-1))
→ daddy29: 第二段代碼if最多執行一次 最壞是 O(n+n) 第二段效率高
→ brucetu: 樓上 第一段程式碼 aaaaa 不會執行 n*(n-1)
→ brucetu: L=0在最外面 迴圈裡面L+=1 當然不可能跑到超過N次
推 s06yji3: d大要確定捏
推 daddy29: https://imgur.com/a/u2MGQmj 碼的被ai戳 害老子去驗證
→ daddy29: 垃圾ai跟我說會執行8*8=64次 貼代碼以後叫我有疑問提出
→ daddy29: 提出以後給我當機 重新再問一次他娘的又變成O(n)了
推 daddy29: 想到還是好氣 補個幹 幹
→ peter98: 好像的是還有人不懂裝懂  嗆人去念演算法課本的結果自己
→ peter98: 錯得一蹋糊塗  可以去看#1X6gCUaz (Soft_Job)後面推文
→ peter98: 奇聞一定要共賞
噓 new122851: 不能純聊天？ 一定要leetcode爭這個？
推 KH22: 還好你沒進去跟這樣的人當同事