數個舊金山軟體公司面試經驗 - 面試

如果行得通的話你已經證明 P = NP... :p

這題是 subset sum problem 的變形, 要找到 polynomial-time reduction 並不難.
http://en.wikipedia.org/wiki/Subset_sum_problem
想法是這樣:
輸入為 {x_1, ..., x_n}, 取一補正值 K > n*max(|x_i|),
假設存在一組解 {y_1, ..., y_m} 共 m 個數,
對於 m <= 2 的情形直接窮舉就可以了,
對於 m > 2 的情形可產生下列資料作為變化版問題的輸入:

{-x_1 + (m-1)*K, x_2+K, x_3+K, ..., x_n+K}
{x_1+K, -x_2 + (m-1)*K, x_3+K, ..., x_n+K}
...
{x_1+K, x_2+K, x_3+K, ..., -x_n + (m-1)*K}

這 n 組資料中若任何一組有解, 其解必為以 -x_a + (m-1)*K 帶頭的 m 個數,
(證明略, 基本上是利用 K 很大, 就算全部 x_i 加起來都沒辦法抵過一個 K 的差.
一個特例是當存在 x_i = x_j 的情形, 這比較難搞,
在此假定 x_1 ... x_n 不重複, 但是重複的情形還是證明得出來)
也就是說 -x_a + (m-1)*K = x_b+K + x_c+K + x_d+K + ...
等式兩邊移一下可以找到 x_a + x_b + x_c + x_d + ... = 0
作為原 subset sum problem 的答案.

只要對於所有可能的 m 試過一遍, 這樣就解了 subset sum problem.
故得證該面試問題為 NP-hard.

話是如此啦, 但我猜原本面試想考的應該是 pseudo-polynomial time 的解法,
當值域不大的時候你可以在值域內用 dynamic programming 來解.
http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution

評: 這題大約是高中競賽的難度, 理論證明要等到碩一上完計算複雜度理論.
(總之是基本工啦)

※ 引述《eshai (暖暖的 ^^)》之銘言：
: 前後文恕刪，剛好在這網站看到有點類似的題目跟解題想法，給有興趣的版友參考一下:
: 先把集合理面的數字 sorting, 然後在往較小的 subset 裡面做測試
: 我覺得概念上來講是行得通的
: (還是很麻煩，但是答起來聽起來就比較 oraginized)
: : Find a subset in a array that the biggest number is sum of rest of the subset
: : ex:
: : {3, 4, 9, 14, 15, 19, ...}
: : {4, 15, 19} 就是19=4+15，是合格的subset
: : 這題最難的是他的數字有二十幾個，光是要計算power set就讓人很頭大
: : 複雜度是2^n，把我的記憶體全部用光光orz
: http://www.careercup.com/question?id=14366691
: Q: there are list of random numbers like 1,3,23,76,908,34,256,12,43,11,2,-10
: given an input suppose:13
: find the combination of the numbers which adds up to 13.
: like 1+12=13,23+(-10)=13..like that
: A: It can be done as follows.
: 1. Sort the list in ascending order (takes O(nlgn))
: 2. Read the list from begining
: 3. For each element read search (13 - element read) value from the list.
: Seaching in list takes lgn and in worst case the time complexity
: will be O(nlgn)

--
「ふ…ふざけるな！そんあ短い咒文で、魔法を起動できるわけないだろうが！
お前わマウゼルの神に逆らう氣なのか？！傲慢な～」

「失禮致しました、誠實に全力でお相手致します。
第一戰術級‧軍用攻性魔法‧出よ、武雷神〈トール〉！」
〈スクラップド‧プリンセス〉

--