Re: [問題] 貌似Facebook面試題目

[saladim (殺拉頂)]

※ 引述《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
→ chunhsiang:a<b<c 這假設怪怪的
→ chunhsiang:a=-1 d=0 c=3 b=4
→ saladim:基本上好像沒考慮到有負數的狀況 ORZ
→ saladim:不過 sorted過後  a b c的內容似乎會滿足 a < b < c??
→ saladim:呵呵 我好像錯了 不過帶入虛擬碼又好像不會出問題...混亂.
→ saladim:偶再想想好了....
→ saladim:感謝!!
推 sandy4444:原文的 N 好像是 billion
推 WaiTingKuo:assume a+b=c
→ WaiTingKuo:for c = 0~n-1
→ WaiTingKuo:for (int a=0, b=N-1, xxx, a++, b--)
推 WaiTingKuo:好像搞錯了... 固定a
→ WaiTingKuo:if arr[c] - arr[b] > arr[a] then b++
→ WaiTingKuo:if arr[a] < arr[c] - arr[b] then c++
→ WaiTingKuo:if arr[c] - arr[b] == arr[a] then output a, b, c