作者fshfsh (鱼~*)
看板Soft_Job
标题Re: [讨论] 我就问，刷题强者的实务表现?
时间Thu Oct 6 07:56:31 2022
※ 引述《goodson (blahblah)》之铭言：
: 最近一次面到刷题的公司...感觉已经走火入魔了，
: 考试考到难的程度，比 Google 还难
: 去年就面过一次，当时考题 Easy ~ Medium
: 隔了一年还在找人，人资看我资历主动邀我面试，
: 却考得更难...有真心要找可以解决问题的人吗?
: 都没有照照镜子，贵司的薪水可以比 G 还高吗?
: 我考得过 Hard，还需要领你这 120 万左右年薪?
: 我近十年经验，可以拿出数十万下载量
: 还在线的作品不被重视，
: 却考 Hard 难度的考题来羞辱人浪费我的时间，
: 我看了考题十分钟就 submit 不爽写了。
: 当然这样的状况不只一间公司，
: 我就不指名道姓了
: 大概是被刷题进去的人占到主管位，
: 所以也就信刷题这一套。
: 但我的疑问是，刷题进去的人，
: 到底产出如何? 只会写那些数学题型类似的演算法，
: 对於实作没有足够经验，到底可以做出什麽啊?
: 有没有人跟刷题派合作过? 真的刷题高分等於强吗?
我亲身经验，刷题非常有用
347 top k frequent elements
23 merge k sorted lists
56 merge intervals
一些基本的工具如 recursion , tree , map , deque ，比较稍微难的像line sweep , biwise
可以说，如果我没碰过这些题目和工具，那麽我之前做的东西绝对难产，为什麽？
只会array list的人，面对复合型问题时，要怎麽写高效能程式？
我曾经看过有人在工作上使用四重巢状回圈，要不是那时资料量还非常小，不然我看某时某刻一定会有人该 为什麽系统卡住了，不会动也没报错欸，console也没印东西是怎样T^T
我不懂为什麽你要因为你解不出来，就否定掉刷题整件事欸
这就好像一个鲁蛇整天怪东怪西，都是they的错
阿你是十年经验强者，是只有几间公司的面试机会吗？
我前同事现在也在挑公司，人家资策会出来的，到现在也才工作三年，怎麽现在也是年薪120起跳在挑
（附带一提，我也算是资策会出来的，要说一句昨日我以资策会为荣，今日我以资策会为耻）
那我真的蛮好奇你的十年工作经验到底都在干嘛，怎麽跟别人三年差不多
我另一个前同事，在公司待了5年啊，写code能力比我资策会时候一些同学还差，有时候跟他共事都会脑袋充血，写code又慢又一堆漏洞，最後我选择自己写好偷偷盖过去
年资真的在这一行不代表什麽，难道Google 微软 Apple那些超级大厂都是老人吗？人家的团队去看照片都年轻的很
对了，再补充你一句，刷题不是考「数学模型」，是时间复杂度和空间复杂度，除非你是在写DP
--
昨日我以资策会为荣，今日我以资策会为耻
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.193.252.168 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1665014195.A.798.html
※ 编辑: fshfsh (123.193.252.168 台湾), 10/06/2022 07:58:23
1F：→ Firstshadow: 好= = 10/06 07:59
※ 编辑: fshfsh (123.193.252.168 台湾), 10/06/2022 08:18:31
2F：→ Csir: 幸好我while回圈每次都不会终止 10/06 08:53
3F：→ leolarrel: 西哥你... 10/06 09:35
4F：推 stupid0319: 推签名 10/06 09:39
5F：推 chatnoir: 为什麽今日以资策会为耻? 10/06 09:41
6F：→ leolarrel: 这个资策会是指转职仔上课的那个资策会吗? 10/06 09:48
7F：推 Hsins: 资策会不好吗？可以一边工读博士，还行吧>< 10/06 09:53
8F：推 littlebroken: 应该是在讲最近那件事 高XX 10/06 09:56
9F：→ littlebroken: 讨论就跑题了 还是继续战刷题吧 10/06 09:57
10F：推 hobnob: 推这篇，我之前真的有一个需求用到了binary search 找inde 10/06 10:13
11F：→ hobnob: x，当时的需求跟题目一摸一样 10/06 10:13
12F：→ lchcoding: 西哥你财富自由了，用软体养生...？ 10/06 10:30
13F：→ ntpuisbest: 想问一下，一般在使用linkedlist我都是Call library, 10/06 11:18
14F：→ ntpuisbest: 但是leetcode那题merge 2 sorted lists 10/06 11:18
15F：→ ntpuisbest: 是不是就要自己去设node的class这样才能在实务上用那 10/06 11:18
16F：→ ntpuisbest: 题的解法? 10/06 11:18
17F：→ ntpuisbest: 另外想问什麽场景你会需要去merge two sorted list 10/06 11:19
先抱歉一下，我其实是要说 merge k sorted list
https://leetcode.com/problems/merge-k-sorted-lists/
第1个问题，我不太确定你是用什麽语言
我自己是用Java，那麽并不是我要自己设node class，而是你的执行环境本身就已经存在ListNode class了
题目也只允许你回传ListNode 类别，自然你不能用Java内建的LinkedList
第2个问题，我假设一个情境
有家鸡排店会从k家厂商进不同数量的鸡排，鸡排我们可以当作只有保存期限一种属性
class 鸡排 {
Date expireDate;
}
就算是同一家厂商来的鸡排，保存期限也不一定一样
当有顾客来的时候，鸡排店老板固定会用「保存期限最接近过期的鸡排」，并且「已过期的鸡排」不使用
现在请写一个程式来符合这个需求。
PS：每家厂商送来的鸡排是用保存期限来排序的，你可以当成是List<鸡排>。
那麽你可能会说，我创一个ArrayList，然後把所有商店的所有鸡排都放到这个List里面去，再用保存期限去排序
排序是O(nlogn)，n是鸡排的总数，每次取出（倒序排然後每次都从最後一位取）是O(1)
这样做确实也可以，但因为鸡排本身就排好了
我可以创一个PiorityQueue，然後把k家厂商的鸡排的第一家作为代表，放到PQ中
这麽一来，建立PQ时间复杂度就缩小成O(klogk)，每次取出为O(logk)，取完後再把下一份鸡排加回去O(logk)
另外，如果鸡排没有用完，由於PQ的特性，我共不会做完整的排序，而是取到哪排到哪
比方说我有3家厂商好了，每家厂商进1000000份鸡排，也就是k = 3，n = 3000000
如果你用第一种方法，那一定会排完这3000000鸡排，再一份一份拿给顾客
第二种方法，就相当於我这3家厂区放入比较池，拿最接近过期的给他，再把那家的下一片鸡排放到比较池
18F：→ Hsins: 楼上你这问题要先看是哪个语言的哪个函数库，在实务上能不 10/06 11:23
19F：→ Hsins: 能那样用，要看那个函式库里怎麽去实作 Linked List 和他 10/06 11:23
20F：→ Hsins: 相关 API 的。 10/06 11:23
21F：→ Hsins: 以 Java 的 java.util.LinkedList 来说，去检查他实作的程 10/06 11:26
22F：→ Hsins: 式码，可以知道跟你所说的自己设 node 的 class 也没太大的 10/06 11:26
23F：→ Hsins: 差别… 10/06 11:26
※ 编辑: fshfsh (123.193.252.168 台湾), 10/06/2022 12:46:26
24F：推 alihue: 开发搜寻引擎就用得到 merge two sorted list 了 10/06 12:19
25F：→ peter98: merge two sorted list的应用明明很广 别说工作上了 大 10/06 12:22
26F：→ peter98: 学课本db课程也有教 DB的external sort就是merge multip 10/06 12:22
27F：→ peter98: le sorted listsarrays啊 10/06 12:22
28F：→ peter98: Lists/arrays 10/06 12:22
29F：→ peter98: 当资料量很大 没有辨法一次载入memory时 就可以考虑exte 10/06 12:25
30F：→ peter98: rnal sort 而另一种应用则是可以跟map reduce 结合 加速 10/06 12:25
31F：→ peter98: 大数据处理 这就是上面说的搜寻引擎 或者recommendation 10/06 12:25
32F：→ peter98: system也用的到 10/06 12:25
33F：→ peter98: 随便说都能有应用 我是不知道反对刷题的为什麽说没用XD 10/06 12:26
34F：→ peter98: 搜索引擎还可以往trie延伸 根本说不完 10/06 12:31
35F：→ Hsins: 经验告诉我不少人连 Trie 是什麽都不知道, 可能实务上不需 10/06 12:34
36F：→ Hsins: 要吧... 10/06 12:34
37F：推 ntpuisbest: 我没说没用，我自己目前也在刷题，只是目前我的工作没 10/06 12:35
38F：→ ntpuisbest: 用到，所以才会想问大家场景是什麽 10/06 12:35
39F：推 ntpuisbest: 回h大我是用java没错，我就在想lc的题目大部分input 10/06 12:38
40F：→ ntpuisbest: 都是head但是java的linkedlist(我记得他好像是double 10/06 12:38
41F：→ ntpuisbest: linkedlist没错),是不是就是因为他封好了，所以还是 10/06 12:38
42F：→ ntpuisbest: 自己写node比较适合，不然我也不知道他封好的状况下 10/06 12:38
43F：→ ntpuisbest: 怎麽去做断开link再接上的动作 10/06 12:38
API没有给你操作Node,你只能自己实作
44F：→ peter98: 喔 原来是认真发问XD 好的 那我会认真回你 自己写node比 10/06 12:43
45F：→ peter98: 较好 练leetcode就是在练功 自己弄node才知道什麽情况用 10/06 12:43
46F：→ peter98: dummy head可以省多事 10/06 12:43
47F：推 ntpuisbest: 像是leetcode有些design特殊的资料结构，lru我还理解 10/06 12:46
48F：→ ntpuisbest: 有用，而且还可以去call linkedhashmap但是像是min st 10/06 12:46
49F：→ ntpuisbest: ack max stack这种，各位前辈有用到过吗？ 10/06 12:46
基本上，有些题目出出来真的就是给你练功用的
比方说LRU，我记得Java某一个API就有内建的功能了
所以工作上确实是不会还要自己写（俗称造轮子）
但如果你能写出来，你会对List指标操作有更深一层了解
重点就是工作上遇到的东西不会永远都用基本API来解
如果你对这些基本操作理解很深，你就有办法自己写一个针对场景客制化的资结或演算法
这也是我从不觉得刷题无用的原因XDD
※ 编辑: fshfsh (123.193.252.168 台湾), 10/06/2022 12:57:13
50F：→ peter98: 这样对你写tree也有帮助 tree实务上用很广哦 tree相关演 10/06 12:48
51F：→ peter98: 算法还有DFS/BFS也很广 各个环环相扣 你终究要自己用nod 10/06 12:48
52F：→ peter98: e写tree的 所以先用node写list吧 10/06 12:48
嗯嗯 100%同意
Tree真的很好用 DFS/BFS都有用到
53F：推 alihue: 其实搜寻也不是典型的 trie 了，而是为了省记忆体改用 10/06 12:48
54F：→ alihue: FST ，先用 FST 找到词的 index 位置再去找词。 10/06 12:48
55F：→ alihue: 那些 leetcode 的资料结构顶多算是常识，实务上会有更多 10/06 12:48
56F：→ alihue: 考量如记忆体/或是在 disk 的 index 结构、 10/06 12:48
57F：→ alihue: 是否 immutable 、cpu overhead等。实务上需要的不是你是 10/06 12:48
58F：→ alihue: 否马上知道要用什麽，而是你能不能做好的 research 找到 10/06 12:48
59F：→ alihue: 最好的演算法 10/06 12:48
60F：推 Hsins: 那些知识是在 research 的同时, 用来判断适用性跟文章有没 10/06 12:50
61F：→ Hsins: 唬烂的…我想 n 想问的是实务上会是要自己写 node 还是怎样 10/06 12:50
62F：→ Hsins: ，那个要从实务面上评估需不需要调整；如果你想要直接访问 10/06 12:52
63F：→ Hsins: 操作封装好的 LinkedList 上 Node 的话，是不建议的，因为 10/06 12:53
64F：→ peter98: 实务上我是都用lib list（挖鼻孔） 10/06 12:53
65F：推 ntpuisbest: tree的话我知道mysql底层是b+ tree,然後霍夫曼编码也 10/06 12:54
66F：→ ntpuisbest: 跟二元树有关，另外inordertravesal也可以顺序印出资 10/06 12:54
67F：→ ntpuisbest: 料，还有什麽场景适合自己刻tree吗？以前有个物流前 10/06 12:54
68F：→ ntpuisbest: 辈说过他用了一堆tree,但他说他不想讲太多，我google 10/06 12:54
69F：→ ntpuisbest: 搜寻 binary tree real world example也没发现什麽， 10/06 12:54
70F：→ ntpuisbest: 再问问各位前辈了 10/06 12:54
71F：→ Hsins: 他是 private 的，或许可以透过 reflect 魔改（？），但这 10/06 12:55
72F：→ Hsins: 样就会打破他的权限，不太安全 10/06 12:55
※ 编辑: fshfsh (123.193.252.168 台湾), 10/06/2022 13:00:54
73F：推 ntpuisbest: 感谢原Po回答，谢谢 10/06 12:59
74F：推 alihue: 实务上如果你越接近开发 infra 才会更容易开发演算法，但 10/06 13:00
75F：→ alihue: 缺很少，别练了一堆结果去投 web api 的缺 10/06 13:00
笑死，不过现在很多前端都要问演算法资结了
※ 编辑: fshfsh (123.193.252.168 台湾), 10/06/2022 13:02:23
76F：推 ntpuisbest: 我发现原Po好像就是我提到的仓储物流前辈，不好意思@@ 10/06 13:01
你误会了吧，我不认识你啊XDD
77F：→ Hsins: 我是觉得前端也该问啦，有些网站一开起来风扇就在那转不停 10/06 13:03
78F：→ Hsins: ，开发者工具打开一看，做个排序写了好几层回圈、不然就是 10/06 13:03
79F：→ Hsins: 一直打 API 死循环的… 10/06 13:04
※ 编辑: fshfsh (123.193.252.168 台湾), 10/06/2022 13:07:05
81F：推 lovdkkkk: 觉得用 ArrayList 也一样，只是要多维护 head index 10/06 16:18
82F：→ lovdkkkk: 还比 LinkedList 少存几百万个 next pointer 10/06 16:18
83F：→ lovdkkkk: (指上面鸡排例子) 10/06 16:20
你讲的没错，但前提是传入的参数
以Leetcode来说，传入的参数是不计入空间复杂度运算的，只计算「额外」的空间使用
（其实想想也很合理，要是题目传参都直接 memory leak，那题目本身就不成立了）
那麽端看你参数传入的型态，看你是像题目一样传入3个鸡排List来排序，每个List各100万鸡排
还是照你说的，传入一个300万元素的ArrayList，以及传入k个index
如果是後者，一样也可以用PriorityQueue的方式来处理
差别就在PQ存入改成index指向ArrayList，因为ArrayList用index取值时间复杂度O(1)，所以没有问题
照理说，你这样处理确实少了pointer
但我很难想像真实场景会把k个鸡排厂排成一个ArrayList来传
毕竟假设鸡排厂要升级成一个物件，上面要加属性了，这个结构会完全失效
所以我可能会先去和传给我的人沟通叫他麦闹XDD
84F：推 lovdkkkk: 不过鸡排摊实体空间限制应该无法一次放几百万片鸡排还是 10/06 16:40
85F：→ lovdkkkk: 得拆成N万个冷冻柜 10/06 16:40
嗯。。Leetcode还有题目是小朋友分糖果，小朋友的数量限制最大是一亿XDD
※ 编辑: fshfsh (123.193.252.168 台湾), 10/06/2022 17:05:26
86F：→ Ekmund: tree的话 看过用heap去做timer 10/06 17:28
87F：→ Ekmund: 每个事件设到期时间 根据时间sort 10/06 17:29
88F：→ Ekmund: 底下挂一堆事件这样 10/06 17:29
89F：→ superpandal: 我只有一开始工作才一直用ArrayList 而且也稍微会考 10/06 18:29
90F：→ superpandal: 虑应用情境 除非一直以来都是使用别人的lib/框架 否 10/06 18:29
91F：→ superpandal: 则要比较好的完成事情肯定会愈来愈深入 10/06 18:30
92F：→ superpandal: 这些东西不一定刷题才会有 当然你说提早知道如何解刷 10/06 18:33
93F：→ superpandal: 题是有帮助的 但多半都是应用不到 而且应用场景没连 10/06 18:34
94F：→ superpandal: 结到你也不一定想得出来可以用某某方式解 10/06 18:35
95F：→ superpandal: 算是蛮认同实践才是检验真理的唯一标准 10/06 18:37
96F：→ superpandal: 而且很多内部功能都可以自己实现 10/06 18:38
97F：推 s25g5d4: 推前端考资结，之前写资料视觉化用 DFS 解环，然後副产物 10/06 20:23
98F：→ s25g5d4: (邻接矩阵)交给下一 phase 算排位，还好小时候刷过 UVa 10/06 20:23
99F：推 lovdkkkk: 一亿...应该分散在多个城市，变发糖员旅行问题 (无误) 10/06 20:31
100F：嘘 ryan2001: 说实在 这种二元辩论真的没什麽意义 10/06 20:50
101F：推 dapple: 资策会付钱让你去美国念博士回来还不用绑约可以直接跳槽 10/06 20:59
102F：→ dapple: 不是很棒吗？ 10/06 20:59
103F：推 s25g5d4: 资策会本来定位不就这样？ 10/06 21:21
104F：推 oopFoo: sort 3百万？现在电脑 sort 1亿笔资料也在瞬间而已。 10/06 21:37
105F：→ oopFoo: 有时笨方法不笨因为电脑太快了。 10/06 21:38
嗯嗯 好有道理
看来各大院校的资工系可以删掉演算法和资结的课程了
反正电脑越来越快，我写10层巢状回圈总能解决问题吧～
看来我只要会写回圈和if就能进Google了呢
106F：→ peter98: sort 1亿笔资料也在瞬间阿 XD 唬烂不打草稿 你的电脑一 10/06 22:41
107F：→ peter98: 整套/整批下来要多少钱 才能在不用特殊演算法的情况下 10/06 22:43
108F：→ peter98: 瞬间sort完1亿笔data? 10/06 22:43
109F：推 viper9709: 感谢分享 10/07 00:10
※ 编辑: fshfsh (123.193.252.168 台湾), 10/07/2022 07:18:17
110F：推 WaterLengend: 那个ID就不用跟他认真了 10/07 10:40
111F：嘘 avril9950: 刷题的至少会 BFS/DFS，实务上很多东西都要碰到 tree 10/07 11:46
112F：→ avril9950: 然後一堆天才在那边乱写ㄏㄏ 10/07 11:46
113F：→ lazarus1121: 以实务来看，鸡排在放入时排序就好了吧 10/07 12:48
114F：→ lazarus1121: 把off line时间考虑进去，就不用太高深的演算法了 10/07 12:49
115F：推 hank55663: 一亿笔资料在用n^2排序的做法下要跑一整年欸 10/07 13:54
116F：推 Hsins: 量子电脑啦>< 10/07 14:21
117F：→ daddy29: 看工作需求程度 有些dp写起来就是简单方便快 分支少 10/07 14:57
118F：→ daddy29: 前提是你得先懂这个算法 10/07 14:57
119F：推 DDR678: 就推以资策会为耻这句 10/07 16:59
120F：推 viper9709: 量子电脑XDDD 10/07 17:36
121F：→ k798976869: 发哥也有在研究量子运算 有兴趣的博士可以去应徵 10/07 17:47
122F：→ k798976869: 而且不用刷题 10/07 17:48
123F：→ jerry840622: 刷题很有趣欸 现在看到程式码都会想降低复杂度 10/07 18:50
124F：→ ku399999: 前端很多连双for loop写不出来 或Map/Set不会用 都算了 10/08 00:53
125F：→ ku399999: fizzbuzz都写错 10/08 00:54
126F：→ ku399999: 这种的就不要说考这个有什麽用了吧... 10/08 00:54
127F：推 LincolnBoy: 一亿笔资料只要瞬间 太猛了 我想要那样的电脑 10/08 00:56
128F：推 ADEMAIN: 量子电脑XD 10/08 15:47
129F：嘘 abc21086999: 团队看照片年轻的很？我在电梯遇到的FTE怎麽看起来 10/09 01:47
130F：→ abc21086999: 都4、50岁 10/09 01:47
131F：嘘 zo4j4: 资策会出来真的强的能用的少数，不要误导大家... 10/15 09:11
132F：→ asonge0000: 重点不在於你在工作中会不会开发演算法 而是在於程式 10/31 20:36
133F：→ asonge0000: 语言都帮你包装好的API 你有没有这个知识判断使用哪 10/31 20:36
134F：→ asonge0000: 样的资料结构跟算法对效能比较好 如果你连这些基础知 10/31 20:36
135F：→ asonge0000: 识都不知道要怎麽样优化效能？ 10/31 20:36