作者NTUmaki (西木野真姬)
看板Soft_Job
标题[请益] (ByteDance 面试) 两种不同写法的复杂度分析
时间Wed Nov 30 17:23:31 2022
事情是这样的，今天下午面了 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://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1669800213.A.900.html
1F：推 me356500: 原本的写法就很直观的是sliding window O(2N) = O(N) 11/30 17:35
2F：→ me356500: 我第一次写这题也是这样下手 11/30 17:35
3F：→ me356500: 怎麽感觉面试官只是要你写出他要的最佳解 11/30 17:36
我自己是认为两种解法差别只是在 r 在什麽时候做 +=1，但拆解开来是一样的
我能理解他可能不想看到 for 里面有 while，但是他给的理由是这样写是 O(N^2) 我就不能理解了
4F：→ me356500: 确实不可能是O(N^2) 11/30 17:41
5F：推 me356500: 他可能只是想讲说你第一个解法在用while把l右移这部分 11/30 17:50
6F：→ me356500: 可以直接透过vector记他上次出现的idx一次就移到位 11/30 17:50
7F：→ me356500: 我看起来你第二个解法也是2N就是了 11/30 17:52
我改成下面那个他就给过= =
8F：→ me356500: 真的假的？ 底下那个不是2N吗？ 11/30 18:00
9F：→ me356500: 其他题方便分享一下大概是什麽方面的吗？ 感谢 11/30 18:01
permutation 跟nms(object detection那个) 还有 kalman filter，後两者我说我只知道概念不知道详细演算法他就跳过不考了
10F：推 doranako: 第一种是跟第二种跑的回圈数是一样，第一种我觉得比较 11/30 18:08
11F：→ doranako: 好懂，因为就是遇到重复要把左边界内缩到重复字元的位 11/30 18:08
12F：→ doranako: 置 11/30 18:08
13F：推 heap5566: 这是n^2没错喔 复杂度是指成长速度 不是绝对的数字 11/30 18:22
用逻辑直接算出他的最多可能执行次数也是一种分析方法，跟是不是成长速度没有关系
14F：→ hobnob: 倒数第三句表示你可能不明白大公司为何考你刷题：面试官「 11/30 18:23
15F：→ hobnob: 认定」你一开始就会给最佳解，否则表示你练习得不到位，只 11/30 18:23
16F：→ hobnob: 求通过测资。不要问为什麽，因为「有人」做得到给最佳解， 11/30 18:23
17F：→ hobnob: 既然有人做得到，为什麽工作机会要给做不到的你？ 11/30 18:23
18F：推 heap5566: 如果输入是qwertaa这种字串不断重复 11/30 18:24
19F：推 hobnob: 确实你的第一个写法是n^2。但我相信你可以跟ByteDance面 11/30 18:25
能解释一下为什麽是 n^2 吗？我是真不懂，实际测试也是时间差不多，leetcode 的测资应该还没有那麽弱吧
20F：→ hobnob: 试一定有能力跟其他大公司面试，刚好你碰到比较铁头的面 11/30 18:25
21F：→ hobnob: 试官而已，祝你未来顺利 11/30 18:25
22F：推 heap5566: 有十分之n的位置的while会跑长度十分之n 11/30 18:26
23F：→ heap5566: 乘起来是100分之n平方 还是n平方喔 11/30 18:27
但我的左界跟右界的更新次数都是O(N)，为什麽会是 O(N^2)?
你不能用乘法啊，你用 n/10 * n/10 代表左界超过右界继续算下去，但这不会成立，set 是空的他就会跳出去了
24F：推 watashino: worst case就是2N阿 11/30 18:30
25F：→ watashino: 这样复杂度怎麽可能是N平方 11/30 18:30
26F：→ watashino: heap大这是没考虑到left不可能超过right吧 11/30 18:34
27F：推 me356500: 底下的写法就上面的换种写法不是吗？ 哪里来的N^2 11/30 18:36
28F：推 watashino: 另外hobnob大讲的跟我理解的不同 11/30 18:37
29F：→ watashino: 通常是在面试过程中改进成最佳解才是一个好的面试官想 11/30 18:38
而且这两个解根本一样... 我只能猜说他觉得 for 里面有 while 可能在实际写 code 不是一个好习惯？
30F：→ watashino: 要的吧 11/30 18:38
31F：推 s06yji3: 面试官不一定是对的。 11/30 18:41
32F：→ ken1325: O(N)+1 11/30 18:43
33F：推 NTHUlagka: 应该是O(n)吧 同一个位置最多跑两次阿 11/30 18:45
34F：推 ok8752665: 用amortized 去看就好啊 到底怎麽跑到N^2 11/30 18:53
35F：推 toole: 面试官不一定是对的，但跟会影响面试结果的人吵只是自找麻 11/30 18:53
36F：→ toole: 烦 11/30 18:53
我没有真的跟他"吵"起来(我有忍住)，就有点像是：他说我错->我解释我是对的->他说我错....无限循环
这种情况应该怎麽办...
37F：推 gaymarriage: 就是O(N) 你衰 运气不好 11/30 18:54
38F：推 NTHUlagka: n平方发生在面试官是白痴的时候 Bytedance就这？ n/10 11/30 18:55
其实真的不能说他是错的，我有一直强调说 O(N^2) 是一个松的 bound，用我的分析方法可以压到 O(N)
39F：→ NTHUlagka: 要乘的不是n/10是10 亏你还台大的 其他系去蹭？ 11/30 18:55
40F：→ watashino: 我也有跟面试官无限循环的经验 11/30 19:00
41F：→ watashino: 後来用例子说服他 他说错的 11/30 19:00
42F：→ watashino: 但耗很多时间 11/30 19:00
我实际拿测资 dry run 他都能说我错了该怎解Orz，他说我们对复杂度的理解不同= =
43F：推 nek0t1m: 跟面试官吵没意义，吵赢也可能被评沟通不良，不如赶快提 11/30 19:05
44F：→ nek0t1m: 出第二种解法move forward 11/30 19:05
其实一开始是这样的：我以为他要测我是不是真的理解复杂度怎麽估才故意 challenge 我
如果我直接换解法 move forward 我怕是扣分（代表我前面写那个是没把握乱写的），结果吵到一半才发现他是真的觉得我错
45F：推 BBSealion: 你是对的，但面试官最大，你的"最佳策略"应该是简单常 11/30 19:06
46F：→ BBSealion: 尝试，发现他无法理解就快速放弃，找他的智商能看懂的 11/30 19:07
47F：→ BBSealion: 做法，浪费时间是最不划算的，除非你也没差这个 offer 11/30 19:07
但我要怎麽分辨他是真的不懂还是只是在挑战我的分析QQ，我一开始以为他是要我解释更清楚，结果辩到一半才发现不是
48F：推 ABuJiuHaoBun: 抖音一响 11/30 19:08
49F：推 s06yji3: 这个upper bound O(N^2)是什麽意思？ 11/30 19:08
我用词不太精确，应该说 Big O 数学上本来就可以估比较大，所以他说 O(N^2) 我没说他错，只是我跟他解释可以分析到变成 O(N)
50F：→ linnom: 你是对的，但面试官才是对的 11/30 19:11
※ 编辑: NTUmaki (123.204.135.123 台湾), 11/30/2022 19:12:24
51F：推 s06yji3: 你的实作是O(N)，除非是给他台阶下，不然我不知道这O(N^2 11/30 19:13
52F：→ s06yji3: )哪里来的XD 11/30 19:13
53F：推 johnny94: 换个角度想，如果你进去公司遇到类似的问题，你会想跟这 11/30 19:13
54F：→ johnny94: 种人工作吗？ 11/30 19:13
55F：→ johnny94: 现在是o(n) 以後就是各种 design 问题，有得吵的。不要 11/30 19:14
56F：→ johnny94: 进去也是好事啦 11/30 19:14
57F：推 a731977: 是n没错 可能面试官讨厌那种写法 11/30 19:17
58F：推 NTHUlagka: 澄清一下上面那个不是在呛你台大 是某h在那乱分析 11/30 19:21
59F：推 SHANGOYANYI: 其实很简单啦 他要的只是程式码上看起来的O(n) 不是 11/30 19:24
60F：→ SHANGOYANYI: 实际执行上的O(n) 反正两个loop看起来就很不O(n) 11/30 19:24
61F：推 BBSealion: 回应原Po 上面问题，其实就直接提问就好，请问面试官 11/30 19:36
62F：→ BBSealion: 希望我证明这个做法是 O(N)，还是换一个写法，如果期望 11/30 19:37
63F：→ BBSealion: 只用一个回圈的话，我也可以改写成xx，但他本质上一样 11/30 19:37
64F：推 Gaogaigar: 你在远端吗? 是的话可能他根本分心在别的事情 11/30 19:37
65F：推 jackfantasy: sliding window 复杂度 worst case 就是 2N，每个元 11/30 19:38
66F：→ jackfantasy: 素最多进出一次 window，r 走过该元素表示进 window 11/30 19:38
67F：→ jackfantasy: ，l 走过该元素表示出 window 11/30 19:38
68F：→ jackfantasy: Best Case 是 N ，就是你的 r 一路走到底都不用内缩 11/30 19:39
69F：→ jackfantasy: l，最终你的 window 等於整个数列长度，那每个元素就 11/30 19:39
70F：→ jackfantasy: 是过一次 11/30 19:39
71F：→ jackfantasy: 所以不管怎麽样这方法就是 O(N) 11/30 19:39
72F：→ jackfantasy: 演算法的复杂度基本看worst case，就像排序会说 NlgN 11/30 19:41
73F：→ jackfantasy: 不会因为 Best Case 可以到N 就说他是 N 11/30 19:41
74F：→ jackfantasy: 这题就算你用 hashmap 纪录每个元素的位置来一次内缩 11/30 19:43
75F：→ jackfantasy: L 到位，worst case 还是看你的字串每个字都一样的 11/30 19:43
76F：→ jackfantasy: 时候，就是每个字进出一次，那复杂度还是 O(N) 没有 11/30 19:43
77F：→ jackfantasy: 因为这样比较快的说法 11/30 19:43
78F：推 jackfantasy: 只能说运气占面试很大一部分 11/30 19:45
79F：推 kevin9527: 2N吧，请他举出一个n^2的例子啊 11/30 19:47
80F：推 kevin9527: 面试官搞不好比你菜 找别家吧 11/30 19:50
81F：推 hank8451: 可以理解一开始看到的时候会以为是O(n^2) 11/30 19:53
82F：→ hank8451: 但解释半天都不懂也太扯… 11/30 19:53
83F：→ watashino: 这串讲的用hash来记位置是不是都没考虑到中间其他元素 11/30 19:59
84F：→ watashino: 也要删除 11/30 19:59
85F：推 jackfantasy: 用 hashmap 记位置的话也不用 set 了 11/30 20:06
86F：→ jackfantasy: 每次 valid window 算一次 r-l+1 跟目前的 max取大的 11/30 20:06
87F：→ jackfantasy: 就好 11/30 20:06
88F：→ watashino: 没看到详细内容不敢断定 11/30 20:11
89F：→ watashino: 但楼上做法应该是错的 11/30 20:11
91F：推 me356500: 不用啊 每次都会更新到最新的 我刚ac没问题 11/30 20:17
92F：→ watashino: OK 看来确实是描述不清楚的问题 11/30 20:21
93F：→ watashino: 抱歉 11/30 20:21
94F：推 genius945: 跟面试官僵持这个意义不大，讨论一下没共识就认定他的 11/30 20:27
95F：→ genius945: 理解有问题然後直接照他要的给就好了 11/30 20:27
96F：推 tallest: O(N) +1 11/30 20:40
97F：→ tallest: 不过想想如果上了要跟这种人当同事 应该也是蛮痛苦的 11/30 20:40
98F：推 hijamoya: 2n无误 11/30 20:42
99F：→ jerry771210: 会是英文表达不好？ 11/30 20:43
中文面试
100F：推 GinginDenSha: O(2N）没错 遇到这种就运气不好 面试官是中国人吗？ 11/30 20:52
从用词跟口音来看应该是中国人没错
101F：推 hijamoya: 可能面试官只背到用map记住最後一个character的位置的 11/30 20:54
102F：→ hijamoya: 那个答案 11/30 20:54
103F：推 steven95421: 敝司智障太多QQ 11/30 21:18
104F：推 h30306: 之前听说抖音刷题都会考到Hard等级 原po面演算法工程师但 11/30 21:33
105F：→ h30306: 是都遇到medium而已吗？ 11/30 21:33
106F：推 Lin25K: 太雷了吧 第一眼看不出是O(n) 问题就很大了吧 11/30 21:51
107F：推 sasoman: sliding window worse case就O(2n) 11/30 22:05
109F：推 sarsman: 你是对的 11/30 22:31
110F：推 BigCockman: 这面试官程度也太差 双层回圈就无脑觉得是n平方？ 11/30 22:32
111F：→ sarsman: 面试最气的不是抽到难题，而是遇到雷包面试官== 11/30 22:32
112F：→ BigCockman: 说真的久没刷题不熟没差 好歹帮人面试前看看解法 原 11/30 22:34
113F：→ BigCockman: po这题写法算很常见的了 11/30 22:34
114F：推 holebro: 烂面试官 11/30 23:08
115F：推 GinginDenSha: 不意外 中国一堆垃圾充斥各种公司 智障面试文化洪流 11/30 23:09
116F：→ GinginDenSha: 下的猪 印度仔更不用说 无限繁衍的蛆虫 11/30 23:09
117F：推 CodingDuck: 字节跳动算了啦 11/30 23:45
118F：→ CodingDuck: 上不了市不知道未来在哪的中国欺上瞒下公司，台湾人 11/30 23:45
119F：→ CodingDuck: 值得更好的。 11/30 23:45
120F：推 viper9709: 跟这种人当同事 应该也是蛮痛苦的+1 12/01 00:00
121F：推 hank55663: 阿就potential function 是r-l 所以每次增加常数(r+=1) 12/01 00:41
122F：→ hank55663: 位能不会低於0 大概这样 叫面试官回去读演算法吧 12/01 00:41
123F：推 paul800526: O(n)+1 12/01 00:43
124F：→ MoonCode: 很简单啊，第一个写法你自己觉得好读吗？ 12/01 00:53
125F：推 pichubaby: 和他说：面试官先生，请不要直接数两层回圈就说他是N2 12/01 01:07
126F：推 pichubaby: 所以才说面试要考LCS等级的DP，因为面试是双向的，这样 12/01 01:10
127F：→ pichubaby: 才有机会意识到未来同事程度如何 :) 12/01 01:10
128F：推 MoonCode: 楼上应该收到很多履历了吧 12/01 01:12
129F：推 Lhmstu: 老实说，确实第二种比较好，就程式码来说的话 12/01 02:35
130F：推 f12sd2e2aa: 好好笑 有人振振有词说一堆 最後补出一个错误的结论 12/01 02:37
131F：推 sarsman: 要求可读性的话就不该扯复杂度，而且还乱扯 12/01 03:34
132F：推 yumekanau: 面试官演算法程度有点差xd 背进去之後忘记怎麽分析了 12/01 03:44
133F：→ yumekanau: 吧 12/01 03:44
134F：推 sxy67230: 先说，第一种解法肯定不会是N^2，你又不是遍历N两次， 12/01 05:16
135F：→ sxy67230: 考官的资结要去重修了，再者主考官提出的下面那种解法w 12/01 05:16
136F：→ sxy67230: hile会执行到2N次，用hash记住最大可以缩到N次 12/01 05:16
137F：嘘 handsomeLin: 认真回，他质疑你的while是n的时候，总operation也是 12/01 05:28
138F：→ handsomeLin: 2n而已，他数学不好就指出来就行，解释也是工作的一 12/01 05:29
139F：→ handsomeLin: 环 12/01 05:29
我有解释 while 里面的 l+=1 总共最多执行 N 次，他说他知道，但他说复杂度分析就是外面 O(N)，里面 O(N) 所以乘起来是 O(N^2)
最後他就说我跟他对复杂度的理解不同，我也不知道该怎麽解释了
※ 编辑: NTUmaki (123.204.135.123 台湾), 12/01/2022 05:44:12
140F：推 yyhsiu: 运气不好无法 你看推文 面试官不是唯一不懂的 12/01 08:23
141F：推 s06yji3: 我喜欢第一种 12/01 08:43
142F：推 louisfghbvc: 第一种解法绝对是O(N)怎麽是O(N^2) 假设for回圈有一 12/01 08:43
143F：→ louisfghbvc: 次l跑满 下一个r就不会跑了 那个l又不会reset, reset 12/01 08:43
144F：→ louisfghbvc: 成0才是O(n^2) 12/01 08:43
145F：推 A4P8T6X9: O(N) 12/01 09:12
146F：推 aa06697: 这面试官以前上演算法应该有被当掉吧 复杂度分析哪是看几 12/01 09:39
147F：→ aa06697: 层回圈去乘 12/01 09:39
148F：→ aa06697: 只能说你运气不好 12/01 09:40
149F：推 jobintan: 找工作就七分实力三分运气，运气差会遇到不专业但又爱硬 12/01 09:58
150F：→ jobintan: 拗的interviewer，这无解。 12/01 09:59
151F：推 hidog: 面试官未必是对的，但你们不适合 12/01 10:28
152F：→ hidog: 这种情况没上不是坏事 12/01 10:28
153F：推 dani1992: set操作不是logN吗？这样复杂度是O(NlogN)? 12/01 11:14
154F：推 xdlow: to 楼上 python 的 set 是 hash table 实作的 所以会是 O 12/01 11:27
155F：→ xdlow: (1) 12/01 11:27
156F：推 gonna01: 争赢好像没什麽优点 12/01 12:09
157F：推 Alex548291: 回楼上 争赢没有优点？啊就面试官观念错还不能讨论喔 12/01 12:26
158F：→ Alex548291: 以後工作只要主管说用A方法做 即使效率明显低落 也继 12/01 12:26
159F：→ Alex548291: 续用A方法？什麽鬼观念啊 12/01 12:26
160F：→ Ekmund: 看到一半就懒了...我也遇过类似情况 说真的对方就是图个 12/01 12:28
161F：→ Ekmund: 心里乾净 避免现实场景规则变化时 你code复杂度跟着改变 12/01 12:28
162F：→ Ekmund: 不能说谁对谁错 但这要争是争不完的 不如换个角度看 你们 12/01 12:28
163F：→ Ekmund: 其实不适合共事 也就不用浪费时间吵了 XD 12/01 12:28
164F：推 Alex548291: 是说连这个也看不出来是O(N)当什麽Algorithm Engineer 12/01 12:35
165F：→ Alex548291: 面试官 是不是文组没修过演算法啊 12/01 12:35
166F：推 can18: 面试官不理解 amortized 的概念吧 要在面试的时间内教会他 12/01 12:43
167F：→ can18: 不太可能 12/01 12:43
168F：→ can18: 只能说运气不好 12/01 12:44
169F：推 stkoso: 之後通常会有interview survey 记得写上去 12/01 12:55
170F：推 gamania0258: 说真的 你都说服他了还跳针 没上也好 共事起来应该很 12/01 13:06
171F：→ gamania0258: 痛苦 还是其实跳针应对也是考察一环XDDD 12/01 13:06
172F：推 Kimheeche: 也可以换个方法说服他 跟他说N2的情况 有N+N次 或是根 12/01 14:46
173F：→ Kimheeche: 据高斯定律N(N+1)/2 也是N2 但sliding window 的左右 12/01 14:46
174F：→ Kimheeche: 指标肯定不是每轮扫N次或是逐次增加 最多就同个元素被 12/01 14:46
175F：→ Kimheeche: 左右各碰到1次顶多2N 12/01 14:46
176F：推 zanyking: 你挑战的是BigO的定义，BigO本来就不细，回圈数看是n^2 12/01 15:29
177F：→ zanyking: 就是n^2，他要的就是程式码看上去就『不可能』是n^2，而 12/01 15:30
178F：→ zanyking: 不是『详细』分析完才不是，很多时候没有那种时间去分析 12/01 15:30
179F：→ zanyking: 可以程式码看上去就不可能那就这样做可以保底 12/01 15:31
180F：推 zanyking: 先注解，我已经接受1+1=5你是对的了，所以... 12/01 15:35
182F：推 olmrgcsi: 笑死 上面某h头脑都不带出来还在大谈 12/01 15:53
183F：→ stkoso: 第一个while加上l<r的条件应该就够好懂了吧 12/01 16:10
184F：→ stkoso: 这看上去就不会是n^2 你看不出来可以再看一眼 12/01 16:11
185F：推 SRmoisTEH: O(N) 面试官该回去复习algo END 12/01 16:21
186F：→ baobomb: 面试官很明显死背的 他可能根本不知道什麽是sliding wind 12/01 16:56
187F：→ baobomb: ow 遇到这种其实也不用跟他吵 有时候写出让不懂的人看的 12/01 16:56
188F：→ baobomb: 懂的code也是工作的一部分 除非你是单干王 12/01 16:56
189F：→ baobomb: 然後Bytedance的hiring bar本来就不高 只要你会讲中文 通 12/01 16:57
190F：→ baobomb: 常就过50% 剩下就刷题而已 12/01 16:57
191F：推 devilkool: 感觉你没上的话是好事 12/01 19:07
192F：推 quickey: 跟中国人面试挺痛苦的 12/01 19:12
193F：推 kingofsdtw: 这很讲脸缘 12/01 20:20
194F：→ kingofsdtw: while不是不能用，只是有人看到就倒蛋 12/01 20:21
195F：推 abccbaandy: 就说考这种通常也只是背答案而已...不意外啦 12/01 21:06
196F：→ peter98: 应该说 其实回圈用双层而且两个回圈的条件逻辑不是一致 12/01 21:20
197F：→ peter98: 就会有可读性的问题 12/01 21:20
198F：推 kuochuwon: 难得这个版有讨论纯技术的串 推 12/01 21:32
199F：推 sunhextfn: 是O(N) 12/01 22:13
200F：推 drysor: monotonic queue / stack 之类的问题起手式就是 for + wh 12/01 22:36
201F：→ drysor: ile ，或是某些区间问题用 priority queue + hash 也会这 12/01 22:36
202F：→ drysor: 样写吧…为啥看到 while 要倒弹 12/01 22:36
203F：→ sxy67230: 某楼真的知道bigO的含义吗？bigO是虽然是粗估worst cas 12/01 22:37
204F：→ sxy67230: e的状况，但是第一种写法的内回圈也不是遍历N，函数上 12/01 22:37
205F：→ sxy67230: 表达还是线性的，根本不是看看你用两个回圈就是N^2这回 12/01 22:37
206F：→ sxy67230: 事好吗 12/01 22:37
207F：推 vir09700929: 我觉得整份程式码很易读乾净，典型sliding window 题 12/01 22:47
208F：→ vir09700929: 目，时间空间都O(N)，看来是面试官问题… 辛苦原PO 12/01 22:47
209F：推 dani1992: 原来python set是hashtable实作 12/02 00:00
210F：→ dani1992: 不过这样hashtable worst case是O(N)，复杂度是O(N^2) 12/02 00:01
211F：推 lovdkkkk: 在这个 case 基本上不会, 因为会不断在 1 就被 remove 12/02 00:38
212F：→ lovdkkkk: 除非找得到 N 个会发生 collision 但实际上不同的字 12/02 00:39
213F：推 seanwu: 因为是字串，就算套两层loop每次重扫也只会有255N=O(N)啊X 12/02 00:57
214F：→ seanwu: D 要写成N^2除非傻傻跑完不break吧，原po就运气不好碰到不 12/02 00:57
215F：→ seanwu: 会算复杂度的面试官 12/02 00:57
就讨论到这吧.. 我不认为这个面试官能力很差，他考的其他题目都蛮 critical 的，很多我都答不太出来，只是在复杂度那块他特别坚持己见而已@@
※ 编辑: NTUmaki (123.204.135.123 台湾), 12/02/2022 04:12:44
216F：推 lance8537: 跟他说别杠 杠就是你对 12/02 06:22
217F：推 Alex548291: 那个zanyking跟h开头的要不要包一包去重修演算法啊 12/02 07:02
218F：推 snailpon: 面试官在测试「听话指数」跟「奴性」，一切都说得通了XD 12/02 09:53
219F：推 Awenwen: 辩论2N vs N^2 在面试胜算不大，要直接实际举各两 12/02 11:04
220F：→ Awenwen: 个字串的例子去 12/02 11:04
221F：→ Awenwen: 说明然後直接演算才有机会说服已经认为自己模糊的 12/02 11:04
222F：→ Awenwen: 估算是对的人， 12/02 11:04
223F：→ Awenwen: 某方面也是种沟通能力的考验？ 12/02 11:04
224F：→ kiki86151: 其实面试要challenge面试官是下策 且想要说服人不能只 12/02 11:44
225F：→ kiki86151: 说说 要直接具体证明 只举case某方面不够严谨 除非反证 12/02 11:44
226F：→ kiki86151: 法这种 且你怎知道举的case一定是worst 还叫人举 虽然 12/02 11:44
227F：→ kiki86151: 这演算法通常图解POC很容易观察到worst case确保一定2n 12/02 11:44
228F：→ a27417332: 我是觉得Q2A2当证明已经足够了吧 12/02 13:02
229F：→ a27417332: 是面试官一直觉得有错，发文者才请他举反例证错 12/02 13:03
230F：→ peter9s3b: 面试官可能不想理解跟自己想法不同的作法。之前面有这 12/02 13:20
231F：→ peter9s3b: 种感受 12/02 13:20
232F：→ kiki86151: 要证l不会超过r啊 用讲的谁都会讲 我猜面试官懒得想 一 12/02 13:22
233F：→ kiki86151: 个for一定是n 两个for不考虑细节 直观无脑看起来就n^2 12/02 13:22
234F：→ a27417332: 那面试官要问为什麽l不会超过r而不是跳针吧XD 12/02 14:15
235F：→ a27417332: 合格的面试官对自己出的题常见做法应该都要足够熟悉吧 12/02 14:17
236F：→ a27417332: 不然至少也要够聪明去了解面试者想说什麽 12/02 14:17
237F：→ a27417332: 不多准备又不想认真听别人说什麽也是挺恐怖的表现 12/02 14:18
238F：→ a27417332: 除非这样的表示是公司期望展现的文化:) 12/02 14:28
239F：推 zanyking: Alex548我就反串啊，都说1+1=5是对的，选完不能崩溃吗 12/02 15:07
240F：→ leolarrel: 人与人的交流比用程式码跟电脑交流难太多了 12/02 15:50
241F：→ kiki86151: 可抱怨面试官不合格 跳针 不好沟通啦 但对通关没帮助:) 12/02 15:53
242F：推 gofigure: algorithm engineer考这种也太水 12/02 19:46
244F：推 s8952889: 面试官没修过演算法…话说这串也太多把worst case跟bigO 12/03 03:15
245F：→ s8952889: 混在一起谈了吧，bigO纯粹是upper bound跟worst case没 12/03 03:15
246F：→ s8952889: 关系，worst case也可以用theta或omega表示 12/03 03:15
247F：推 Gorilla1234: 白痴面试官丢爆公司的脸... 12/03 12:33
248F：→ acgotaku: 面试争论这题没啥意义呀 这题都做烂了 12/03 19:49
249F：推 youtuuube000: 面试官的症结点应该是忘了set是hash而不是array所以 12/03 20:02
250F：→ youtuuube000: 查找只要big(1)吧… 12/03 20:02
251F：推 gsrr: 面试不合就不要去工作 12/03 21:28
252F：推 xluds24805: O(N) 没错，不过这要解释起来可能不是那麽直觉，面试 12/03 22:03
253F：→ xluds24805: 官也一时没考虑清楚 12/03 22:03
254F：推 masturbateee: chatGPT笑死 12/04 15:57
255F：推 ManOfSteel: 惨，面试官，在网路上被鞭到爆。 12/04 21:27
256F：嘘 Murasaki0110: 好啦吵赢了好棒棒 拿个reject开心吗 12/05 13:29
257F：→ integritywei: bytedance本来就程度不怎麽样, 不意外 12/05 13:36
258F：推 bitcch: 下方写法每次执行不保证r一定前进 其实就上面的变形也是2N 12/05 20:20
259F：推 nicepeter: 时间复杂度是O(n)没错，很典型的sliding window算法 12/05 21:26
260F：推 daddy29: 这题如果用两个WHILE 写他应该爆炸 蛮可悲的中国人 12/08 02:35
261F：→ daddy29: upper bound 根本到不了O(N^2) 你这句话反而给他信心 12/08 02:36
262F：→ daddy29: 直接留一句傻逼中国人断线 跟hr回报换人面试就好 12/08 02:36
263F：推 daddy29: 好像是我傻逼了,你第一段代码真的是O(n^2) 12/08 16:28
264F：→ daddy29: 用aaaaaaa 去算的话 你原本代码执行 O(n * (n-1)) 12/08 16:29
265F：→ daddy29: 第二段代码if最多执行一次 最坏是 O(n+n) 第二段效率高 12/08 16:31
266F：→ brucetu: 楼上 第一段程式码 aaaaa 不会执行 n*(n-1) 12/08 17:35
267F：→ brucetu: L=0在最外面 回圈里面L+=1 当然不可能跑到超过N次 12/08 17:37
268F：推 s06yji3: d大要确定捏 12/08 18:24
270F：→ daddy29: 垃圾ai跟我说会执行8*8=64次 贴代码以後叫我有疑问提出 12/08 22:59
271F：→ daddy29: 提出以後给我当机 重新再问一次他娘的又变成O(n)了 12/08 22:59
272F：推 daddy29: 想到还是好气 补个干 干 12/08 23:03
273F：→ peter98: 好像的是还有人不懂装懂 呛人去念演算法课本的结果自己 12/11 00:23
275F：→ peter98: 奇闻一定要共赏 12/11 00:24
276F：嘘 new122851: 不能纯聊天？ 一定要leetcode争这个？ 12/12 11:05
277F：推 KH22: 还好你没进去跟这样的人当同事 12/19 04:28