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