LinkedIn一面攒人品

hr多久回复你的？ 我这周面的linkedin，hr不回邮件吖

readman 发表于 2014-8-1 19:21
http://stackoverflow.com/questions/8110538/total-number-of-possible-triangles-from-n-numbers

Note: I don't start while loop from the beginning for each j.

人家特意说了是因为counting没有nested while loop from j. 他的k虽然是nested的loop， 但和j一样只需要遍历一遍from i to n.

你在看看你最后的实现， 有一个l, from j to k. 这才是关键。

基本可以确定这题要找出所有解是没法n^3以下。

北美农民 发表于 2014-8-2 17:48
人家特意说了是因为counting没有nested while loop from j. 他的k虽然是nested的loop， 但和j一样只 ...

啊..它不是一直再说他的算法是O(n^2)的么....

补充内容 (2014-8-2 19:04):
哦... 我明白了..while take n  

请问楼主申请的是linkedin的什么职位，我看官网上new graduate 2015的还没有出来啊。

第二题 o(n^2)吧 a<b<c, 所以只要判断a+b>c；
for(c = array.length-1 .... 2)
    b= c-1, a = 0;
    while(a<b){
         if(a+b > c) return true;
         else a++;
    }

这个应该是n^2 solution，不知道是否有更快的。

qshen1989 发表于 2014-8-1 15:02
第一题根据这个改一下：http://answer.ninechapter.com/solutions/valid-number/ 这个网站的答案大都很精练 ...

排完序后一重循环就好了。

检查a1 a2 a3
a2 a3 a4
a3 a4 a5
....
an-2   an-1  an

readman 发表于 2014-8-1 21:37
https://gist.github.com/gaoyike/40df1e0ec5a6c95e0014

做出来了

这个答案不对吧。。。先不说可不可以重复使用数字的问题，关键是会miss掉很多解。
比如5,7,9,10.13,15这几个数
i = 0, j = 1, k = 2的话，(5,7,9), (5,7,10), (5,7,13)都是合理解
但这时k已经到了15这里的，现在变j到9的话，k只能从15往后跑，
就会miss掉5,9,10和5,9,13这两个解。
我不觉得这题有比n^3的方法更快的解。。。。。。