g****v
发帖数: 971 | 1 第一题挺难的。
suppose the array has n elements with an average "avg". then we divide the
array into two subarrays.
Suppose the first subarray has n1 elements with average "avg1" and 2nd
subarray has n2 elements with average "avg2".
we can have equations:
n1*avg1 + n2 * avg2 = n*avg
n1+n2=n
since we are looking for two subarrays with same average, we have :
avg1 = avg2
so we finally have :
(n1+n2)*avg1 = n*avg => n*avg1 = n*avg => avg1 = avg
结论： 数组的平均数就是要找的ｓｕｂａｒｒａｙ的平均数
所以现在的问题就变成了怎么找到subset whose av... 阅读全帖 |
|
g***s
发帖数: 3811 | 2 The idea is correct but the last step has error.
for i=1 to n {
avg = A * i;
find t closest to avg that S[n][t][i] = true;
if |t/i - avg| < |best - avg| then best = t/i;
}
then it would always divide to two group with size n and 0 since t/n-
avg=0 when t=sumOf(a);
even if using for i=1 to n-1, it is still not correct:e.g.
1,4,4,8,8 avg=5
by this way, you will divide to {1 4 8 8} and {4} but correct one should
be {1 8} { 4 4 8}
should change to:
for i=1 to n {
avg1 = t/i;
avg2 = (sum-t... 阅读全帖 |
|
b**********5
发帖数: 7881 | 3 先问: map reduce mean
我说， mapper emit （number， 1）， 可以弄几个combiner， emit （partial sum
， partial N）， 然后最后一个reducer， add up sum divide by N
问： 会有什么问题
答： sum overflow， 可以用 long， 或者big integer？
此处省略一千字
原来是这样的：something called rolling average
let's say avg0 is average for a0... aN0, avg1 is average for aN0 .... aN1....
so the total average is avg0*(N0/N) + avg1*(N1/N) + avg2*(N2/N)....
so the combiner can emit (avg0, N0), (avg1, N1) ... pair
and the reducer would calculate the total average
=============... 阅读全帖 |
|
g****g
发帖数: 310 | 4 绝对没必要，也不应该写这类代码。根本没有任何速度上的提升。(如果有，那么是在
你做梦的时候)
unsigned long avg1=0, avg2=0;
for (int n=0;n<1000000; n++)
{
int j = 0, i=0;
a = rdtsc();
i+= !(!(j));
b=rdtsc()-a;
avg1+=b;
j=0; i=1;
a = rdtsc();
if( j!=0 ) i++;
b=rdtsc()-a;
avg2+=b;
j++;i++;
}
std::cout << "Take:" << avg1/1000000 << std::endl;
std::cout << "Take:" << avg2/1000000 << std::endl;
两者的结果基本相同。 |
|
g****g
发帖数: 310 | 5 一样的结果，整天讨论哪个快，却自己不去测试一下有意义么？
unsigned long avg1=0, avg2=0;
srand( (unsigned)time( NULL ) );
int j = 0, i=0;
for (int n=0;n<1000000; n++)
{
j = (rand() > RAND_MAX/2) ? 0 : 1;
a = rdtsc();
i+= !(!(j));
b=rdtsc()-a;
avg1+=b;
j=0; i=1;
a = rdtsc();
if( j!=0 ) i++;
b=rdtsc()-a;
avg2+=b;
}
std::cout << "Take:" << avg1/1000000 << std::endl;
std::cout << "Take:" << avg2/1000000 << std: |
|
w******1
发帖数: 520 | 6 这个不错， 不过电话面试要是紧张了， 可能真做不出来。
count=1,
return avg1= a1,
count =2,
retun avg2 = a1+a2/2 = > a1-a1/2+a2=> a1 + (a2-a1)/2
=> avg1 + (a2-a1)/2
count =3,
retun avg3 = a1+a2+a3/3 => 2(a1+a2)/6 + 2 a3/6=> 2 avg2 /3 + a3/3
=> avg2 + (a3-avg2)/3
....
avgn = avg(n-1) + (an-avg(n-1))/n |
|
g***s
发帖数: 3811 | 7 the sample:
1 4 4 8 8
avg = 5
the best by your step will get best=0.25 -- (t = 21, i = 4, t/i-avg=0.25)
which is: {1 4 8 8} and {4}.
{1 4 8 8} {4} the |avg1 - avg2| = 1.25
correct one should be:
{1 8} { 4 4 8} the |avg1 - avg2| = 0.83 |
|
S******t
发帖数: 151 | 8 我贴一个第一题能通过的代码吧：
vector bestA;
int bestLen;
void search(int idx, int sum, int len, vector>>& f,
vector& ret, vector& A) {
//cout << idx << " " << sum << " " << len << endl;
if (idx == 0) {
int lenA = bestA.size();
vector v = ret;
/*
for (int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl;
*/
if (v.size() < lenA || lenA == 0) {
bestA = v;
return;
... 阅读全帖 |
|
t***u
发帖数: 2057 | 9 就在昨天，一个寒风习习落叶萧萧的秋日午后，我那几十载波澜不惊的人生终于迎来了
第一只小鸟，而且一来就是两只。一个在Handicap 1的四杆洞，一个在handicap 18的
三杆洞。
三杆洞的鸟是早就盼着的，只要开杆上果岭，总有机会不是。但这次是个果岭边的chip
in，算是意外之喜。
第四洞355码的四杆洞是最难的一个，两边都是密林子，右边大陡坡，fireway窄。果岭
在半坡上。对我而言，要完美的两杆才可能上。3wood开球slice，从坡上弹了一下，落
在Fireway一片裸露的硬泥地上，GPS显示还有180多，加上上坡，明显是我任何一根杆
子都reach不了的。带着layup的轻松用3hybird挥了一杆，眼见着奔果岭前的坡脚去了
。把cart停到果岭边，下去找球，看洞的正前方16feet处有个白球。第一反映是前边的
人太大意了，果岭上的球也不捡，回头一想不至于啊。上去一看，自己的球。大概是弹
道低，前冲大，从坡下一路连滚带爬上来的。仔细看线，推进了。这个洞我一向的希望
就是不罚杆，bogey，结果三杆累积的lucky整出个鸟来。可惜这个球在下一洞开球就直
接打飞了，应该当时... 阅读全帖 |
|
t***u
发帖数: 2057 | 10 就在昨天，一个寒风习习落叶萧萧的秋日午后，我那几十载波澜不惊的人生终于迎来了
第一只小鸟，而且一来就是两只。一个在Handicap 1的四杆洞，一个在handicap 18的
三杆洞。
三杆洞的鸟是早就盼着的，只要开杆上果岭，总有机会不是。但这次是个果岭边的chip
in，算是意外之喜。
第四洞355码的四杆洞是最难的一个，两边都是密林子，右边大陡坡，fireway窄。果岭
在半坡上。对我而言，要完美的两杆才可能上。3wood开球slice，从坡上弹了一下，落
在Fireway一片裸露的硬泥地上，GPS显示还有180多，加上上坡，明显是我任何一根杆
子都reach不了的。带着layup的轻松用3hybird挥了一杆，眼见着奔果岭前的坡脚去了
。把cart停到果岭边，下去找球，看洞的正前方16feet处有个白球。第一反映是前边的
人太大意了，果岭上的球也不捡，回头一想不至于啊。上去一看，自己的球。大概是弹
道低，前冲大，从坡下一路连滚带爬上来的。仔细看线，推进了。这个洞我一向的希望
就是不罚杆，bogey，结果三杆累积的lucky整出个鸟来。可惜这个球在下一洞开球就直
接打飞了，应该当时... 阅读全帖 |
|
