作者leeym (leeym)
看板Oversea_Job
标题Re: [北美] CS面试问题(entry level)分享
时间Sat Jul 30 13:34:42 2011
※ 引述《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).
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 209.131.62.115
1F：推 ccchen:这个方法，印不出3 对 55 喔 07/30 14:01
2F：→ leeym:可以, 用 C(n,k) 可以算出要重复几次. 07/30 15:25
※ 编辑: leeym 来自: 209.131.62.115 (07/30 15:31)
3F：推 nukchichi:非常感谢你!(不过他说印出的顺序是固定那顺序的...) 07/30 16:45
4F：→ nukchichi:(所以感觉这方法会先印出37 or 73?) 07/30 16:46
5F：→ leeym:会印出 37 55 55 55, 如果顺序要固定, 可能得看 Solti 的. 07/30 22:35
6F：推 Solti:如果有要求顺序 我的也办不到 得多加一个array 最後再一次 07/30 23:19
7F：→ Solti:全部print出来, memory会变成O(N+K) 07/30 23:19
8F：推 Baudelaire:强者未看先拜... 08/12 02:21