如何評價《職人介紹所》第 21 期節目，以及嘉賓 趙劼 和 winter 的表現？
徒手寫代碼 + 分析完整版視頻：《職人介紹所》第 21 期：你們要的 winter 趙劼徒手寫碼到分析代碼完整版【節目中提到的編程題】：有一個數組，從中挑ABC三個整數，讓ABC三個整數加起來等於0，看有多少個這樣的數組？（3Sum | LeetCode OJ）
職人介紹所第21期：年薪不過百萬就不是好程序員？視頻
單純說題，這題如果放ACM Regional賽場上，基本上妥妥的是個簽到題，屬於一場比賽一百來個隊伍每一支都能過並且開場5分鐘上下就會被過掉的題目，因此真不是什麼難題。
思維方式的問題：如果問題能夠轉化為2-sum，在一個有序數組裡找所有的兩個數對，使其和為指定q，這大概各位誰都能想到排序後兩端掃一遍，跳過重複數對辦法，O(n)的下界也非常明確地達到了，更快的方法也不會比這快。問題里是三個數，那麼枚舉一個數就能夠變為2-sum了，保證枚舉的數不重複，由於後兩數不重複，那麼總的三個數也不會重複，問題解決。時間O(n^2)，唯一疑問是有沒有更快的辦法：更快的方法無非是空間換時間，然而問題狀態空間自身就是O(n^2)的，再怎麼優化也做不到規模下降了。
坦白說，正經學過CS，學過些個基本的演算法課程並且不笨的都能做出來，只不過可能比不上受過ACM訓練的那麼快。二位大概工程用代碼寫的比較多，這類的問題生疏了罷……
——————————————————————————補個代碼吧……出門在外靠平板，也就別太挑剔這個變數名命名的問題了……class Solution {
public:
vector&
vector&
if (nums.size()&<3) return rt;
sort(nums.begin(), nums.end());
int last_a=nums[0]-1, last_b=nums[0]-1;
for (int i=0;i&
if (k &> j nums[i]+nums[j]+nums[k] == 0) {
rt.push_back({nums[i], nums[j], nums[k]});
}
}
}
return rt;
}
};
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
r = set()
numk = {}
for n in nums:
numk[n] = numk.get(n, 0) + 1
def st(a,b,c):
if a &> b:
a,b = b,a
if c &<= a:
return (c,a,b)
elif c &<= b:
return (a,c,b)
else:
return (a,b,c)
for i in range(0, len(nums)):
for j in range(i+1, len(nums)):
k = -(nums[i] + nums[j])
if k in numk:
if k == nums[i] and k == nums[j]:
if numk[k] &>= 3:
r.add(st(nums[i],nums[j],k))
elif k == nums[i] or k == nums[j]:
if numk[k] &>= 2:
r.add(st(nums[i], nums[j], k))
else:
r.add(st(nums[i], nums[j], k))
return [list(v) for v in r]
Python版本的，一點都不拉風，真不甘心啊……而且速度還是排倒數的。不優化的惡果。
好吧，怒優化一波！class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
r = []
numk = set()
for n in nums:
numk.add(n)
nums = sorted(nums)
for i in range(0, len(nums)-2):
if nums[i] &> 0:
break
if i &> 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, len(nums)-1):
if j &> i + 1 and nums[j] == nums[j-1]:
continue
k = -(nums[i] + nums[j])
if k &< nums[j]:
break
if k in numk:
if k == nums[j]:
if nums[j+1] == k:
r.append([nums[i], nums[j], k])
else:
r.append([nums[i], nums[j], k])
return r
然後
等了半天還是沒有人貼最佳解法啊，我來吧。時間複雜度O(n^2)，空間O(1)，不需要哈希表這道題如果思路錯了，會在查重的細節處理上非常麻煩。姐夫的思路就不太正確，他先遍歷兩次，然後再搜索第三個數。正確的思路是，先遍歷一次，再使用兩端掃描的方法找剩下兩個。當然這是個小技巧，現場沒想起來，很正常。
class Solution {
public:
vector&
vector&
int len = nums.size();
if (len &< 3) {
return result;
}
sort(nums.begin(), nums.end());
for (int i = 0; i &< len; ++i) {
if (i &> 0 nums[i] == nums[i-1]) {
continue;
}
int l = i + 1;
int r = len - 1;
while (l &< r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
vector&
result.push_back(triplet);
while (l &< r nums[l] == nums[l+1]) {
l++;
}
while (l &< r nums[r] == nums[r-1]) {
r--;
}
l++;
r--;
} else if (sum &< 0) {
l++;
} else {
r--;
}
}
}
return result;
}
};
順便回憶下當年刷代碼時候的青蔥歲月。。。。。。這題好像提交了12次才過，而且代碼寫的慘不忍睹。
void bsearch(vector&
int i;
if (num[l] == key) {
for (i = l; num[i] == key i &< num.size(); ++i) {
result.push_back(i);
}
return;
}
if (num[r] == key) {
for (i = r; num[i] == key i &>= 0; --i) {
result.push_back(i);
}
return;
}
int middle;
while (l &<= r) {
middle = (l + r) / 2;
if (num[middle] == key) {
result.push_back(middle);
for (i = middle+1; num[i] == key i &< num.size(); ++i) {
result.push_back(i);
}
for (i = middle-1; num[i] == key i &>=0; --i) {
result.push_back(i);
}
return;
} else if (num[middle] &> key) {
r = middle - 1;
} else {
l = middle + 1;
}
}
return;
}
class Solution {
public:
vector&
if (num.size() &< 3) {
return vector&
}
sort(num.begin(), num.end());
int i;
int j;
map&
for (i = 0; i &< num.size(); ++i) {
if (i!=0 num[i] == num[i-1]) {
continue;
}
if (num[i] &> 0) {
break;
}
for (j = i+1; j &< num.size(); ++j) {
if (j != i+1 num[j] == num[j-1]) {
continue;
}
vector&
bsearch(num, -num[i]-num[j], j+1, num.size()-1, ks);
for (int k = 0; k &< ks.size(); ++k) {
if (ks[k] != i ks[k] != j) {
vector&
tmp[0] = num[i];
tmp[1] = num[j];
tmp[2] = num[ks[k]];
char buf[256] = {0};
sprintf(buf, "%d%d%d", tmp[0], tmp[1], tmp[2]);
if (result_index.find(buf) == result_index.end()) {
result_index[buf] = tmp;
}
}
}
}
}
vector&
map&
i = 0;
for (it = result_index.begin(); it != result_index.end(); ++it) {
result[i++].swap(it-&>second);
}
return result;
}
};
真可憐，被要求手寫代碼，還不能掀桌子。
============================================正經答題好了。先講這個演算法題好了。
其實從題目來講，這個題目太難了，而且過分側重於底層的演算法而不是高層的結構。
leetcode的題很多時候其實是一種基本功的訓練，簡單說這個題目就像是請兩個數學教授來解一個大型的不定積分，並不能體現出超乎常人的能力出來。
這種題目要面試的時候手寫真的是要掀桌子的。而且從答案來看，老趙確實佔便宜了。像這種演算法題，最麻煩的是你要知道坑在哪裡，而你沒做過的話就很難搞清楚。
老趙上來直接排序然後兩重循環+BinarySearch，就是因為他知道這條簡單直接的路是沒有坑的，winter沒見過吃虧了。至於排重的問題， HashSet的時間複雜度是O(n)（創建O(n)，查詢O(1)，總體O(n)），也就是不會增加時間複雜度，除非你其他部分的時間複雜度做到了O(n)這個程度了（當然複雜度不代表最終的時間）。
那個Hash很明顯是指HashSet應該可以代替BinarySearch提升性能嘛。
最後講點別的。
很多時候最佳方案不是最好的方案，如果面試遇到這種問題，在沒有限定複雜度的情況下，三重循環+結果排重是最穩妥的實現，稍微優化一下就可以得到老趙的代碼。先做出來再去優化，比做不出來要好很多。
寫了個風騷的版本，也通過leetcode了。。。。。public class Solution
{
public IList&
{
var all = new HashSet&
var left = new HashSet&
var right = new HashSet&
var doubles = new HashSet&
var zeros = 0;
if ( nums.Length &< 3 ) return new int[][] { }; foreach ( var i in nums ) { if ( i &< 0 ) { if ( left.Add( i ) == false ) doubles.Add( i ); } else { if ( right.Add( i ) == false ) doubles.Add( i ); if ( i == 0 ) zeros++; } } var result = from i in left from j in right let k = -(i + j) where all.Contains( k ) (k != i || doubles.Contains( i )) (k != j || doubles.Contains( j ))//這裡是避免只出現一次的數字被兩次添加到結果 select k &> j ? new { i, j, k } : k &> i ? new { i, j = k, k = j } : new { i = k, j = i, k = j };//這裡是排序，為後面的排重做準備
var _result = result.Distinct().Select( item =&> new[] { item.i, item.j, item.k } ).ToList();
if ( zeros &>= 3 )
_result.Add( new[] { 0, 0, 0 } );//這裡是000補丁
return _result.ToArray();
}
}
其實我主要是想測試一下leetcode對LINQ Expression的支持程度。
演算法很簡單，就是把正負數配對，然後看他們的和的取反是不是存在，存在就說明這是一個合法的結果。
其實相當暴力，但關鍵在於正負數配對，導致性能可以很大提升。
因為三個數之和要等於零，必然是++-、--+和000（我們把0歸到+或-之一）這三種情況中的一種。
順便說一句這個純屬賣弄風騷的代碼版本，竟然是C#裡面跑最快的？突然很奇怪其他人都寫了些啥？！(╯°Д°)╯ ┻━┻當前最好的演算法是 時間
這個問題和 3-sum problem 聯繫密切
給定3-sum problem 當前最快的演算法就是 時間。實際上有一個 3-sum conjecture，認為 3-sum 沒有
時間的演算法。
在時間之外，還可以考慮空間。當前 3-sum 最優的演算法是 時間，
空間的確定性演算法 [LWWW16]（上個月才出爐的新鮮文章）
[LWWW16] Deterministic Time-Space Tradeoffs for k-SUM https://arxiv.org/abs/1605.07285
實際上這篇文章提供了一系列演算法。可以以增加時間消耗為代價來節省空間。即用首先，題目：3Sum | LeetCode OJ
節目中答應了大家要放出 @winter 和 @趙劼 寫的代碼。
winter 聽起來冷冰冰的，然而
趙老闆，聽起來霸道總裁既視感，然而
看這拘謹的小眼神
總體上winter表現還是符合預期的，風風火火大大咧咧的，說要日狗日的知乎，立馬就鼓動大家一起日。趙老闆真是……害羞的little boy……
希望輪子哥下次接受採訪作為一個大胖子色情狂不要表現得跟網上反差太大。這道題目也不容易啊，你還要考慮同一個數字到底重複出現了多少遍。譬如說數組是[0,0,0,0]，這樣的話實際上就只有一組答案，而不是4組。同時為了對付那種一個超大數組只有那麼兩三個數字但是重複很多遍的情況，我花了差不多20分鐘的時間在leetcode上面寫，居然submit了一次才AC。現場那麼快估計出來一大堆bug。
class Solution {
public:
vector&
vector&
map&
for (auto i : nums)
{
auto it = counts.find(i);
if (it == counts.end())
{
counts.insert(make_pair(i, 1));
}
else
{
it-&>second++;
}
}
int size = counts.size();
auto keys = new int[size];
auto values = new int[size];
{
int index = 0;
for (auto p : counts)
{
keys[index] = p.first;
values[index] = p.second;
index++;
}
}
for (int i = 0; i &< size; i++) { auto a = keys[i]; for (int j = i; j &< size; j++) { auto b = keys[j]; if (a == b values[i] &< 2) continue; auto c = -(a + b); if (c &< b) break; if (c == b values[j] &< 2) continue; if (c == a values[i] &< 3) continue; if (counts.find(c) == counts.end()) continue; results.push_back({ a, b, c }); } } delete[] keys; delete[] values; return move(results); } };
話說這道編程題是&
Analysis of Algorithms
其實沒啥特別的，尤其是知道答案以後寫出來基本不用動腦子。winter的遞歸解法思路上更有意思一點，只是時間複雜度分析起來比較麻煩，而且最後一個OneSum改成BinarySearch就其實一樣了。想了想，如果是我的話，我會有三個反應。
1，事先告知不要問我狗屎題
2，如果非要問狗屎題，那麼必須提前一個月告訴我，不然我不好準備
3，如果觀眾喜歡狗屎，那麼就準備一坨更大的狗屎，讓觀眾滿意
請了老趙和 winter，結果拖住別人做這種狗屎題……
難道不應該問一點編程的心法，設計的思想，人生的經驗嗎還是說知乎的這個節目只想面向知乎的核心用戶群……Javascript的那個3重循環，明顯很久沒做演算法題了，就先不說了；
偽代碼那個是錯的啊，有這麼幾個地方：1. if (r &< j) continue; //這句是錯的，應該是 if (r &<= j)，否則我給你一個[-2, 1, 2] 你會給我輸出一個 [-2, 1, 1]。2. 查重仍然不夠。即使把(1)的錯誤改掉，仍然會有錯，比如有 [-2, 1, 1, 1]，這個偽代碼會把 [-2, 1, 1]輸出兩次，而題目要求是 unique triplet。另外，用hashtable顯然比binarysearch時間複雜度低，偽代碼的複雜度是O(n^2 log(n))，如果用hash就是O(n^2)。
當然複雜度的問題並不太大，你如果額外說只能用O(1)的空間那我也接受。但是 edge case 不考慮好，就是不及格啊，尤其是上來就聲稱「這題我見過，知道怎麼做」的情況下，寫成這樣真是挺糟糕的。等了這麼久(截止20160621 13:00)都沒有看到最優解，我也忍不住寫了一發。。。
大概用時7min，沒檢查，希望木有bug。。。。Remark: 最壞情況count可以越界，這裡懶特別處理了。。。(假設可以重複取，如果不能重複取，容斥原理減一下即可~~~~)size_t ThreeSum(std::vector&
size_t count = 0;
std::sort(v.begin(), v.end());
for (size_t i = 0; i &< v.size(); ++i) {
size_t right_lowerbound = v.size();
size_t right_upperbound = v.size();
int64_t target = -v[i];
for (size_t left = 0; left &< v.size(); ++left) {
while (right_lowerbound - left &> 0
(int64_t)v[left] + v[right_lowerbound - 1] &>= target) {
--right_lowerbound;
}
while (right_upperbound - left &> 0
(int64_t)v[left] + v[right_upperbound - 1] &> target) {
--right_upperbound;
}
count += right_upperbound - right_lowerbound;
}
}
return count;
}
項目經理（曾經的產品經理）看不懂考題/演算法，幸好視頻快進了（抱拳！），記住了2點。1-winter講三個層次的產品經理。捫心自問，我以前跟tech團隊、跟TPM說事，現在想來真是羞愧難當啊，我TMD就是個普通用戶！還常常做出「我不懂技術啊，我不知道怎麼實現，反之我作為一個普通用戶，我就想要.....」的無賴潑皮狀！幾年後的現在也只能算個中等層次，嘗試了解更多的代碼思維中...關於幾大系統、串聯更多的關聯產品、數據結構，吾將上下而求索……2，winder談什麼時候就該離職了，他說尋找發揮更多了解更多的地方，如果我發揮的價值不再增值而居於平穩，就該離開了。每年都該比上一年做更多更重要的事情。深以為然。趙老師是外霸道內親切的，winter是內外都蠻真摯的，雖然我以前從沒聽說過他們。
為了理解winter原先的演算法，寫了一個帶UT的python版本。原帖中winter和老趙的時間複雜度分析很值得細細品味。
import sys
import traceback
def main():
run_tests()
indexed_arr = generate_array()
print("Official result: {0}".format(k_sum(indexed_arr, 3, len(indexed_arr), 0, create_cache())))
return 0
def run_tests():
test_one_sum()
test_find_k_sum_all_results()
test_k_sum()
print("")
def test_one_sum():
try:
# 4
arr = [1, 2, 3, 4, 5]
cache = create_cache()
result = one_sum(conv_to_indexed_array(arr), len(arr), 4, cache)
if result != [(4, 3)]:
raise ValueError("result not expected: {0}".format(result))
# 1
arr = [1, 2, 3, 4, 5]
cache = create_cache()
result = one_sum(conv_to_indexed_array(arr), len(arr), 1, cache)
if result != [(1, 0)]:
raise ValueError("result not expected: {0}".format(result))
# 5
arr = [1, 2, 3, 4, 5]
cache = create_cache()
result = one_sum(conv_to_indexed_array(arr), len(arr), 5, cache)
if result != [(5, 4)]:
raise ValueError("result not expected: {0}".format(result))
# Non-existent
arr = [1, 2, 3, 4, 5]
cache = create_cache()
result = one_sum(conv_to_indexed_array(arr), len(arr), 0, cache)
if result != None:
raise ValueError("result not expected: {0}".format(result))
sys.stdout.write(".")
sys.stdout.flush()
except ValueError as ex:
traceback.print_exc()
def test_find_k_sum_all_results():
try:
# 9 = 1 + 3 + 5 = 2 + 3 + 4
arr = [1, 2, 3, 4, 5]
result = find_k_sum_all_results(conv_to_indexed_array(arr), 3, 9)
# Sort by the number
result.sort()
if result != [[(1, 0), (3, 2), (5, 4)], [(2, 1), (3, 2), (4, 3)]]:
raise ValueError("result not expected: {0}".format(result))
# 21 = 3 + 8 + 10 = 3 + 9 + 9 = ...
arr = [9, 8, 4, 9, 5, 5, 10, 1, 3, 7]
result = find_k_sum_all_results(conv_to_indexed_array(arr), 3, 21)
# Sort by the number
result.sort()
if [(3, 8), (8, 1), (10, 6)] not in result:
raise ValueError("result not expected: {0}".format(result))
if [(3, 8), (9, 0), (9, 3)] not in result:
raise ValueError("result not expected: {0}".format(result))
# 100 is not achieveable by the array elements
arr = [9, 8, 4, 9, 5, 5, 10, 1, 3, 7]
result = find_k_sum_all_results(conv_to_indexed_array(arr), 3, 100)
if len(result) != 0:
raise ValueError("result is not an empty array--{0}".format(result))
sys.stdout.write(".")
sys.stdout.flush()
except ValueError as ex:
traceback.print_exc()
def test_k_sum():
try:
# 9 = 1 + 3 + 5 = 2 + 3 + 4
arr = [1, 2, 3, 4, 5]
k = 3
n = 9
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 27
#print("Count is {0}".format(cache["count"]))
# 20 = 3 + 8 + 9 = ...
arr = [9, 8, 4, 9, 5, 5, 10, 1, 3, 7]
k = 3
n = 20
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 33
#print("Count is {0}".format(cache["count"]))
# 100 is not achieveable by the array elements
arr = [9, 8, 4, 9, 5, 5, 10, 1, 3, 7]
k = 3
n = 100
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
if result != None:
raise ValueError("result is not None--{0}".format(result))
# 100 array 1, rand 0
arr = get_100_array_1()
k = 3
n = get_100_3_sum_rnd(0)
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 240625
#print("Count is {0}".format(cache["count"]))
# 100 array 1, rand 1
arr = get_100_array_1()
k = 3
n = get_100_3_sum_rnd(1)
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 419527
#print("Count is {0}".format(cache["count"]))
# 100 array 1, rand 2
arr = get_100_array_1()
k = 3
n = get_100_3_sum_rnd(2)
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 255
#print("Count is {0}".format(cache["count"]))
# 100 array 1, rand 3
arr = get_100_array_1()
k = 3
n = get_100_3_sum_rnd(3)
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 8595
#print("Count is {0}".format(cache["count"]))
# 100 array 2, rand 0
arr = get_100_array_2()
k = 3
n = get_100_3_sum_rnd(0)
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 103928
#print("Count is {0}".format(cache["count"]))
# 100 array 2, rand 1
arr = get_100_array_2()
k = 3
n = get_100_3_sum_rnd(1)
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 103917
#print("Count is {0}".format(cache["count"]))
# 100 array 2, rand 2
arr = get_100_array_2()
k = 3
n = get_100_3_sum_rnd(2)
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 678
#print("Count is {0}".format(cache["count"]))
# 100 array 2, rand 3
arr = get_100_array_2()
k = 3
n = get_100_3_sum_rnd(3)
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 598680
#print("Count is {0}".format(cache["count"]))
# 1000 array 1, rand 0
arr = get_1000_array_1()
k = 3
n = get_1000_3_sum_rnd(0)
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 8688
#print("Count is {0}".format(cache["count"]))
# 1000 array 1, rand 1
arr = get_1000_array_1()
k = 3
n = get_1000_3_sum_rnd(1)
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 46150
#print("Count is {0}".format(cache["count"]))
# 1000 array 2, rand 2
arr = get_1000_array_2()
k = 3
n = get_1000_3_sum_rnd(2)
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 6212
#print("Count is {0}".format(cache["count"]))
# 1000 array 2, rand 3
arr = get_1000_array_2()
k = 3
n = get_1000_3_sum_rnd(3)
cache = create_cache()
result = k_sum(conv_to_indexed_array(arr), k, len(arr), n, cache)
# Sort by the number
result.sort()
if result not in find_k_sum_all_results(conv_to_indexed_array(arr), k, n):
raise ValueError("result not expected: {0}".format(result))
# count: 6290
#print("Count is {0}".format(cache["count"]))
sys.stdout.write(".")
sys.stdout.flush()
except ValueError as ex:
traceback.print_exc()
def k_sum(indexed_arr, k, i, n, cache):
cache["count"] += 1
if (k, i, n) in cache:
return cache[(k, i, n)]
if k == 1:
return one_sum(indexed_arr, i, n, cache)
result = None
for (curr_idx, (num, index)) in enumerate(indexed_arr):
cache["count"] += i - 1 # For slicing the array
ret = k_sum(indexed_arr[:curr_idx] + indexed_arr[curr_idx + 1:], k - 1,
i - 1, n - num, cache)
if ret != None:
cache["count"] += k # For building the array
result = ret + [(num, index)]
cache[(k, i, n)] = result
return result
return result
def one_sum(indexed_arr, i, n, cache):
cache["count"] += 1
if (1, i, n) in cache:
return cache[(1, i, n)]
result = None
for (num, index) in indexed_arr:
cache["count"] += 1
if num == n:
result = [(num, index)]
cache[(1, i, n)] = result
return result
return result
def conv_to_indexed_array(arr):
result = []
for (i, num) in enumerate(arr):
result.append((num, i))
return result
def generate_array():
result = [2, 5, 1, -6, 5, 8, 3, 9, 0, 8]
return conv_to_indexed_array(result)
def get_100_array_1():
return [ 8, 52, 55, 74, 15, 33, 68, 35, 24, 65, 44, 50, 89, 44, 36, 63, 81,
40, 55, 58, 77, 100, 59, 53, 55, 68, 35, 36, 85, 90, 60, 75, 55,
91, 7, 88, 99, 39, 54, 74, 58, 82, 50, 3, 90, 36, 88, 5, 93, 21,
97, 67, 81, 17, 44, 17, 36, 44, 30, 37, 40, 47, 61, 21, 55, 22, 99,
32, 32, 54, 84, 36, 77, 88, 6, 71, 18, 65, 18, 9, 14, 1, 22, 58,
56, 20, 57, 13, 75, 98, 34, 25, 85, 53, 86, 66, 99, 17, 32, 45, ]
def get_100_array_2():
return [ 88, 24, 65, 20, 59, 96, 78, 48, 71, 52, 16, 44, 59, 36, 47, 70,
85, 64, 30, 93, 87, 60, 46, 61, 83, 69, 36, 97, 19, 15, 2, 59, 50,
98, 61, 71, 15, 47, 2, 84, 22, 71, 84, 65, 40, 64, 79, 38, 12, 73,
35, 8, 60, 21, 96, 98, 66, 65, 34, 76, 66, 16, 51, 62, 80, 95, 41,
21, 93, 89, 80, 92, 46, 78, 64, 36, 83, 49, 83, 66, 47, 90, 74, 82,
21, 1, 25, 32, 44, 13, 63, 82, 57, 50, 3, 89, 44, 43, 19, 87, ]
def get_100_3_sum_rnd(index):
if index == 0:
return 288
elif index == 1:
return 289
elif index == 2:
return 157
elif index == 3:
return 17
else:
raise ValueError("Invalid index--{0}".format(index))
def get_1000_array_1():
return [ 404, 118, 227, 795, 986, 803, 602, 920, 839, 731, 648, 474, 636,
954, 995, 740, 510, 339, 522, 971, 576, 978, 380, 95, 650, 588,
632, 441, 989, 820, 525, 753, 789, 865, 180, 410, 738, 660, 102,
669, 716, 159, 745, 260, 539, 594, 241, 761, 368, 35, 129, 380,
754, 720, 885, 130, 892, 693, 386, 840, 131, 863, 725, 580, 510,
123, 109, 117, 259, 683, 257, 716, 539, 658, 532, 691, 68, 300,
356, 985, 365, 640, 815, 322, 481, 259, 214, 805, 393, 172, 94,
120, 451, 357, 582, 669, 292, 253, 717, 202, 298, 477, 20, 238,
548, 337, 561, 474, 271, 648, 862, 974, 773, 69, 432, 961, 976,
435, 928, 273, 950, 652, 772, 435, 727, 388, 523, 22, 249, 7, 729,
766, 306, 888, 848, 828, 226, 267, 308, 176, 925, 341, 2, 892, 269,
610, 202, 8, 246, 98, 36, 381, 620, 927, 970, 916, 322, 429, 241,
237, 180, 979, 139, 322, 777, 851, 319, 770, 140, 853, 332, 937,
826, 158, 89, 645, 781, 976, 896, 808, 778, 561, 702, 534, 62, 331,
244, 977, 620, 324, 776, 33, 486, 488, 477, 837, 363, 782, 607,
768, 416, 581, 483, 46, 363, 168, 728, 445, 283, 368, 552, 604,
818, 584, 208, 553, 307, 560, 115, 605, 57, 953, 623, 935, 97, 313,
555, 160, 54, 616, 560, 257, 242, 794, 432, 170, 266, 44, 467, 213,
753, 62, 33, 139, 789, 695, 759, 424, 635, 217, 208, 295, 449, 331,
205, 399, 720, 440, 145, 378, 922, 278, 327, 595, 580, 65, 271,
754, 87, 392, 851, 123, 115, 70, 544, 535, 202, 848, 815, 743, 974,
271, 796, 653, 926, 796, 173, 956, 404, 359, 712, 988, 799, 148, 1,
800, 75, 947, 723, 727, 964, 468, 168, 202, 514, 86, 243, 48, 64,
669, 48, 824, 702, 799, 534, 325, 388, 696, 243, 347, 159, 729, 95,
5, 274, 597, 651, 275, 352, 249, 865, 887, 967, 899, 266, 320, 327,
931, 141, 947, 965, 654, 4, 932, 409, 834, 672, 998, 63, 468, 732,
582, 91, 828, 946, 436, 753, 821, 61, 580, 20, 626, 257, 251, 347,
165, 842, 390, 634, 686, 9, 235, 939, 569, 250, 957, 637, 580, 719,
355, 675, 465, 63, 641, 692, 291, 704, 620, 92, 168, 854, 864, 628,
568, 108, 302, 368, 688, 592, 770, 503, 798, 841, 828, 760, 845,
96, 926, 109, 812, 231, 259, 317, 178, 168, 831, 12, 457, 280, 606,
582, 382, 587, 732, 164, 884, 796, 735, 377, 517, 988, 990, 827,
22, 447, 325, 142, 432, 225, 572, 503, 401, 790, 985, 258, 107,
850, 1000, 539, 971, 309, 917, 50, 860, 543, 452, 753, 885, 37,
805, 619, 381, 459, 373, 652, 357, 706, 513, 748, 26, 655, 563,
938, 199, 448, 578, 398, 97, 131, 805, 213, 390, 947, 485, 358,
837, 26, 354, 963, 915, 483, 695, 227, 169, 185, 597, 908, 590,
904, 314, 323, 355, 452, 799, 768, 252, 508, 407, 586, 499, 162,
618, 838, 916, 792, 817, 524, 37, 175, 280, 603, 199, 736, 378, 28,
108, 347, 24, 119, 106, 10, 976, 754, 970, 166, 785, 401, 818, 114,
940, 697, 540, 667, 490, 749, 686, 631, 363, 719, 205, 302, 76,
392, 697, 181, 452, 787, 229, 968, 827, 131, 256, 885, 750, 855,
661, 72, 595, 422, 33, 242, 835, 56, 339, 879, 241, 439, 246, 207,
22, 27, 179, 947, 881, 462, 930, 72, 923, 330, 940, 338, 526, 498,
642, 350, 96, 169, 183, 147, 36, 604, 507, 521, 722, 267, 706, 482,
292, 739, 760, 478, 523, 619, 728, 295, 869, 759, 570, 732, 562,
528, 670, 449, 123, 52, 425, 814, 598, 257, 584, 195, 285, 373,
229, 954, 17, 371, 140, 237, 28, 596, 370, 892, 934, 476, 786, 46,
291, 366, 991, 725, 101, 881, 998, 529, 856, 957, 613, 657, 573,
951, 516, 775, 785, 972, 687, 222, 461, 171, 488, 52, 421, 76, 83,
496, 862, 454, 184, 623, 399, 898, 164, 598, 593, 326, 101, 652, 8,
60, 901, 338, 23, 921, 864, 376, 189, 699, 503, 789, 694, 315, 593,
969, 23, 1000, 186, 180, 156, 615, 511, 334, 803, 685, 818, 641,
697, 542, 351, 296, 157, 163, 2, 857, 379, 576, 255, 509, 603, 513,
683, 760, 37, 549, 601, 423, 200, 133, 577, 223, 184, 104, 259,
508, 924, 998, 950, 88, 520, 176, 8, 476, 217, 160, 299, 947, 999,
324, 452, 647, 865, 689, 463, 767, 481, 184, 173, 715, 686, 767,
664, 739, 16, 267, 99, 483, 848, 311, 639, 508, 209, 576, 500, 894,
875, 391, 197, 583, 539, 571, 561, 479, 153, 125, 389, 481, 613,
455, 731, 547, 808, 633, 952, 518, 943, 112, 742, 535, 662, 143,
345, 158, 606, 138, 369, 607, 531, 325, 819, 497, 563, 794, 841,
355, 967, 688, 162, 398, 575, 185, 224, 620, 936, 857, 815, 793,
371, 159, 51, 876, 614, 965, 623, 507, 493, 23, 412, 13, 513, 304,
456, 842, 243, 734, 622, 663, 850, 353, 856, 771, 786, 243, 273,
714, 630, 297, 157, 981, 330, 718, 540, 413, 845, 802, 976, 651,
237, 164, 760, 571, 536, 191, 541, 787, 634, 459, 166, 242, 347,
812, 155, 769, 247, 112, 55, 202, 403, 101, 842, 498, 855, 250,
696, 751, 964, 899, 789, 318, 453, 570, 470, 158, 104, 169, 281,
318, 407, 564, 989, 784, 840, 404, 909, 465, 113, 642, 667, 994,
280, 489, 664, 666, 985, 972, 82, 490, 669, 433, 93, 875, 439, 477,
538, 415, 796, 482, 548, 596, 899, 762, 540, 12, 195, 234, 697,
771, 669, 18, 416, 387, 713, 522, 713, 93, 630, 43, 736, 237, 165,
769, 187, 577, 690, 707, 54, 769, 735, 823, 640, 426, 918, 695, 76,
100, 105, 403, 623, 976, 320, 600, 857, 176, 300, 660, 911, 604,
742, 179, 142, 445, 637, ]
def get_1000_array_2():
return [ 289, 552, 459, 938, 42, 986, 108, 746, 199, 716, 196, 834, 518,
677, 133, 251, 534, 149, 317, 482, 855, 402, 825, 87, 817, 370,
687, 448, 886, 630, 461, 921, 589, 765, 312, 160, 572, 854, 682,
481, 741, 529, 591, 344, 174, 699, 281, 11, 686, 893, 13, 89, 769,
556, 219, 21, 444, 440, 195, 650, 921, 554, 435, 547, 366, 184,
502, 969, 588, 231, 201, 498, 401, 168, 197, 696, 797, 259, 668,
836, 992, 360, 189, 171, 112, 215, 840, 625, 619, 980, 395, 908,
183, 424, 416, 249, 570, 556, 851, 706, 356, 5, 899, 137, 905, 393,
743, 128, 597, 878, 47, 913, 716, 307, 984, 364, 802, 242, 882,
790, 156, 659, 599, 317, 453, 714, 736, 999, 236, 434, 144, 110,
644, 829, 496, 376, 463, 75, 367, 743, 114, 33, 63, 996, 956, 270,
753, 930, 785, 587, 211, 331, 219, 806, 312, 288, 184, 425, 747,
665, 342, 374, 441, 863, 519, 309, 493, 867, 272, 659, 985, 709,
550, 971, 263, 100, 767, 765, 618, 811, 902, 212, 493, 387, 616,
141, 461, 607, 269, 426, 417, 284, 669, 766, 764, 377, 71, 386,
100, 506, 21, 843, 829, 589, 466, 556, 767, 761, 590, 282, 849,
982, 89, 616, 171, 562, 889, 389, 437, 875, 314, 68, 845, 16, 259,
258, 35, 725, 636, 772, 433, 30, 923, 715, 995, 83, 242, 745, 827,
1000, 652, 851, 482, 825, 123, 23, 142, 187, 396, 337, 430, 156,
783, 173, 693, 952, 949, 429, 19, 186, 680, 499, 856, 90, 149, 604,
161, 348, 876, 222, 968, 884, 855, 255, 115, 418, 524, 699, 874,
699, 759, 959, 863, 126, 979, 240, 885, 179, 721, 990, 823, 903,
583, 87, 6, 506, 341, 461, 61, 462, 786, 139, 763, 381, 226, 611,
32, 237, 477, 516, 848, 483, 89, 786, 815, 277, 622, 610, 487, 807,
108, 694, 859, 77, 585, 1000, 292, 693, 460, 725, 389, 508, 65,
268, 35, 125, 946, 821, 184, 536, 641, 704, 169, 43, 122, 839, 283,
82, 399, 337, 937, 439, 684, 66, 630, 463, 540, 471, 351, 691, 382,
736, 530, 47, 81, 653, 928, 783, 163, 105, 34, 163, 671, 217, 269,
921, 341, 224, 173, 754, 897, 334, 815, 837, 671, 643, 131, 420,
38, 205, 258, 468, 374, 184, 998, 763, 26, 877, 782, 752, 58, 9,
123, 475, 683, 601, 249, 840, 486, 158, 540, 660, 172, 377, 738,
351, 286, 800, 739, 155, 484, 494, 277, 438, 370, 352, 106, 467,
612, 424, 810, 523, 528, 306, 434, 415, 933, 54, 857, 473, 165,
677, 119, 820, 687, 126, 641, 918, 382, 628, 640, 939, 136, 888,
802, 390, 727, 537, 390, 806, 92, 206, 128, 664, 313, 773, 924,
853, 439, 899, 996, 533, 21, 737, 468, 556, 372, 870, 145, 434,
683, 824, 657, 64, 262, 511, 318, 579, 172, 104, 600, 155, 127, 67,
733, 864, 647, 526, 733, 605, 973, 374, 461, 374, 788, 28, 315,
251, 860, 605, 473, 302, 845, 117, 645, 557, 622, 396, 615, 396,
180, 205, 956, 531, 688, 288, 660, 317, 173, 675, 423, 714, 878,
651, 286, 193, 661, 955, 892, 101, 604, 358, 315, 117, 850, 113,
564, 204, 426, 487, 805, 936, 842, 664, 366, 974, 917, 32, 498, 15,
573, 22, 432, 398, 701, 705, 998, 294, 646, 252, 629, 605, 386,
375, 92, 73, 840, 389, 767, 590, 562, 329, 132, 547, 643, 932, 631,
731, 776, 471, 337, 246, 3, 674, 606, 512, 20, 134, 640, 388, 438,
750, 927, 286, 510, 371, 157, 417, 146, 966, 483, 422, 474, 765,
393, 259, 473, 129, 306, 826, 276, 263, 654, 854, 550, 433, 81,
968, 271, 286, 917, 470, 537, 851, 459, 253, 760, 596, 383, 278,
56, 577, 993, 485, 470, 578, 575, 749, 862, 147, 987, 243, 849,
134, 91, 223, 271, 811, 975, 292, 441, 681, 837, 881, 649, 906,
746, 389, 278, 808, 892, 599, 482, 319, 404, 91, 687, 481, 62, 970,
571, 683, 6, 824, 353, 617, 796, 637, 645, 423, 223, 556, 861, 409,
162, 183, 274, 957, 211, 141, 108, 50, 312, 238, 829, 243, 814,
629, 915, 102, 839, 599, 719, 997, 862, 330, 644, 805, 761, 296,
205, 350, 112, 492, 856, 359, 907, 774, 170, 65, 420, 295, 383, 68,
814, 958, 201, 519, 961, 871, 566, 523, 706, 64, 911, 279, 190,
727, 912, 36, 281, 350, 239, 940, 416, 836, 631, 307, 26, 933, 714,
112, 471, 976, 60, 146, 850, 366, 358, 788, 48, 37, 368, 1, 915,
616, 5, 357, 21, 733, 606, 558, 469, 218, 917, 241, 1000, 493, 56,
69, 155, 499, 40, 480, 891, 530, 82, 957, 533, 923, 837, 280, 37,
314, 835, 189, 492, 283, 683, 393, 101, 601, 194, 220, 413, 654,
510, 906, 675, 420, 375, 235, 922, 899, 100, 767, 206, 621, 662,
780, 650, 924, 573, 946, 752, 66, 366, 703, 198, 603, 684, 613, 38,
528, 122, 379, 506, 894, 420, 706, 904, 783, 736, 414, 602, 958,
849, 820, 617, 701, 317, 188, 837, 711, 979, 477, 98, 739, 849, 67,
22, 533, 54, 561, 513, 583, 655, 774, 87, 313, 194, 235, 525, 31,
344, 529, 871, 252, 495, 417, 812, 143, 684, 708, 370, 239, 580,
641, 829, 147, 236, 18, 363, 977, 891, 894, 667, 848, 54, 153, 733,
687, 434, 501, 897, 245, 321, 569, 892, 274, 127, 810, 306, 495,
742, 947, 82, 912, 554, 107, 32, 506, 805, 563, 504, 618, 834, 514,
28, 210, 581, 960, 98, 48, 913, 307, 433, 105, 726, 876, 526, 940,
786, 517, 287, 616, 29, 151, 638, 935, 930, 95, 479, 808, 869, 150,
416, 1000, 43, 595, 329, 350, 602, 451, 149, 273, 404, 133, 463,
607, 39, 407, 788, 608, 953, 879, 137, 320, 11, 240, 744, 826, 944,
899, 282, 777, 170, 143, 666, 840, ]
def get_1000_3_sum_rnd(index):
if index == 0:
return 2291
elif index == 1:
return 823
elif index == 2:
return 2209
elif index == 3:
return 2217
else:
raise ValueError("Invalid index--{0}".format(index))
def find_k_sum_all_results(indexed_arr, k, n):
indexed_set = set(indexed_arr)
result = find_k_sum_all_results_rec(indexed_set, k, n)
result = [list(x) for x in result]
return result
def find_k_sum_all_results_rec(indexed_set, k, n):
if k == 1:
return find_one_sum_all_results(indexed_set, n)
result = set()
for (num, index) in indexed_set:
indexed_set.remove((num, index)) # Take the number before recursion
ret = find_k_sum_all_results_rec(indexed_set, k - 1, n - num)
# We sort the result, so that duplicate ones can automatically be
# eliminated
# A set needs to use tuples rather than lists as members
result.update([tuple(sort_indexed_iterable(list(x) + [(num, index)]))
for x in ret])
indexed_set.add((num, index)) # Put the number back
return result
def sort_indexed_iterable(indexed_iterable):
sorted_list = list(indexed_iterable)
sorted_list.sort()
return sorted_list
def find_one_sum_all_results(indexed_set, n):
result = set()
for (num, index) in indexed_set:
if num == n:
result.add(((num, index),))
return result
def create_cache():
return { "count" : 0 }
sys.exit(main())
講真這題大二的演算法課上就有提及，而且真的不算難，考試都沒法當作最後一題。真的說明不了任何問題，根據答題來揣測甚至評估兩位大神的演算法水平簡直痴人說夢。。。
越來越喜歡老趙了！！！！！！除了智商不如他，其他方面的回答和我的三觀好像好像啊。
winter：要是把你那工作給我干我早辭職了趙劼：要是我來面試你根本拿不到我的工作！
很多時候，面試時出的演算法題，短時間我是寫不出來的。看了這期頓時心裡平衡了！
術業有專攻吧，雖然二位都是全棧大牛，但win 神明顯是偏前端的，演算法肯定沒有老趙6，出的題雖然基礎，但還是win神吃虧鳥～不過也沒關係，娛樂聊天嘛～期待把全部視頻放出來～～
趙劼寫的n2logn，這要是去微軟面試，肯定就掛了。可見微軟是一家無良的壓迫無產階級的公司，是我們的敵人，滑稽
推薦閱讀：
※如何評價售價 4399 元的智米空調？
※戴著hd800出街是一種怎樣的體驗？
※【技術貼】手機掉廁所裡面如何補救？
※如何評價《殺出重圍3：人類革命》這部遊戲？