[請益] 面試白板考題目的時間複雜度
剛剛編輯文章按到復原草稿
插入很多不必要東西
但用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)一定不對
他很肯定說這樣做答案絕對不是線性的
想請問這樣計算時間複雜度到底哪裡有問題
謝謝
--
O(m+n)是對的吧
兩個loop分開怎麼不會是線型的，不解+1
不專業回答：HashMap廣義來說都是O(1)碰撞之後才會用
紅黑樹實踐排列碰撞的元素 當Hash array足夠大時紅黑
樹的成本可以不計 廣義是這樣 若有錯請高手指點迷津
不過你po的程式碼O(m+n)完全沒毛病 不知面試官的思
路是怎樣為何會覺得不是
你應該當場反問哪裡不對的，搞不好是面試官自己根本不懂
面試官搞錯的機率很大 也有可能你們的溝通有一些誤會
move on就可以了
面試官大概把TreeMap and HashMap搞錯了吧
c++ 的 std::set 不是 hash map ，std::unorderd_map
才是噢。不過前面 O(m+n) 看起來沒什麼問題。
啊是 std::map 不是 std::set
O(m+n) 一票
再一票O(m+n)
c++ 的map （TreeMap)vs unordered map(HashMap)前
者強調有序所以會用RBTree就會多了log複雜度，後者大
Hash 表查詢O(1) 但有碰撞好像另當別論，不過機率低
，Amortized 應該仍是O(1)，有誤歡迎指正
O(m+n)吧 但如果面試官說錯的話 我會問他是因為hash coll
ision嗎
不是線性的話就是nlogn了吧 面試官一定想到紅黑樹了
面試官搞錯了
unordered map發生嚴重碰撞的話 搜尋的worst case 是 O(
m)
average case才是O(1)
面試官沒解釋自己的思路 感覺有點雷R
O(m+n) +1
這面試官不太行啊 不過建議你可以問下數據大小 如果
面試官說數據量很大 那你可以說有碰撞問題 如果不是
那你可以選別家公司了
這間面試官程度太差了
南港面過做手機的公司 主管也是堅持hash search not
O(1)
面試官只是希望你說一下worst case而已吧 我感覺面試
的時候被要求分別提一下worst case跟average case的
情況還蠻常見的啊
O(n+m) +1，除非每一個插進HashSet的元素都雜湊碰撞
才會讓複雜度變成O(n*m)
那面試官的主觀意識感覺過強+不善溝通，雷雷的不去也罷
也有可能是問worse case 或者現場的程式碼不一樣
已經在討論時間複雜度了，應該都是用最基本的資料結構，
先入為主用unordered map來算，其實也有問題，一定是雙方
沒溝通清楚
我覺得說人錯，到最後都沒給提示算是面試官問題
我看過幾本中國的面試刷題書 分析hash table的time
complexity都會要求面試者要特別提一下運氣極差所有
key都collision的情況跟一般情況 我猜那個主管大概也
是看過類似的書 所以預設你應該要回答..
溝通不良吧 如果如原PO所言 面試官責任較大
你的實作就是線性...
面試官也是人 面試官搞錯的可能性也是有的
其實討論Big O我覺得就是在講worst case了
我倒覺得科班出身念過演算法的會答linear time很奇怪...
c++ 的 unordered_set 預設的 hash function 很容易造
出讓他全部 collision 的狀況，所以要更乾淨還得自製
亂數更均勻的 hash function，但感覺上不是在考這個...
不過真遇到這種面試官自己搞不清楚狀況的時候，就是把
你所有知道的底層知識都搬出來跟他討論一遍就對了，看
是他會突然發現自己搞錯，或是你突然打中他某個神祕的
想聽得關鍵點，你就會過了
M+n哪裡不對 又不是nested loop 面試官不要不懂裝懂
欸
我只能說algorithm課本是好東西，可以多念一下
要討論實作這樣寫沒什麼問題
但是如果是要討論time complexity回linear真的比較外行
去查一下大O小o還有omega
big O就是在討論worst case
建立一組O(1)? 查詢O(1)? 不懂不要裝懂
照樓上的說法 一堆排序例如quicksort應該是O(n^2)
回頭看到這篇 rems是真的很外行 worst case跟big-O沒什
關係 big-O也可以用在best case和avg case
爆
[心得] Google TW SWE 面試心得（下）（文長警告） 上一篇提到 2019 年底聯繫上 HR 開始全職刷題六個月， 到了 2020 年中面試完收到拒絕信，灰心了好一陣子。 但也沒辦法，還是只能乖乖回去公司上班。 這次回公司上班其實也獲得一個不錯的契機，98
[請益] (ByteDance 面試) 兩種不同寫法的複雜度分析事情是這樣的，今天下午面了 ByteDance 2023 的缺 (Algorithm Engineer) 考了 leetcode 3. Longest Substring Without Repeating Characters () 我的解法：![[請益] (ByteDance 面試) 兩種不同寫法的複雜度分析](https://i.imgur.com/o5wrRMob.png "[請益] (ByteDance 面試) 兩種不同寫法的複雜度分析")
79
[面試] 2020新鮮人面試(MixerBox/Nvidia/AWS/Sho自我介紹: 四大學碩 這篇文章大概分享我今年2月多到現在面試的結果跟心得 但有幾間公司還在等結果 因為疫情影響都沒什麼面試機會 原本想試看看新思的研替 結果連面試機會都沒有30
Re: [問卦] leetcode medium看完答案還是寫不出來看什麼題目吧 一些討論區的最佳解 簡化到失去可讀性 也失去題目的思維 要不看人題解 要不就是自己認真從頭到尾寫出來 對刷leetcode比較有用 依照本巨巨在矽谷面試別人的經驗 我準備的題目都是 馬上可以寫出暴力解 然後暴力解逐步優化 我個人最愛的就是01背包問題 因為暴力解超簡單 就一個東西只能放一次27
Re: [討論] 我就問，刷題強者的實務表現?我親身經驗，刷題非常有用 347 top k frequent elements 23 merge k sorted lists 56 merge intervals 一些基本的工具如 recursion , tree , map , deque ，比較稍微難的像line sweep , biwise21
Re: [請益] (ByteDance 面試) 兩種不同寫法的複這不是一個 code reviewer 該有的心態 如果你在意這段程式碼，把它看懂是你的責任 如果你有建議你可以跟原作者說，你可以要求他改或封裝 如果你不在意的話，那你幹嘛管它的複雜度 : 程式要寫的讓人看得懂X
Re: [請益] (ByteDance 面試) 兩種不同寫法的複雜度分析這題應該是用dict，而不是set。用dict來紀錄字元的位置，這樣就不用while來重找。 面試官對你很好，提示你不要用while，讓你想其它方法，可惜你卡在n2，2n的問題上。 --5
Re: [問卦] 程式能寫if 就不要用for loop？你會算複雜度嗎 以你的例子 10, 20, 30 N=3 M=30 用loop是O(M) 用if是O(N) 不過都不是最佳解
Re: [難過] 國考十幾年的朋友...主要是這種東西如果不太理解原理，也不是很好背 就算給你背起來一題，如果你不了解為什麼要這樣做， 出了變化題，你也是bye 而且考這個，通常也不是code寫完就好... 面試可能還要你解釋你為什麼要這樣做? 時間複雜度空間複雜度是什麼?