Islamorada归来，奔些花花草草 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>gardening - 拈花惹草

Islamorada归来，奔些花花草草

Islamorada归来，奔些花花草草# gardening - 拈花惹草

r*g2014-01-21 08:01

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?
谢了

z*e2014-01-21 08:01

2 楼

昨天LD在Florida Keys中的Islamorada有个拍照的任务。因为正好放假，所以我也借光
跟着来到风光旖旎的小岛上，帮帮忙什么的。在忙碌之余，偷闲用手机拍了几张棚子里
的花花草草。虽说都是就地取材的植物，那浓浓的热带风情还真是让人瞬间就感受到了
阳光沙滩和温暖的海风呢～
发芽的椰子
换个角度
life style photography利器，香蕉串和菠萝头～
还有一种不认识的花花，谁帮认认？
换个角度

c*p2014-01-21 08:01

3 楼

第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

m*f2014-01-21 08:01

4 楼

噢噢，我在costco看到过这种花，不知道什么名字呢，好特别啊～～

r*g2014-01-21 08:01

5 楼

那这个题就是考察不引用额外空间没有向上指针情况下如何颠倒一个linked list?

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

: 第1题
: 当选定某一个结点n后，
: parent(n)和children(n)都成为n的子结点。
: 对应地，n->parent(n)->parent(parent(n))->...->root这一路径上所有的父子关系全
: 部逆转，
: 其他关系不变。
:
: you
: will

c*92014-01-21 08:01

6 楼

长见识了，那个菠萝头好大！谢谢！

c*p2014-01-21 08:01

7 楼

reverse a single linked list

【在 r*******g 的大作中提到】

: 那这个题就是考察不引用额外空间没有向上指针情况下如何颠倒一个linked list?

y*22014-01-21 08:01

8 楼

不知名的花花很大气，喜欢！

g*y2014-01-21 08:01

9 楼

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

h*e2014-01-21 08:01

10 楼

漂亮
那个大花应该是king protea

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

: 昨天LD在Florida Keys中的Islamorada有个拍照的任务。因为正好放假，所以我也借光
: 跟着来到风光旖旎的小岛上，帮帮忙什么的。在忙碌之余，偷闲用手机拍了几张棚子里
: 的花花草草。虽说都是就地取材的植物，那浓浓的热带风情还真是让人瞬间就感受到了
: 阳光沙滩和温暖的海风呢～
: 发芽的椰子
: 换个角度
: life style photography利器，香蕉串和菠萝头～
: 还有一种不认识的花花，谁帮认认？
: 换个角度

r*g2014-01-21 08:01

11 楼

第二题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

L*a2014-01-21 08:01

12 楼

第一次见椰子发芽，好挺拔好有气场。

S*I2014-01-21 08:01

13 楼

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里面。

z*e2014-01-21 08:01

14 楼

我也是第一次看到。觉得还挺好看的~

【在 L******a 的大作中提到】

: 第一次见椰子发芽，好挺拔好有气场。

g*y2014-01-21 08:01

15 楼

这种题硬盘空间不用考虑。内存放不下，你还能怎么办？
那个set是min heap。如果还有不明白的，参考topcoder的tutorial:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=

【在 r*******g 的大作中提到】

z*e2014-01-21 08:01

16 楼

图像搜索了一下，好像的确是！版版威武！

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

: 漂亮
: 那个大花应该是king protea

S*I2014-01-21 08:01

17 楼

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=

z*e2014-01-21 08:01

18 楼

哈哈，谢谢~花真的挺大个儿的~

【在 y****2 的大作中提到】

: 不知名的花花很大气，喜欢！

d*d2014-01-21 08:01

19 楼

这题比这个要麻烦得多了.
首先得把从root到这个node的path找出来.
然后reverse这个path.
这个过程,又和这个树的表示形式相关.
coding很麻烦的.
就算是个binary tree,半个小时内无错coding都很有难度.

【在 r*******g 的大作中提到】

: 那这个题就是考察不引用额外空间没有向上指针情况下如何颠倒一个linked list?

z*e2014-01-21 08:01

20 楼

我猜这花 shelf life挺长的。因为她根本没啥水分的样子~

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

: 噢噢，我在costco看到过这种花，不知道什么名字呢，好特别啊～～

r*g2014-01-21 08:01

21 楼

这个题最难弄的地方是，从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?

z*e2014-01-21 08:01

22 楼

哈哈，菠萝头是够大的。估计菠萝本身已经不好吃了，养分都被惜光了~

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

: 长见识了，那个菠萝头好大！谢谢！

d*d2014-01-21 08:01

23 楼

这题书上不是给了答案么?书上答案挺好的啊.那用得上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

T*m2014-01-21 08:01

24 楼

出一次远门，就这么几张照片？

r*g2014-01-21 08:01

25 楼

我们可以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都很有难度.

z*e2014-01-21 08:01

26 楼

一个多小时就到的地方也算远门。。

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

: 出一次远门，就这么几张照片？

S*I2014-01-21 08:01

27 楼

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

l*12014-01-21 08:01

28 楼

随手拍的都那么好看！椰子苗好清秀挺拔，花也很美，都是没有见过的。谢谢分享！

r*g2014-01-21 08:01

29 楼

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

y*82014-01-21 08:01

30 楼

好漂亮啊！椰子苗真美，种地上就可以变成一棵椰子树？

g*y2014-01-21 08:01

31 楼

Find kth p,q,r's composition number (assume ppublic long find(int p, int q, int r, int k) {
PriorityQueue pq = new PriorityQueue();
long t = p;
pq.add(t);
for (int i=0; it = 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);
}

z*e2014-01-21 08:01

32 楼

谢谢游子姐姐夸奖！
我去继续努力滴~

【在 l*****1 的大作中提到】

: 随手拍的都那么好看！椰子苗好清秀挺拔，花也很美，都是没有见过的。谢谢分享！

g*y2014-01-21 08:01

33 楼

哪本书上的答案？能贴一下吗？不需要经典Dijkstra的code, 几行就行，但是思路是一
样的，本质就是贪心。

【在 d*******d 的大作中提到】

: 这题书上不是给了答案么?书上答案挺好的啊.那用得上dijkstra啊.
:
: 到B
: 和B

z*e2014-01-21 08:01

34 楼

我也是第一次见到椰子苗，真的挺惊艳的！说起来，我家院子里最近也出了个这样长相
的苗，我待会儿看看去~

【在 y*****8 的大作中提到】

: 好漂亮啊！椰子苗真美，种地上就可以变成一棵椰子树？

d*d2014-01-21 08:01

35 楼

好,写点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, 几行就行，但是思路是一
: 样的，本质就是贪心。

m*62014-01-21 08:01

36 楼

进来是想看私货的，难道这次没有让男神给你拍几张？

s*c2014-01-21 08:01

37 楼

第二题:
对list1生成一个摘要(比如一个hashtable或者一个bloom filter)
然后在enumerate list2中的每个元素, 检查其是否hit那个摘要, 并记录所有结果为
positive的元素,存入list2'
然后对于list2' 的元素再做一遍摘要来筛一遍list1 得到list1'
这时list1'和list2'的元素已经很相近了,再来分别sort一下,然后来找.
对于巨大的文件, 上述两个筛数的过程可以用mapreduce来完成.

you
will
in
l*
amotized

【在 r*******g 的大作中提到】

T*m2014-01-21 08:01

38 楼

在美国，超过50英里就算是楚远门了，呵呵。

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

: 一个多小时就到的地方也算远门。。

g*y2014-01-21 08:01

39 楼

谢谢，这个效率很好。

【在 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();