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

這題就是回答O(m+n)

面試官硬說不是線性 大概有以下幾種可能

1. 面試官搞錯order map跟unordered map了

2. 面試官想追問worst case的話 hash table的search複雜度就不是O(1)

這樣你的答案就不是O(m+n)

1的情形是面試官顆顆

2的情形可能是溝通誤會

可能是面試官沒有明確說 what if collision happens very frequently?

也可能是你朋友沒有理解面試官其實想問collision之後的chaining的結果

不過既然你朋友知道紅黑樹這東西

沒道理不知道紅黑樹是為了解決hash的collision問題

所以我猜是面試官自己搞錯了

但是不管1或2 都是move on就好 不用糾結在實作上的特性

你就想想 如果你遇到這種同事 你會想跟他一起工作嗎?

※ 引述《cccict (馬路柏油)》之銘言：
: 剛剛編輯文章按到復原草稿
: 插入很多不必要東西
: 但用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)一定不對
: 他很肯定說這樣做答案絕對不是線性的
: 想請問這樣計算時間複雜度到底哪裡有問題
: 謝謝

--