CS面試問題(entry level)分享 - 面試

※ 引述《nukchichi (haha)》之銘言：
: 大家好,
: 今天phone interview某間大公司的小 entry level Software developer.
: 考到一個問題...想分享出來且尋求答案.
: ==
: 給數字 5, 5, 7, 12, 3, 5
: 如何找出並印出裡面是兩個和 sum = 10的數字組(pair)
: 他給的printpair 的 output是 55 55 73 55 (但是我後來想 應該有少給我37...)
: ==
: 我一開始沒有想法 但是時間壓力 就直接先給他直觀的做法
: 兩個for loop 檢查,
: 第一次迴圈 用10-5 = 5 去找數組裡其他的5 找到就印出
: 2nd 10 - 5 = 5 去找其他的5
: 3nd 10 - 7 = 3 去找其他的3
: ...
: 這樣他說可以, 但是希望能更好. 我想了想 想不太出來請他能提示
: 他說: 想想為何我剛剛問你比較 link list, binary tree, 和hash table.
: 我直覺是要用hashtable去找(他好像也認同我用hashtable)
: 但是他要我把hashtable的樣子跟他講 exactly 一點~
: 我就答不出來了...然後就byebye了...
: ==
: 煩請版友幫忙我這新手解答疑惑...
: 感謝!!

入門經典考題之一, 雖然我不是很確定為什麼 37 和 73 算兩對?

你的解法算是 naive solution, 用 O(N^2) 通常都不會過.

比較好一點的解法是先排序, 排完的數字為 3 5 5 5 7 12,
然後用兩個指標, 分別指向最大和最小的數字
然後重複一個迴圈, 直到大小指標重疊
如果大小指標相加小於 10, 就把小指標向右移
如果大小指標相加大於 10, 就把大指標向左移
如果大小指標相加等於 10, 就把相同的數字組合都印出來, 然後大小指標分別向內移

以上解法的瓶頸在排序, 一般比較排序, 就算是最好的 quicksort 也只有 O(NlogN)
後面迴圈的部份是 O(N)

更好的解法是改用計數排序, 可以把排序那一段加快到 O(N), 基本上就是把數字倒進
hashtable, 數字本身是 key, 重複次數為 value. 最後再掃一次倒出來.

所以總結, counting sort + loop with two pointers, 時間複雜度為 O(N).

--