是不是奖越大，致辞时间可以越长？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Movie - 无限影话

是不是奖越大，致辞时间可以越长？

是不是奖越大，致辞时间可以越长？# Movie - 无限影话

S*Y2013-02-25 08:02

1 楼

第一个，Given a file with a lot of words (10 million) find out the top 10% m
ost frequently occurring words.
这题我的想法是，先走一遍file, hash到 hash table,key是word, 出现的次数是value
，然后走一边hash table,用一个heap来存频率最高的词。这样就走了两遍，有没有可能
只走一边？比如upodate heap的key,但是heap是不可以寻找的。
第二题，如果输出第三题，Given a number determine whether the number is sum of consecutive
positive integers, if it is not return false else return true. Consecutive
integers can be from 2 to n。

z*72013-02-25 08:02

2 楼

现在公司12/24辞职
新公司1/5入职。中间十几天unpaid gap.会有问题吗
新h1b已经批准
谢谢了

v*t2013-02-25 08:02

3 楼

前面小奖，一下子就音乐声了

c*o2013-02-25 08:02

4 楼

第二题如果n不能被首先产生一个初始的array保存prime number {1,2,3,5}。每增加一个prime number就
放在这个array里面
还有一个减少查找次数的规律是对于每6个连续的数6x,6x+1,6x+2,6x+3,6x+4,6x+5只要
检查6x+1和6x+5就可以了。这样查找的次数减少到1/3。

m
value
可能

【在 S**Y 的大作中提到】

: 第一个，Given a file with a lot of words (10 million) find out the top 10% m
: ost frequently occurring words.
: 这题我的想法是，先走一遍file, hash到 hash table,key是word, 出现的次数是value
: ，然后走一边hash table,用一个heap来存频率最高的词。这样就走了两遍，有没有可能
: 只走一边？比如upodate heap的key,但是heap是不可以寻找的。
: 第二题，如果输出: 第三题，Given a number determine whether the number is sum of consecutive
: positive integers, if it is not return false else return true. Consecutive
: integers can be from 2 to n。

s*e2013-02-25 08:02

5 楼

I guess not. what did your lawyer say?

P*52013-02-25 08:02

6 楼

Nod

c*e2013-02-25 08:02

7 楼

Any positive integer can be written as the sum of consecutive positive
numbers. The number can be written as 2^k(2*l+1). Because the sum of j
integers starting from i has a sum of j*(2*i+j-1)/2. Force the two be
equal, we have 2^(k+1)(2*l+1) = j*(2*i+j-1). Notice one of j and 2*i+j-1
is odd while the other is even, it is easy to solve it. To make sure i>=1,
we need to consider 2^k>=l and 2^kThis solution will leave one problem, those 2^k type (1,2,4,8,16,etc) is
only the sum of a '

c*g2013-02-25 08:02

8 楼

不care，他们说话的时候我就灌水

c*e2013-02-25 08:02

9 楼

Your test is OK. But the complexity is O(n^2).
The AKS primality test has complexity O(log^(6+epsilon)) for each number.
So the complexity for checking all numbers between 1 and n is at most
O(n*log^(6+epsilon)).

【在 c*****o 的大作中提到】

: 第二题如果n不能被: 首先产生一个初始的array保存prime number {1,2,3,5}。每增加一个prime number就
: 放在这个array里面
: 还有一个减少查找次数的规律是对于每6个连续的数6x,6x+1,6x+2,6x+3,6x+4,6x+5只要
: 检查6x+1和6x+5就可以了。这样查找的次数减少到1/3。
:
: m
: value
: 可能

c*o2013-02-25 08:02

10 楼

您太专业了，佩服～

【在 c**********e 的大作中提到】

: Your test is OK. But the complexity is O(n^2).
: The AKS primality test has complexity O(log^(6+epsilon)) for each number.
: So the complexity for checking all numbers between 1 and n is at most
: O(n*log^(6+epsilon)).

g*u2013-02-25 08:02

11 楼

如果consecutive integers可以是n，那么所有的n都可以表示为consecutive integers
的和啊。算法如下：
pair consecutive_sum(int n)
{
int i = 2;
int j = (sqrt((double)n * 8 + 9) - 1)/2;// find j such that sum_2^j < n
and sum_2^(j+1) > n
int cur_sum = (2 + j) * (j-1) / 2;
assert( cur_sum <= n );
assert ( (cur_sum + j + 1) > n);
while ( i <= n && j <= n)
{
if (cur_sum == n)
return make_pair(i,j);
else if(cur_sum < n)
{
j++;
cur_sum += j;
}else if(cur_sum