作者saladim (杀拉顶)
看板Prob_Solve
标题Re: [问题] 貌似Facebook面试题目
时间Sat Mar 17 19:38:30 2012
※ 引述《saladim (杀拉顶)》之铭言：
: 有人跟我说这是一提FB的面试题目, 想了一下想不太出合适的解法, 题目如下:
: 给一个sorted array, 找出array里面有没有某两个元素加起来等於另外一个元素,
: 有的话请列印出来, 没有的话请回答没有.
: 尝试利用 sorted元素大小关系跟binary search去做, 但是想不出来阿!!!!
: 请各位大大提供一下意见.....感激不尽.....
刚回来 看到推文 先来简短回应一下 ORZ , 自己当然有一些想法 叙述如下:
根据原来的题目 可以得到以下讯息(假设元素不重复):
假设 a, b, c为所求(a,b,c都是阵列内的元素), 则
1. a+b=c,
2. a<b<c,
3. 0 <= i < j < k <= MAX_NUM, 其中i j k为 a b c的索引值.
虚拟码:
for i = 0 to MAX-2
{
for j = i+1 to MAX-1
{
ans = binary_search( a[i]+a[j] );
if 0 <= ans && ans < MAX_NUM
printf i,j ans
}
}
这样可以印出满足 a+b=c 的所有pair. 我想这个时间复杂度是 O(N^2 * logN) (对吧??)
但是呢 看到 N^2就有点不舒服 然後又说是FB的面试题 所以根据小弟的崇洋媚外心理
觉得应该会有 N*logN 或是 logN*logN之类的方法 只是我想不到而已 XD
以上!!!
那我先去研究一下3SUM problem......欢迎大家来讨论讨论~~~~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.43.203.126
1F：→ chunhsiang:a<b<c 这假设怪怪的 03/17 21:24
2F：→ chunhsiang:a=-1 d=0 c=3 b=4 03/17 21:29
3F：→ saladim:基本上好像没考虑到有负数的状况 ORZ 03/17 22:07
4F：→ saladim:不过 sorted过後 a b c的内容似乎会满足 a < b < c?? 03/17 22:07
5F：→ saladim:呵呵 我好像错了 不过带入虚拟码又好像不会出问题...混乱. 03/17 22:11
6F：→ saladim:偶再想想好了.... 03/17 22:12
7F：→ saladim:感谢!! 03/17 22:17
8F：推 sandy4444:原文的 N 好像是 billion 03/18 02:47
9F：推 WaiTingKuo:assume a+b=c 03/18 03:27
10F：→ WaiTingKuo:for c = 0~n-1 03/18 03:27
11F：→ WaiTingKuo:for (int a=0, b=N-1, xxx, a++, b--) 03/18 03:28
12F：推 WaiTingKuo:好像搞错了... 固定a 03/18 03:49
13F：→ WaiTingKuo:if arr[c] - arr[b] > arr[a] then b++ 03/18 03:50
14F：→ WaiTingKuo:if arr[a] < arr[c] - arr[b] then c++ 03/18 03:50
15F：→ WaiTingKuo:if arr[c] - arr[b] == arr[a] then output a, b, c 03/18 03:51