事情是这样的，今天下午面了 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)我第一次写这题也是这样下手怎么感觉面试官只是要你写出他要的最佳解确实不可能是O(N^2)他可能只是想讲说你第一个解法在用while把l右移这部分可以直接透过vector记他上次出现的idx一次就移到位我看起来你第二个解法也是2N就是了真的假的？ 底下那个不是2N吗？其他题方便分享一下大概是什么方面的吗？ 感谢

第一种是跟第二种跑的循环数是一样，第一种我觉得比较好懂，因为就是遇到重复要把左边界内缩到重复字符的位置

这是n^2没错喔 复杂度是指成长速度 不是绝对的数字

倒数第三句表示你可能不明白大公司为何考你刷题：面试官“认定”你一开始就会给最佳解，否则表示你练习得不到位，只求通过测资。不要问为什么，因为“有人”做得到给最佳解，既然有人做得到，为什么工作机会要给做不到的你？

如果输入是qwertaa这种字串不断重复

确实你的第一个写法是n^2。但我相信你可以跟ByteDance面试一定有能力跟其他大公司面试，刚好你碰到比较铁头的面试官而已，祝你未来顺利

有十分之n的位置的while会跑长度十分之n乘起来是100分之n平方 还是n平方喔

worst case就是2N阿这样复杂度怎么可能是N平方heap大这是没考虑到left不可能超过right吧

底下的写法就上面的换种写法不是吗？ 哪里来的N^2

另外hobnob大讲的跟我理解的不同通常是在面试过程中改进成最佳解才是一个好的面试官想要的吧

面试官不一定是对的。

O(N)+1

应该是O(n)吧 同一个位置最多跑两次阿

用amortized 去看就好啊 到底怎么跑到N^2

面试官不一定是对的，但跟会影响面试结果的人吵只是自找麻烦

就是O(N) 你衰 运气不好

n平方发生在面试官是白痴的时候 Bytedance就这？ n/10要乘的不是n/10是10 亏你还台大的 其他系去蹭？

我也有跟面试官无限循环的经验后来用例子说服他 他说错的但耗很多时间

跟面试官吵没意义，吵赢也可能被评沟通不良，不如赶快提出第二种解法move forward

你是对的，但面试官最大，你的"最佳策略"应该是简单常尝试，发现他无法理解就快速放弃，找他的智商能看懂的做法，浪费时间是最不划算的，除非你也没差这个 offer

抖音一响

这个upper bound O(N^2)是什么意思？

你是对的，但面试官才是对的

你的实作是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 走过该元素表示出 windowBest 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两次，考官的资结要去重修了，再者主考官提出的下面那种解法while会执行到2N次，用hash记住最大可以缩到N次

认真回，他质疑你的while是n的时候，总operation也是2n而已，他数学不好就指出来就行，解释也是工作的一环

运气不好无法 你看推文 面试官不是唯一不懂的

我喜欢第一种

第一种解法绝对是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 window 遇到这种其实也不用跟他吵 有时候写出让不懂的人看的懂的code也是工作的一部分 除非你是单干王然后Bytedance的hiring bar本来就不高 只要你会讲中文 通常就过50% 剩下就刷题而已

感觉你没上的话是好事

跟中国人面试挺痛苦的

这很讲脸缘while不是不能用，只是有人看到就倒蛋

就说考这种通常也只是背答案而已...不意外啦

应该说 其实循环用双层而且两个循环的条件逻辑不是一致就会有可读性的问题

难得这个版有讨论纯技术的串 推

是O(N)

monotonic queue / stack 之类的问题起手式就是 for + while ，或是某些区间问题用 priority queue + hash 也会这样写吧…为啥看到 while 要倒弹

某楼真的知道bigO的含义吗？bigO是虽然是粗估worst case的状况，但是第一种写法的内循环也不是遍历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)啊XD 要写成N^2除非傻傻跑完不break吧，原po就运气不好碰到不会算复杂度的面试官

跟他说别杠 杠就是你对

那个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都会这题....

面试官没修过算法…话说这串也太多把worst case跟bigO混在一起谈了吧，bigO纯粹是upper bound跟worst case没关系，worst case也可以用theta或omega表示

白痴面试官丢爆公司的脸...

面试争论这题没啥意义呀 这题都做烂了

面试官的症结点应该是忘了set是hash而不是array所以查找只要big(1)吧…

面试不合就不要去工作

O(N) 没错，不过这要解释起来可能不是那么直觉，面试官也一时没考虑清楚

chatGPT笑死

惨，面试官，在网络上被鞭到爆。

好啦吵赢了好棒棒 拿个reject开心吗

bytedance本来就程度不怎么样, 不意外

下方写法每次执行不保証r一定前进 其实就上面的变形也是2N

时间复杂度是O(n)没错，很典型的sliding window算法

这题如果用两个WHILE 写他应该爆炸 蛮可悲的中国人upper bound 根本到不了O(N^2) 你这句话反而给他信心直接留一句傻逼中国人断线 跟hr回报换人面试就好

楼上 第一段程式码 aaaaa 不会执行 n*(n-1)L=0在最外面 循环里面L+=1 当然不可能跑到超过N次

d大要确定捏

https://imgur.com/a/u2MGQmj 码的被ai戳 害老子去验证垃圾ai跟我说会执行8*8=64次 贴代码以后叫我有疑问提出提出以后给我当机 重新再问一次他娘的又变成O(n)了想到还是好气 补个干 干

好像的是还有人不懂装懂 呛人去念算法课本的结果自己错得一蹋糊涂 可以去看#1X6gCUaz (Soft_Job)后面推文奇闻一定要共赏

不能纯聊天？ 一定要leetcode争这个？

还好你没进去跟这样的人当同事