S**Y
发帖数: 136 | 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。 | c*****o
发帖数: 178 | 2 第二题如果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。
| c**********e
发帖数: 2007 | 3 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^k
This solution will leave one problem, those 2^k type (1,2,4,8,16,etc) is
only the sum of a ' | c**********e
发帖数: 2007 | 4 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*****o
发帖数: 178 | 5 您太专业了，佩服～
【在 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*****u
发帖数: 298 | 6 如果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 | h**6
发帖数: 4160 | 7 第二题，把从2到sqrt(n)所有没有被划去的数的倍数都划去，剩下的就是素数。 |
|
