[請益] 面試白板考題目的時間複雜度

看板Soft_Job作者 (馬路柏油)時間2年前 (2021/08/17 01:40), 編輯推噓24(24推 0噓 48→)
留言72則, 29人參與, 2年前最新討論串2/3 (看更多)
剛剛編輯文章按到復原草稿 插入很多不必要東西 但用Pitt沒辦法編輯 所以刪除重po不好意思 以下代之前社團認識的學妹代po詢問 我是今年畢業的新鮮人 今天面試白板考的時候考了跟差集有關的問題 關於時間複雜度的部分怎麼想都想不通 已經查過資料也跟要考資工所的朋友、資工系的朋友討論過 仍然不確定答案，想請版上大神開示一下：D 題目：有A、B兩個未經排序的array A有n個整數，B有m個整數 寫一個function回傳在A且不在B的整數。 (皆先不討論A、B內各自有重複元素的情況) 我的做法： 1.先把B的每個元素放進dictionary 2.然後用for檢查A的每個元素是否為dictionary的key，不是的話就加入ans的list 3.回傳ans 想以python的dictionary來討論這題的時間複雜度 用B建立長度為m的dictionary 新增一組key-value時間複雜度是O(1)；A的長度為n 查找是否在dictionary的key時的時間複雜度是O(1) 我覺得時間複雜度是O(m+n)。 參考leetcode簡中板的類似題目的官方詳解(只有簡中版討論區有官方詳解) https://reurl.cc/KAaRmy leetcode這題基本一樣 是找出在A且在B的整數 官方是用set來實作 時間複雜度是O(m+n) 想請問dictionary和set()底層的hash原理會是造成時間複雜度不同的關鍵嗎？ Python程式碼如下 def solution(A:List[int], B:List[int]): ans = [] dic = dict() for b in B: dic[b] = b for a in A: if a not in dic: ans.append(a) return ans 另外，我知道hash在python以外的語言像是C/C++ 若是基於紅黑樹來實做的話 時間複雜度會是O(nlogm)。 我想問的是python的時間複雜度！ 補充 想知道答案是因為 面試官說我的答案O(m+n)一定不對 他很肯定說這樣做答案絕對不是線性的 想請問這樣計算時間複雜度到底哪裡有問題 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.24.250.114 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1629135646.A.93D.html
推
08/17 02:01, 2年前 , 1F
O(m+n)是對的吧
08/17 02:01, 1F
→
08/17 02:09, 2年前 , 2F
兩個loop分開怎麼不會是線型的，不解+1
08/17 02:09, 2F
→
08/17 02:54, 2年前 , 3F
不專業回答：HashMap廣義來說都是O(1)碰撞之後才會用
08/17 02:54, 3F
→
08/17 02:54, 2年前 , 4F
紅黑樹實踐排列碰撞的元素 當Hash array足夠大時紅黑
08/17 02:54, 4F
→
08/17 02:54, 2年前 , 5F
樹的成本可以不計 廣義是這樣 若有錯請高手指點迷津
08/17 02:54, 5F
→
08/17 02:54, 2年前 , 6F
不過你po的程式碼O(m+n)完全沒毛病 不知面試官的思
08/17 02:54, 6F
→
08/17 02:54, 2年前 , 7F
路是怎樣為何會覺得不是
08/17 02:54, 7F
推
08/17 04:28, 2年前 , 8F
你應該當場反問哪裡不對的，搞不好是面試官自己根本不懂
08/17 04:28, 8F
→
08/17 06:41, 2年前 , 9F
面試官搞錯的機率很大 也有可能你們的溝通有一些誤會
08/17 06:41, 9F
→
08/17 06:41, 2年前 , 10F
move on就可以了
08/17 06:41, 10F
推
08/17 06:55, 2年前 , 11F
面試官大概把TreeMap and HashMap搞錯了吧
08/17 06:55, 11F
推
08/17 07:05, 2年前 , 12F
c++ 的 std::set 不是 hash map ，std::unorderd_map
08/17 07:05, 12F
→
08/17 07:05, 2年前 , 13F
才是噢。不過前面 O(m+n) 看起來沒什麼問題。
08/17 07:05, 13F
→
08/17 07:06, 2年前 , 14F
啊是 std::map 不是 std::set
08/17 07:06, 14F
推
08/17 08:13, 2年前 , 15F
O(m+n) 一票
08/17 08:13, 15F
推
08/17 08:31, 2年前 , 16F
再一票O(m+n)
08/17 08:31, 16F
推
08/17 08:39, 2年前 , 17F
c++ 的map （TreeMap)vs unordered map(HashMap)前
08/17 08:39, 17F
→
08/17 08:39, 2年前 , 18F
者強調有序所以會用RBTree就會多了log複雜度，後者大
08/17 08:39, 18F
→
08/17 08:39, 2年前 , 19F
Hash 表查詢O(1) 但有碰撞好像另當別論，不過機率低
08/17 08:39, 19F
→
08/17 08:39, 2年前 , 20F
，Amortized 應該仍是O(1)，有誤歡迎指正
08/17 08:39, 20F
→
08/17 08:39, 2年前 , 21F
O(m+n)吧 但如果面試官說錯的話 我會問他是因為hash coll
08/17 08:39, 21F
→
08/17 08:39, 2年前 , 22F
ision嗎
08/17 08:39, 22F
推
08/17 09:00, 2年前 , 23F
不是線性的話就是nlogn了吧 面試官一定想到紅黑樹了
08/17 09:00, 23F
→
08/17 09:18, 2年前 , 24F
面試官搞錯了
08/17 09:18, 24F
推
08/17 09:40, 2年前 , 25F
unordered map發生嚴重碰撞的話 搜尋的worst case 是 O(
08/17 09:40, 25F
→
08/17 09:40, 2年前 , 26F
m)
08/17 09:40, 26F
→
08/17 09:41, 2年前 , 27F
average case才是O(1)
08/17 09:41, 27F
推
08/17 11:06, 2年前 , 28F
面試官沒解釋自己的思路 感覺有點雷R
08/17 11:06, 28F
推
08/17 11:28, 2年前 , 29F
O(m+n) +1
08/17 11:28, 29F
推
08/17 13:09, 2年前 , 30F
這面試官不太行啊 不過建議你可以問下數據大小 如果
08/17 13:09, 30F
→
08/17 13:09, 2年前 , 31F
面試官說數據量很大 那你可以說有碰撞問題 如果不是
08/17 13:09, 31F
→
08/17 13:09, 2年前 , 32F
那你可以選別家公司了
08/17 13:09, 32F
推
08/17 18:19, 2年前 , 33F
這間面試官程度太差了
08/17 18:19, 33F
推
08/17 18:39, 2年前 , 34F
南港面過做手機的公司 主管也是堅持hash search not
08/17 18:39, 34F
→
08/17 18:39, 2年前 , 35F
O(1)
08/17 18:39, 35F
推
08/17 21:22, 2年前 , 36F
面試官只是希望你說一下worst case而已吧 我感覺面試
08/17 21:22, 36F
→
08/17 21:22, 2年前 , 37F
的時候被要求分別提一下worst case跟average case的
08/17 21:22, 37F
→
08/17 21:22, 2年前 , 38F
情況還蠻常見的啊
08/17 21:22, 38F
推
08/17 21:58, 2年前 , 39F
O(n+m) +1，除非每一個插進HashSet的元素都雜湊碰撞
08/17 21:58, 39F
→
08/17 21:58, 2年前 , 40F
才會讓複雜度變成O(n*m)
08/17 21:58, 40F
→
08/17 21:59, 2年前 , 41F
那面試官的主觀意識感覺過強+不善溝通，雷雷的不去也罷
08/17 21:59, 41F
→
08/17 22:49, 2年前 , 42F
也有可能是問worse case 或者現場的程式碼不一樣
08/17 22:49, 42F
推
08/18 01:04, 2年前 , 43F
已經在討論時間複雜度了，應該都是用最基本的資料結構，
08/18 01:04, 43F
→
08/18 01:04, 2年前 , 44F
先入為主用unordered map來算，其實也有問題，一定是雙方
08/18 01:04, 44F
→
08/18 01:04, 2年前 , 45F
沒溝通清楚
08/18 01:04, 45F
→
08/18 07:20, 2年前 , 46F
我覺得說人錯，到最後都沒給提示算是面試官問題
08/18 07:20, 46F
推
08/18 09:30, 2年前 , 47F
我看過幾本中國的面試刷題書 分析hash table的time
08/18 09:30, 47F
→
08/18 09:30, 2年前 , 48F
complexity都會要求面試者要特別提一下運氣極差所有
08/18 09:30, 48F
→
08/18 09:31, 2年前 , 49F
key都collision的情況跟一般情況 我猜那個主管大概也
08/18 09:31, 49F
→
08/18 09:32, 2年前 , 50F
是看過類似的書 所以預設你應該要回答..
08/18 09:32, 50F
推
08/19 13:41, 2年前 , 51F
溝通不良吧 如果如原PO所言 面試官責任較大
08/19 13:41, 51F
推
08/19 13:44, 2年前 , 52F
08/19 13:44, 52F
推
08/19 22:03, 2年前 , 53F
你的實作就是線性...
08/19 22:03, 53F
→
08/19 22:04, 2年前 , 54F
面試官也是人 面試官搞錯的可能性也是有的
08/19 22:04, 54F
→
08/20 23:30, 2年前 , 55F
其實討論Big O我覺得就是在講worst case了
08/20 23:30, 55F
→
08/20 23:32, 2年前 , 56F
我倒覺得科班出身念過演算法的會答linear time很奇怪...
08/20 23:32, 56F
推
08/21 19:33, 2年前 , 57F
c++ 的 unordered_set 預設的 hash function 很容易造
08/21 19:33, 57F
→
08/21 19:33, 2年前 , 58F
出讓他全部 collision 的狀況，所以要更乾淨還得自製
08/21 19:33, 58F
→
08/21 19:33, 2年前 , 59F
亂數更均勻的 hash function，但感覺上不是在考這個...
08/21 19:33, 59F
→
08/21 19:34, 2年前 , 60F
不過真遇到這種面試官自己搞不清楚狀況的時候，就是把
08/21 19:34, 60F
→
08/21 19:35, 2年前 , 61F
你所有知道的底層知識都搬出來跟他討論一遍就對了，看
08/21 19:35, 61F
→
08/21 19:35, 2年前 , 62F
是他會突然發現自己搞錯，或是你突然打中他某個神祕的
08/21 19:35, 62F
→
08/21 19:35, 2年前 , 63F
想聽得關鍵點，你就會過了
08/21 19:35, 63F
推
08/23 10:21, 2年前 , 64F
M+n哪裡不對 又不是nested loop 面試官不要不懂裝懂
08/23 10:21, 64F
→
08/23 10:21, 2年前 , 65F
欸
08/23 10:21, 65F
→
08/23 22:59, 2年前 , 66F
我只能說algorithm課本是好東西，可以多念一下
08/23 22:59, 66F
→
08/23 22:59, 2年前 , 67F
要討論實作這樣寫沒什麼問題
08/23 22:59, 67F
→
08/23 23:00, 2年前 , 68F
但是如果是要討論time complexity回linear真的比較外行
08/23 23:00, 68F
→
08/23 23:01, 2年前 , 69F
去查一下大O小o還有omega
08/23 23:01, 69F
→
08/23 23:02, 2年前 , 70F
big O就是在討論worst case
08/23 23:02, 70F
→
08/23 23:03, 2年前 , 71F
建立一組O(1)? 查詢O(1)? 不懂不要裝懂
08/23 23:03, 71F
推
08/24 07:52, 2年前 , 72F
照樓上的說法 一堆排序例如quicksort應該是O(n^2)
08/24 07:52, 72F
‣ 更多 cccict 的文章
文章代碼(AID): #1X6gCUaz (Soft_Job)
‣ 更多 cccict 的文章
文章代碼(AID): #1X6gCUaz (Soft_Job)