a very difficult interview question - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

a very difficult interview question

a very difficult interview question# JobHunting - 待字闺中

d*82011-01-21 08:01

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*n2011-01-21 08:01

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*82011-01-21 08:01

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*m2011-01-21 08:01

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*82011-01-21 08:01

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*42011-01-21 08:01

6 楼

N是会变化的就是说随时有可能有更大的N加入进来
linear scan也可以但是每次都得和(N+1)^2判断大小看是否有新的N加入
也可以构造一个winner tree减少scan时间至log(N)

scan

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

q*r2011-01-21 08:01

7 楼

不懂ls们说的，直接2层for循环不行吗？

k*s2011-01-21 08:01

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 的大作中提到】

i*e2011-01-21 08:01

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*22011-01-21 08:01

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*l2011-01-21 08:01

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 的大作中提到】

l*a2011-01-21 08:01

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*o2011-01-21 08:01

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((lsmallest = l;
if ((rsmallest = 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*72011-01-21 08:01

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
std::map SeriesNumber;
static unsigned value = 1;
void NtoM(unsigned n, unsigned m)
{
unsigned result = n;
for (unsigned i = 0; i < m - 1; i++)
{
result = result * n;
SeriesNumber[result] = value++;
}
}
void printOut(std::map& m)
{
std::map::const_iterator it;
for (it = m.begin(); it != m.end(); ++it)
{
std::cout << (*it).first << "," ;
}
std::cout << std::endl;
}
int main()
{
for (unsigned p = 2; p <= 10; ++p)
{
NtoM(p, 4);
}
printOut(SeriesNumber);
return 0;
}
// Looking for a C++ job in New York Area. If you can help, please contact me at robertlzw AT yahoo.com
BTW: Does anybody here know the HTML tag for posting source code on mitbbs? My posted code format above is really ugly!

i*92011-01-21 08:01

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