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

[brucetu (sec)]

這個第一個做法一看就很簡單不會是N^2

如果是我會這樣嘗試跟面試官解釋

字串abccba
    L
    R

R一直往右跑 L視條件往右跑 但L永不超過R

所以R最多右移N次 L也最多右移N次

複雜度應該是2N

以上面為例
abccba
L
   R
此時S={a,b,c}
這時候發現s[r]=c, 與S內的字元重複, L開始往右移直到沒有重複 即
abccba
   L
   R
此時S={}, L一共位移3次
之後R繼續往右走, 如遇重複則L要操作右移

但整個演算法跑完L最多不會移動超過N次

所以應該是O(N)

不知道這樣有沒有達到你(面試官)的要求?

如果面試官還是認為你錯

你該做的是聽他的建議改成下面這樣

因為你沒有能力解釋到他懂

面試官本來就有高手有白癡

有時候人的盲點就是覺得這個東西很簡單

所以在跟對方解釋的時候一兩句話帶過 以為對方一點就通

其實你的跟他的對答方式 有一點溝通不良

例如

Q1: 你這個 while 應該改成 if 才對，不然會是 O(N^2)

A1: 改成 if 的話會錯，因為我必須"一直"縮左界直到目前的 window 內沒有重複的字符

這時候你應該跟他討論的是 你的寫法不會是O(N^2)而不是if不if的問題

如我前面說的 很多人在跟對方解釋溝通的時候語焉不詳 一兩句話帶過以為對方懂他意思

面試官講這句話其實真正的意思是

"你的這段code看起來有兩個迴圈應該是O(N^2) 可能要把while改成if還是怎麼樣看看"

他的意思不是在說 "你把while改成if就會O(N) pass"

所以你回他 "改成 if的話會錯" 整個討論已經偏掉

這就是為什麼溝通很重要也很困難 常常有人開會討論半天沒重點

就是因為兩個人都不把話完整講清楚 一直互相誤導

第二個QA

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)

我看你的回答馬上就懂你要表達的意思 有點程度的工程師應該都懂

但是顯然你遇到的面試官是一個白癡

這時候你不能用這麼跳步驟快速簡單講重點的方式來跟他解釋

你應該在學校也遇過那種 明明很簡單但是他就聽不懂

一定要一步一步來才能聽懂的同學吧?

你現在遇到的就是那樣的人啊

你想要過他這關

只有兩個辦法

1.他說的都是對的 弄懂他需求 滿足他需求就好了

2.你的解釋溝通技巧超好 講到他能懂

基本上走路線1比較安全

如果你當初快速搞懂他只是不要那個while 然後兩三下改好code

他還會覺得你好溝通 寫code快速熟練呢

還不用浪費力氣跟他解釋半天

再補充一點

Q6: 我要的最優解是 O(N)，不是 O(2N) (然後繼續跳針回 Q2)，我覺得我們對算法複雜
度的理解不一樣

其實你後來給的下面那個解worst還是2N啊

abcdefgg

可見不要跟面試官爭 沒有好下場的


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.59.14 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1670044767.A.CB1.html
※ 編輯: brucetu (114.36.59.14 臺灣), 12/03/2022 13:42:39
推 et84121: 推推這篇
推 art1: 我還以為 L 跟 R 的意思是一個從左邊開始，一個從右邊開始XD
推 viper9709: 推這篇
推 akito117: 推 硬要說服對方真的麻煩
→ kiki86151: 本來就這樣 SBStep還是不懂就該採做法1 就算MAAMA尖牙
→ kiki86151: 公司多少還是會有白癡面試官 想過關就別跟他爭 就算爭
→ kiki86151: 贏又怎樣 等著準備吃strong no hire吧 真的吃到就別哭
推 ronald0000: 推 溝通很重要
→ hsnuyi: 所以set access是O(1)? 初學者想了解更多 有官方文件? 3Q
→ hsnuyi: 請問https://wiki.python.org/moin/TimeComplexity是官方?
→ peter98: 一般情況set的search complexity就是講constant就好  另
→ peter98: 外記得worst case是linear  然後有些語言會改善set  如果
→ peter98: 用tree去實作set的話則是lgN (避開worst case = N)
→ peter98: 如此而已  沒其他的了
→ hsnuyi: 所以這種題目 使用array算字母出現狀況 會和用set有差不
→ hsnuyi: 多的效果嗎? 謝謝
推 ke265379ke: 樓上，在python內 in cause 速度會有差，set是O(1) li
→ ke265379ke: st 是O(N)
推 s06yji3: 他的array應該是說把char換算成對應的index直接存取吧。
推 ke265379ke: 喔喔 那我誤會了
推 ntpuisbest: 分開的，所以不能用乘我知道，但是為何這樣就是分開
→ ntpuisbest: 的?
→ ntpuisbest: 因為L不會倒退?
→ brucetu: set access 這邊因為char只有英數 跟超長字串的N比起來
→ brucetu: 當作O(1)是沒問題
→ brucetu: 那個set的大小頂多就10個數字+26個英數字大小寫
→ brucetu: 因為L不會倒退 沒錯 如果L有可能倒退 那很有可能
→ brucetu: 會是一個worst case O(N^2)的問題
→ brucetu: *上兩行是回ntpuisbest
推 ntpuisbest: 謝謝解釋
推 daddy29: 面試官應該被搞混了 第一種寫法乍看真的像O(N^2)
→ daddy29: R固定+1 遇到特定條件L才+1 for while 等價情況他不熟