作者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/m.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