r*******g
发帖数: 1335 | 1 1，Given a n-ary tree. A random leaf node will be selected.Imagine that you
are now holding the tree with your hand from that node. All other nodes will
now fall under gravity. Write a function to perform this transformation.
n-ary tree又不是bst，这题什么意思，怎么也无法想象把一个节点提起来是什么感觉
2，Given two lists, each containing numbers, how would you find the
intersection of these two lists? What if these two lists are read from a
huge file that cannot fit in memory?
如果文件很大该怎么办，我能想到的是尝试一个number对应一位，但是如果memory实在
有限，number的range很大，那也没有办法。
3，Given 3 prime numbers and an integer k, find the kth number if all the
nos which are having these 3 prime numbers as their factors are arranged in
increasing order.
Eg. prime numbers - 2,3,5
The increasing sequence will be 2,3,4,5,6,8,9...
这个题我在careerup上看到两次了，都没看到好的解法，我能想到的是，当你走到2^l*
3^m*5^n时，下一个数一定是通过2^l*3^m*5^(n-1)之后的数变化得到，这样就抛弃了很
多数，假设紧接2^l*3^m*5^(n-1)的数是M，那么下一个数就在2^l*3^m*5^n和M*5之间，
这个范围有可能很大，挨个做质因数分解似乎不大对。似乎这个题只能尽量使amotized
时间尽量小？any link on this?
谢了 |
c****p
发帖数: 6474 | 2 第1题
当选定某一个结点n后，
parent(n)和children(n)都成为n的子结点。
对应地，n->parent(n)->parent(parent(n))->...->root这一路径上所有的父子关系全
部逆转，
其他关系不变。
you
will
【在 r*******g 的大作中提到】
: 1，Given a n-ary tree. A random leaf node will be selected.Imagine that you
: are now holding the tree with your hand from that node. All other nodes will
: now fall under gravity. Write a function to perform this transformation.
: n-ary tree又不是bst，这题什么意思，怎么也无法想象把一个节点提起来是什么感觉
: 2，Given two lists, each containing numbers, how would you find the
: intersection of these two lists? What if these two lists are read from a
: huge file that cannot fit in memory?
: 如果文件很大该怎么办，我能想到的是尝试一个number对应一位，但是如果memory实在
: 有限，number的range很大，那也没有办法。
: 3，Given 3 prime numbers and an integer k, find the kth number if all the
|
r*******g
发帖数: 1335 | 3 那这个题就是考察不引用额外空间没有向上指针情况下如何颠倒一个linked list?
【在 c****p 的大作中提到】
: 第1题
: 当选定某一个结点n后，
: parent(n)和children(n)都成为n的子结点。
: 对应地，n->parent(n)->parent(parent(n))->...->root这一路径上所有的父子关系全
: 部逆转，
: 其他关系不变。
:
: you
: will
|
c****p
发帖数: 6474 | 4 reverse a single linked list
【在 r*******g 的大作中提到】
: 那这个题就是考察不引用额外空间没有向上指针情况下如何颠倒一个linked list?
|
g**********y
发帖数: 14569 | 5 2. 先merge sort file, 然后merge intersection.
3. 这是个Dijkstra算法的变形，从set = {2^0*3^0*5^0 = 1}出发，每次取最小的数，
然后把该数的2*a, 3*a, 5*a放进set里(需要一个visited[][][]来记录避免重复), 然
后再取最小的重复以上步骤，直到k步。
you
will
【在 r*******g 的大作中提到】
: 1，Given a n-ary tree. A random leaf node will be selected.Imagine that you
: are now holding the tree with your hand from that node. All other nodes will
: now fall under gravity. Write a function to perform this transformation.
: n-ary tree又不是bst，这题什么意思，怎么也无法想象把一个节点提起来是什么感觉
: 2，Given two lists, each containing numbers, how would you find the
: intersection of these two lists? What if these two lists are read from a
: huge file that cannot fit in memory?
: 如果文件很大该怎么办，我能想到的是尝试一个number对应一位，但是如果memory实在
: 有限，number的range很大，那也没有办法。
: 3，Given 3 prime numbers and an integer k, find the kth number if all the
|
r*******g
发帖数: 1335 | 6 第二题merge sort的话岂不是很耗费硬盘空间
第三题我很好奇的是如何每次取最小的数，你说的dijkstra不是最短路径算法么，貌似
你说的是一次explor很多数，然后选最小一个，这样平坦下来开销小？explor的数还可
以放到heap里面。
【在 g**********y 的大作中提到】
: 2. 先merge sort file, 然后merge intersection.
: 3. 这是个Dijkstra算法的变形，从set = {2^0*3^0*5^0 = 1}出发，每次取最小的数，
: 然后把该数的2*a, 3*a, 5*a放进set里(需要一个visited[][][]来记录避免重复), 然
: 后再取最小的重复以上步骤，直到k步。
:
: you
: will
|
S**I
发帖数: 15689 | 7 a brute force solution to the third problem:
1. Let n = 0, m = 1;
2. Find all permutations of i, j and k such that i+j+k = m. Compute product
of 2^i * 3^j * 5^k of each permutation, put all the products in a set S.
3. Suppose the number of permutations found in the previous step is p (it
can be shown that p = (m+1)*(m+2)/2); then m++, n += p.
4. If k > n, go back to step 2; otherwise, the kth number in set S is the
solution.
【在 r*******g 的大作中提到】
: 第二题merge sort的话岂不是很耗费硬盘空间
: 第三题我很好奇的是如何每次取最小的数，你说的dijkstra不是最短路径算法么，貌似
: 你说的是一次explor很多数，然后选最小一个，这样平坦下来开销小？explor的数还可
: 以放到heap里面。
|
g**********y
发帖数: 14569 | 8
这种题硬盘空间不用考虑。内存放不下，你还能怎么办？
那个set是min heap。如果还有不明白的，参考topcoder的tutorial:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
【在 r*******g 的大作中提到】
: 第二题merge sort的话岂不是很耗费硬盘空间
: 第三题我很好奇的是如何每次取最小的数，你说的dijkstra不是最短路径算法么，貌似
: 你说的是一次explor很多数，然后选最小一个，这样平坦下来开销小？explor的数还可
: 以放到heap里面。
|
S**I
发帖数: 15689 | 9 In Dijkstra all the neighbors of a current node are known, but in this problem they are
unknown, so how do you find the smallest neighbor?
【在 g**********y 的大作中提到】
:
: 这种题硬盘空间不用考虑。内存放不下，你还能怎么办？
: 那个set是min heap。如果还有不明白的，参考topcoder的tutorial:
: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
|
d*******d
发帖数: 2050 | 10 这题比这个要麻烦得多了.
首先得把从root到这个node的path找出来.
然后reverse这个path.
这个过程,又和这个树的表示形式相关.
coding很麻烦的.
就算是个binary tree,半个小时内无错coding都很有难度.
【在 r*******g 的大作中提到】
: 那这个题就是考察不引用额外空间没有向上指针情况下如何颠倒一个linked list?
|
|
|
r*******g
发帖数: 1335 | 11 这个题最难弄的地方是，从2^l*3^m*5^n到2^(l+1)*3^(m+1)*5^(n+1)之间有很多数，有
的数其指数可能不是在l和l+1之间。所以，即使把很多数放入heap，也需要考虑清楚到
底哪些放入heap。
我能想到的就是我第一个帖子说的，每次对前面一段数做变化，假设目前这段是从A到B
，对每个数乘以2或者3或者5，如果超过了B，就把变化后的数放进heap。注意这个A和B
是变化的，我在第一个帖子说了的。
这样做的话，一次会存入很多数进入heap，每次B向后一定一个数，A也向后移动。
problem they are
【在 S**I 的大作中提到】
: In Dijkstra all the neighbors of a current node are known, but in this problem they are
: unknown, so how do you find the smallest neighbor?
|
d*******d
发帖数: 2050 | 12 这题书上不是给了答案么?书上答案挺好的啊.那用得上dijkstra啊.
到B
和B
【在 r*******g 的大作中提到】
: 这个题最难弄的地方是，从2^l*3^m*5^n到2^(l+1)*3^(m+1)*5^(n+1)之间有很多数，有
: 的数其指数可能不是在l和l+1之间。所以，即使把很多数放入heap，也需要考虑清楚到
: 底哪些放入heap。
: 我能想到的就是我第一个帖子说的，每次对前面一段数做变化，假设目前这段是从A到B
: ，对每个数乘以2或者3或者5，如果超过了B，就把变化后的数放进heap。注意这个A和B
: 是变化的，我在第一个帖子说了的。
: 这样做的话，一次会存入很多数进入heap，每次B向后一定一个数，A也向后移动。
:
: problem they are
|
r*******g
发帖数: 1335 | 13 我们可以recursion，
Move(Node * currentnode, bool & path_contain_node, Node * & final_root){
如果下面传上来的path_contain_node是true，那就颠倒顺序，否则的话维持不变。
关键就是走到了新的root怎么办
}
【在 d*******d 的大作中提到】
: 这题比这个要麻烦得多了.
: 首先得把从root到这个node的path找出来.
: 然后reverse这个path.
: 这个过程,又和这个树的表示形式相关.
: coding很麻烦的.
: 就算是个binary tree,半个小时内无错coding都很有难度.
|
S**I
发帖数: 15689 | 14 I think this solution is no better than brute force. :) Brute force is not bad for this problem, it is approximately linear with k.
到B
和B
【在 r*******g 的大作中提到】
: 这个题最难弄的地方是，从2^l*3^m*5^n到2^(l+1)*3^(m+1)*5^(n+1)之间有很多数，有
: 的数其指数可能不是在l和l+1之间。所以，即使把很多数放入heap，也需要考虑清楚到
: 底哪些放入heap。
: 我能想到的就是我第一个帖子说的，每次对前面一段数做变化，假设目前这段是从A到B
: ，对每个数乘以2或者3或者5，如果超过了B，就把变化后的数放进heap。注意这个A和B
: 是变化的，我在第一个帖子说了的。
: 这样做的话，一次会存入很多数进入heap，每次B向后一定一个数，A也向后移动。
:
: problem they are
|
r*******g
发帖数: 1335 | 15 I got it from cracking code interview. It is already in book.....
bad for this problem, it is approximately linear with k.
【在 S**I 的大作中提到】
: I think this solution is no better than brute force. :) Brute force is not bad for this problem, it is approximately linear with k.
:
: 到B
: 和B
|
g**********y
发帖数: 14569 | 16 Find kth p,q,r's composition number (assume p
public long find(int p, int q, int r, int k) {
PriorityQueue pq = new PriorityQueue();
long t = p;
pq.add(t);
for (int i=0; i
t = pq.remove();
add(pq, p*t);
add(pq, q*t);
add(pq, r*t);
}
return t;
}
private void add(PriorityQueue pq, long n) {
if (!pq.contains(n)) pq.add(n);
} |
g**********y
发帖数: 14569 | 17 哪本书上的答案？能贴一下吗？不需要经典Dijkstra的code, 几行就行，但是思路是一
样的，本质就是贪心。
【在 d*******d 的大作中提到】
: 这题书上不是给了答案么?书上答案挺好的啊.那用得上dijkstra啊.
:
: 到B
: 和B
|
d*******d
发帖数: 2050 | 18 好,写点code攒人品:
return 第k个.和原题要求稍微不一样一点.
int findkth(int p, int q, int r, int k){
queue q1, q2, q3;
q1.push(p);
q2.push(q);
q3.push(r);
int cur = p;
for(int i =1; i<=k; i++){
int h1 = q1.front();
int h2 = q2.front();
int h3 = q3.front();
int min = h1 < h2 ? h1 : h2;
min = min
cur = min;
if( min == h1){
q1.pop();
q1.push(cur*p);
q2.push(cur*q);
q3.push(cur*r);
}else if( min == h2){
q2.pop();
q2.push(cur*q);
q2.push(cur*r);
}else{
q3.pop();
q3.push(cur*r);
}
}
return cur;
}
【在 g**********y 的大作中提到】
: 哪本书上的答案？能贴一下吗？不需要经典Dijkstra的code, 几行就行，但是思路是一
: 样的，本质就是贪心。
|
s******c
发帖数: 1920 | 19 第二题:
对list1生成一个摘要(比如一个hashtable或者一个bloom filter)
然后在enumerate list2中的每个元素, 检查其是否hit那个摘要, 并记录所有结果为
positive的元素,存入list2'
然后对于list2' 的元素再做一遍摘要来筛一遍list1 得到list1'
这时list1'和list2'的元素已经很相近了,再来分别sort一下,然后来找.
对于巨大的文件, 上述两个筛数的过程可以用mapreduce来完成.
you
will
in
l*
amotized
【在 r*******g 的大作中提到】
: 1，Given a n-ary tree. A random leaf node will be selected.Imagine that you
: are now holding the tree with your hand from that node. All other nodes will
: now fall under gravity. Write a function to perform this transformation.
: n-ary tree又不是bst，这题什么意思，怎么也无法想象把一个节点提起来是什么感觉
: 2，Given two lists, each containing numbers, how would you find the
: intersection of these two lists? What if these two lists are read from a
: huge file that cannot fit in memory?
: 如果文件很大该怎么办，我能想到的是尝试一个number对应一位，但是如果memory实在
: 有限，number的range很大，那也没有办法。
: 3，Given 3 prime numbers and an integer k, find the kth number if all the
|
g**********y
发帖数: 14569 | 20 谢谢，这个效率很好。
【在 d*******d 的大作中提到】
: 好,写点code攒人品:
: return 第k个.和原题要求稍微不一样一点.
: int findkth(int p, int q, int r, int k){
: queue q1, q2, q3;
: q1.push(p);
: q2.push(q);
: q3.push(r);
: int cur = p;
: for(int i =1; i<=k; i++){
: int h1 = q1.front();
|
