為什麼這篇面試 白板題 PTT鄉民發文收入到精華區：因為在面試 白板題 PTT這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者cccict (馬路柏油)看板Soft_Job標題[請益] 面試白板考題目的時間複雜度時間Tue...
面試 白板題 PTT 在 包定居美國中(๑•̀ㅂ•́)و? Instagram 的最佳解答
2021-09-16 09:24:53
《上學日常🏫》 講一些上學的小故事好了(ﾟ∀。)然後我們都是全英上課啦（畢竟我在美國???）我聽的時候都懂，但回想都會忘記原話，所以我都自己翻成中文（大家也比較好看懂ʕ´• ᴥ•̥`ʔ）請不要再私訊問我教授是不是都講中文惹...ಥ_ಥ 一、 我和我同學去找上學期的英文教授聊天（上學期在台灣上網...
剛剛編輯文章按到復原草稿
插入很多不必要東西
但用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
推 mimi9126: O(m+n)是對的吧 08/17 02:01
→ sjensen: 兩個loop分開怎麼不會是線型的，不解+1 08/17 02:09
→ charle0911: 不專業回答：HashMap廣義來說都是O(1)碰撞之後才會用 08/17 02:54
→ charle0911: 紅黑樹實踐排列碰撞的元素 當Hash array足夠大時紅黑 08/17 02:54
→ charle0911: 樹的成本可以不計 廣義是這樣 若有錯請高手指點迷津 08/17 02:54
→ charle0911: 不過你po的程式碼O(m+n)完全沒毛病 不知面試官的思 08/17 02:54
→ charle0911: 路是怎樣為何會覺得不是 08/17 02:54
推 sorryla: 你應該當場反問哪裡不對的，搞不好是面試官自己根本不懂 08/17 04:28
→ wawi2: 面試官搞錯的機率很大 也有可能你們的溝通有一些誤會 08/17 06:41
→ wawi2: move on就可以了 08/17 06:41
推 shiauji: 面試官大概把TreeMap and HashMap搞錯了吧 08/17 06:55
推 NciscalA: c++ 的 std::set 不是 hash map ，std::unorderd_map 08/17 07:05
→ NciscalA: 才是噢。不過前面 O(m+n) 看起來沒什麼問題。 08/17 07:05
→ NciscalA: 啊是 std::map 不是 std::set 08/17 07:06
推 WaterLengend: O(m+n) 一票 08/17 08:13
推 aspwell520: 再一票O(m+n) 08/17 08:31
推 Amazonite96: c++ 的map （TreeMap)vs unordered map(HashMap)前 08/17 08:39
→ Amazonite96: 者強調有序所以會用RBTree就會多了log複雜度，後者大 08/17 08:39
→ Amazonite96: Hash 表查詢O(1) 但有碰撞好像另當別論，不過機率低 08/17 08:39
→ Amazonite96: ，Amortized 應該仍是O(1)，有誤歡迎指正 08/17 08:39
→ aa06697: O(m+n)吧 但如果面試官說錯的話 我會問他是因為hash coll 08/17 08:39
→ aa06697: ision嗎 08/17 08:39
推 sooge: 不是線性的話就是nlogn了吧 面試官一定想到紅黑樹了 08/17 09:00
→ yyc1217: 面試官搞錯了 08/17 09:18
推 eigen555: unordered map發生嚴重碰撞的話 搜尋的worst case 是 O( 08/17 09:40
→ eigen555: m) 08/17 09:40
→ eigen555: average case才是O(1) 08/17 09:41
推 DarkIllusion: 面試官沒解釋自己的思路 感覺有點雷R 08/17 11:06
推 zenithyoung: O(m+n) +1 08/17 11:28
推 jass970991: 這面試官不太行啊 不過建議你可以問下數據大小 如果 08/17 13:09
→ jass970991: 面試官說數據量很大 那你可以說有碰撞問題 如果不是 08/17 13:09
→ jass970991: 那你可以選別家公司了 08/17 13:09
推 pttano: 這間面試官程度太差了 08/17 18:19
推 TheOneisNEO: 南港面過做手機的公司 主管也是堅持hash search not 08/17 18:39
→ TheOneisNEO: O(1) 08/17 18:39
推 Parazicecum: 面試官只是希望你說一下worst case而已吧 我感覺面試 08/17 21:22
→ Parazicecum: 的時候被要求分別提一下worst case跟average case的 08/17 21:22
→ Parazicecum: 情況還蠻常見的啊 08/17 21:22
推 MyNion: O(n+m) +1，除非每一個插進HashSet的元素都雜湊碰撞 08/17 21:58
→ MyNion: 才會讓複雜度變成O(n*m) 08/17 21:58
→ MyNion: 那面試官的主觀意識感覺過強+不善溝通，雷雷的不去也罷 08/17 21:59
→ cha122977: 也有可能是問worse case 或者現場的程式碼不一樣 08/17 22:49
推 jolyoy: 已經在討論時間複雜度了，應該都是用最基本的資料結構， 08/18 01:04
→ jolyoy: 先入為主用unordered map來算，其實也有問題，一定是雙方 08/18 01:04
→ jolyoy: 沒溝通清楚 08/18 01:04
→ wulouise: 我覺得說人錯，到最後都沒給提示算是面試官問題 08/18 07:20
推 Parazicecum: 我看過幾本中國的面試刷題書 分析hash table的time 08/18 09:30
→ Parazicecum: complexity都會要求面試者要特別提一下運氣極差所有 08/18 09:30
→ Parazicecum: key都collision的情況跟一般情況 我猜那個主管大概也 08/18 09:31
→ Parazicecum: 是看過類似的書 所以預設你應該要回答.. 08/18 09:32
推 s0914714: 溝通不良吧 如果如原PO所言 面試官責任較大 08/19 13:41
推 jlhc: 你的實作就是線性... 08/19 22:03
→ jlhc: 面試官也是人 面試官搞錯的可能性也是有的 08/19 22:04
→ rems: 其實討論Big O我覺得就是在講worst case了 08/20 23:30
→ rems: 我倒覺得科班出身念過演算法的會答linear time很奇怪... 08/20 23:32
推 BBSealion: c++ 的 unordered_set 預設的 hash function 很容易造 08/21 19:33
→ BBSealion: 出讓他全部 collision 的狀況，所以要更乾淨還得自製 08/21 19:33
→ BBSealion: 亂數更均勻的 hash function，但感覺上不是在考這個... 08/21 19:33
→ BBSealion: 不過真遇到這種面試官自己搞不清楚狀況的時候，就是把 08/21 19:34
→ BBSealion: 你所有知道的底層知識都搬出來跟他討論一遍就對了，看 08/21 19:35
→ BBSealion: 是他會突然發現自己搞錯，或是你突然打中他某個神祕的 08/21 19:35
→ BBSealion: 想聽得關鍵點，你就會過了 08/21 19:35
推 imjeffreylee: M+n哪裡不對 又不是nested loop 面試官不要不懂裝懂 08/23 10:21
→ imjeffreylee: 欸 08/23 10:21
→ rems: 我只能說algorithm課本是好東西，可以多念一下 08/23 22:59
→ rems: 要討論實作這樣寫沒什麼問題 08/23 22:59
→ rems: 但是如果是要討論time complexity回linear真的比較外行 08/23 23:00
→ rems: 去查一下大O小o還有omega 08/23 23:01
→ rems: big O就是在討論worst case 08/23 23:02
→ rems: 建立一組O(1)? 查詢O(1)? 不懂不要裝懂 08/23 23:03
推 s0914714: 照樓上的說法 一堆排序例如quicksort應該是O(n^2) 08/24 07:52
→ peter98: 回頭看到這篇 rems是真的很外行 worst case跟big-O沒什 12/03 04:48
→ peter98: 關係 big-O也可以用在best case和avg case 12/03 04:49