作者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