d***8
发帖数: 1552 | 1 write a program, to generate a seris of numbers which are N to the power of
M, where N and M are integer that greater than 1.
The seris of the number should be in increasing order.
i.e.,
we have 2^2, 2^3, 2^4, ...
and 3^2, 3^3, 3^4, ...
and 4^2, 4^3, 4^4, ..., etc.
so the number should be generated in this order:
4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, ......
How to write the program to do this??? | B********n
发帖数: 384 | 2 N-way merge. Build a heap of N elements, then keep doing extract(min) and
insertion. Complexity is O(Log(N) * N * M)
of
【在 d***8 的大作中提到】
: write a program, to generate a seris of numbers which are N to the power of
: M, where N and M are integer that greater than 1.
: The seris of the number should be in increasing order.
: i.e.,
: we have 2^2, 2^3, 2^4, ...
: and 3^2, 3^3, 3^4, ...
: and 4^2, 4^3, 4^4, ..., etc.
: so the number should be generated in this order:
: 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, ......
: How to write the program to do this???
| d***8
发帖数: 1552 | 3 N is infinite. So you method won't work.
【在 B********n 的大作中提到】
: N-way merge. Build a heap of N elements, then keep doing extract(min) and
: insertion. Complexity is O(Log(N) * N * M)
:
: of
| c****m
发帖数: 179 | 4 first, to compute N^M, (using binary recursive or DP for each N, then
optimize it by utilizing sparsity of prime number both in space and time
complexity over all N).
Then just N-way merge, I don't see the need of a heap. Just do linear scan
of each array.
Any Better Idea? | d***8
发帖数: 1552 | 5 Sorry I don't understand what you said. Could you elaborate on it? and show
some examples please.
Prime number is also infinite.
scan
【在 c****m 的大作中提到】
: first, to compute N^M, (using binary recursive or DP for each N, then
: optimize it by utilizing sparsity of prime number both in space and time
: complexity over all N).
: Then just N-way merge, I don't see the need of a heap. Just do linear scan
: of each array.
: Any Better Idea?
| f*******4
发帖数: 1401 | 6 N是会变化的 就是说随时有可能有更大的N加入进来
linear scan也可以 但是每次都得和(N+1)^2判断大小 看是否有新的N加入
也可以构造一个winner tree减少scan时间至log(N)
scan
【在 c****m 的大作中提到】
: first, to compute N^M, (using binary recursive or DP for each N, then
: optimize it by utilizing sparsity of prime number both in space and time
: complexity over all N).
: Then just N-way merge, I don't see the need of a heap. Just do linear scan
: of each array.
: Any Better Idea?
| q**r
发帖数: 611 | | k***s
发帖数: 277 | 8 think about the infinite matrix
2^1 3^1 4^1 5^1
2^2 3^2 4^2 5^2
2^3 3^3 ...
then you can find a traverse routing from 2^1 in increasing order.
for each row, store the header
all headers are put into a min heap (# of headers depends on how long the
sequence)
each time to get min element in min heap, add the next element in same row
to heap.
space O(n), time O(nlog(n))
of
【在 d***8 的大作中提到】
: write a program, to generate a seris of numbers which are N to the power of
: M, where N and M are integer that greater than 1.
: The seris of the number should be in increasing order.
: i.e.,
: we have 2^2, 2^3, 2^4, ...
: and 3^2, 3^3, 3^4, ...
: and 4^2, 4^3, 4^4, ..., etc.
: so the number should be generated in this order:
: 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, ......
: How to write the program to do this???
| i**********e
发帖数: 1145 | 9 Something to add.
>> Build a heap of N elements, ...
Please note that the N is a variable, not a constant. The N would grow as
more elements are being printed.
For example, to print the first element, N = 2, and you must insert 2^2 and
3^2 into the heap.
ExtractMin() would get you 2^2 as the first element to print. Then, you must
insert 2^3 to the heap next. There are now 2 elements in the heap, so N = 2
. ExtractMin() again and you get 2^3. Insert 2^4 to the heap. N is still 2.
ExtractMin() again and get 3^2. Now, you would need to insert both 3^3 and 4
^2. Now the heap size is N = 3. You get the pattern.
To prove the lower bound complexity of this, you would need more math. You
would have to calculate to print a total of M elements, what is the largest
N? Assume that N = O(f(M)), then the run time complexity (not necessarily a
tight bound, just an upper bound) = O(f(M) lg N).
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 B********n 的大作中提到】
: N-way merge. Build a heap of N elements, then keep doing extract(min) and
: insertion. Complexity is O(Log(N) * N * M)
:
: of
| d****2
发帖数: 12 | 10 Even though N is unbounded, M is bounded. So build a heap of M elements,
initially with 2^2 ... M^2. If GetMin returns i^j where 2<=i<=M, you just
add i^(j+1) and heapfy. | | | s*********l
发帖数: 103 | 11 prime factorization, check the multiplicity of each prime factor,
see if there is only one prime factor with multiplicity > 1 or
these multiplicities have a common factor > 1.
of
【在 d***8 的大作中提到】
: write a program, to generate a seris of numbers which are N to the power of
: M, where N and M are integer that greater than 1.
: The seris of the number should be in increasing order.
: i.e.,
: we have 2^2, 2^3, 2^4, ...
: and 3^2, 3^3, 3^4, ...
: and 4^2, 4^3, 4^4, ..., etc.
: so the number should be generated in this order:
: 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, ......
: How to write the program to do this???
| l*****a
发帖数: 559 | 12 prime factorization is np complete.
【在 s*********l 的大作中提到】
: prime factorization, check the multiplicity of each prime factor,
: see if there is only one prime factor with multiplicity > 1 or
: these multiplicities have a common factor > 1.
:
: of
| b*****o
发帖数: 715 | 13 贴一个基于heap的代码吧：
///////////////////////////////////////////////
void swap(int & a, int &b)
{
int temp = a;
a = b;
b = temp;
}
void min_heapify(int *a, int *b,int n, int i)
{
while(i<=n/2)
{
int l = 2*i+1;
int r = 2*i+2;
int smallest=i;
if((l
smallest = l;
if ((r
smallest = r;
if(smallest == i)
break;
else
{
swap(a[i],a[smallest]);
swap(b[i],b[smallest]);
i = smallest;
}
}
}
void NPowerM(int n)
{
int *a = new int[n];
int *b = new int[n];
for(int i=0;i
{
a[i]=(i+2)*(i+2);
b[i] = i+2;
}
int count=0;
int prev = 0;
while(count<=n)
{
if (a[0]!=prev)
{
count++;
prev = a[0];
std::cout<
}
a[0] = a[0]*b[0];
min_heapify(a,b,n,0);
}
delete []a;
delete []b;
} | E*****7
发帖数: 128 | 14 Try this one in C++.
(1) Compute N to the power of M;
(2) Insert each of the generated result to std::map as the key of the key-value pair. std::map sorts the key exactly as required by the interview question when each key-value pair is inserted into it. In my code, the "value" is just a placeholder.
#include
#include | i**9
发帖数: 351 | 15 this is a problem quite similar to "Ugly Numbers"
http://www.algorithmist.com/index.php/UVa_136
there is a O(n) solution for Ugly Numbers, so this one can be solved in
O(n).
solution to "Ugly Numbers":
http://pastie.org/1236070 |
|
