Weighted Graph Challenge 一道面试题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Programming - 葵花宝典

Weighted Graph Challenge 一道面试题

Weighted Graph Challenge 一道面试题# Programming - 葵花宝典

k*a2016-12-20 08:12

1 楼

【以下文字转载自 WaterWorld 讨论区】
发信人: kayaka (jimm), 信区: WaterWorld
标题: 有三个版的人特爱装逼
发信站: BBS 未名空间站 (Fri Nov 11 10:07:52 2011, 美东)
Faculty
EB1
Biology
这三个版灌水的基本都同一拨人。

b*u2016-12-20 08:12

2 楼

这电影明显是给影迷怀旧来拍的，这完全是我想看到的。宏大的场景，优美的地貌，久
远神秘的建筑。甚至剧情节奏都基本模仿指一。甘多夫带着矮人往外突时我自觉在脑子
里播放卡扎克之桥的配乐。最后点化下主题cheesy的升华一下霍比人特有的勇气正义和
爱，让人感觉这片百分百是正宗的指环王世界，就比什么都重要。
虽然是模仿指一，可各方面和指一都有明显差距的。像缺少震撼的开场，人物单一，大
段时间安排bilbo和golumn猜谜语。。而且嬉皮笑脸的棕巫师和电影风格很不搭。但这
都是为了忠实原著。霍比人是不折不扣的儿童文学。其实指环王本来该写成一样的续集
，可托尔金写上瘾了不小心写成了鸿篇巨作，差点吃出版商官司。peter jackson在忠
于原著和电影的原则下搞出这个，实属不易。
最后大赞一下48帧。清晰好多。以现在的技术真应该变成电影业标准了。区别真的有玩
游戏时24帧和48帧的差距。

l*i2016-12-20 08:12

3 楼

我没帮成那个山东大妈的忙，感觉挺遗憾的，我就继续往北开，就开始收过桥费了，挺
讨厌的。
我不喜欢开地道，路太窄，我怕撞墙壁上。
在巴尔的摩的港口下来吃饭，看见好多海鸟。海鸥比鸽子厉害，还有一种白色的鸟，体
型是最小，但是最厉害，敢啄海鸥,鸽子更不在话下。把其他的鸟都赶开，自己吃游客
扔过来的面包
路上碰见黑人大哥，双手高举着喊：I am a good man. I am hungry。向我要钱。我
掏出钱包，给了他一个5块的，可他探头一看，看见我钱包里有10块的，就问我说：Mam
, can I have that ten?
我一猥琐，就说No,心想10块我就心疼了。那个黑人大哥听我说No 以后，神色很尴尬，
就乖乖的拿着5块钱走了，我后来感觉挺对不起他的。
我要走两个block去取车，在路上被一个黑人大妈，莫名其妙的踹了一脚，非常的郁闷。
到了纽约，在离唐人街很劲的地方住下，晚上出去，在一个街口，也碰见一个要钱的，
手里还挥舞着一把大刀。我就给他钱了。
第二天，我又出去了，在一个不同的街口，又碰见他，又挥舞着刀向我要钱，我凑上去
，说，你仔细看看，你记得我吗，你昨天刚向我要过的

c*52016-12-20 08:12

4 楼

曾经上大学的时候，宿舍有规定不让用一些功率大的用电器，比如“热得快”，还有“
电饭锅”等等，更不能用明火，甚至连蜡烛都不允许，其实都是些安全防范，只不过大
学生在宿舍里哪能受得了不做饭呢，最起码要煮个方便面吧。
我们宿舍是6个女生，经常偷着做饭，其实每个宿舍都有这样的，一个人在那里煮东西
，方便面或者是火锅麻辣烫之类的，一个人在门口放风，看到宿管阿姨来了，立马进来
通风报信，然后全宿舍的都赶紧想办法度过此劫难。
有一次超级搞笑，一个姐们儿在给我们煮方便面，另一个是在放风，结果宿管阿姨一下
子上来3个，立马进来通风报信，我们赶紧把电饭锅藏到阳台上（当时我们住的是豪华
型的宿舍，还有阳台呢，哈哈），然后把厚棉被盖在锅上，再放些衣服在棉被上。
但是满屋子的方便面的味道是掩盖不了的，宿管阿姨进来之后说，吃方便面呢啊？
我们赶紧说，是啊是啊，刚才泡了个方便面，刚吃完。
阿姨在屋子里来回仔细的看了看，还到了阳台上，我们很紧张的，不过好在阿姨没有掀
开被子，就走了。
要知道，我们为了掩盖彻底，把内衣都放被子上了。

s*e2016-12-20 08:12

5 楼

This is a simplified version of a real problem we encountered.
Your solutions will preferably be implemented in Go. We'll also consider
solutions implemented in Python (or other languages on request), but since
Go can be learned in approximately a day, we really do prefer a solution
written in Go.
We're building a directed graph.
The graph consists of Nodes connected by Edges.
Each Node has an ID (int64).
Each Node keeps track of its outgoing Edges (list of ids).
There might be thousands of outgoing Edges.
Each outgoing Edge also has an edge weight (float64).
The Node needs to maintain a sorted list of its outgoing Edges.
Operations are triggered on Nodes that might change edge weights.
Some Operations might update one edge weight, others many.
For the purposes of this exercise, the operation is a function that (
randomly) changes a few edge weights.
The sorted list needs to efficiently stay sorted even as many weights are
changed.
For the purposes of this exercise it's initially enough to focus on one Node
and its outgoing Edges (to Node IDs that don't need an instantiated Node)
Multiple edges can have the same weight.
We recommend to build on top of https://github.com/google/btree/ but are
interested to hear if you have a different take.
目前发现有另外一个解法,比如做双向链表,好像跟btree一样可以做到log(n),不想误导
大家,过几天更新和大家探讨
这个问题应该是可以partition然后计算的,甚至可以request来了以后,直接随机发到任
意server上然后用chord做peer-to-peer通讯最后到达request应该被送到的server上,
跳过master-slave这个model的
Go其实最适合拿来怎么用呢?有什么具体例子么?哪里会容易找这样的工作?

S*r2016-12-20 08:12

6 楼

喷～

s*j2016-12-20 08:12

7 楼

报纸上评论很差. 尤其那个48帧, 说看起来还不如以前BBC拍的mini series
需要去验证一下.

【在 b***u 的大作中提到】

: 这电影明显是给影迷怀旧来拍的，这完全是我想看到的。宏大的场景，优美的地貌，久
: 远神秘的建筑。甚至剧情节奏都基本模仿指一。甘多夫带着矮人往外突时我自觉在脑子
: 里播放卡扎克之桥的配乐。最后点化下主题cheesy的升华一下霍比人特有的勇气正义和
: 爱，让人感觉这片百分百是正宗的指环王世界，就比什么都重要。
: 虽然是模仿指一，可各方面和指一都有明显差距的。像缺少震撼的开场，人物单一，大
: 段时间安排bilbo和golumn猜谜语。。而且嬉皮笑脸的棕巫师和电影风格很不搭。但这
: 都是为了忠实原著。霍比人是不折不扣的儿童文学。其实指环王本来该写成一样的续集
: ，可托尔金写上瘾了不小心写成了鸿篇巨作，差点吃出版商官司。peter jackson在忠
: 于原著和电影的原则下搞出这个，实属不易。
: 最后大赞一下48帧。清晰好多。以现在的技术真应该变成电影业标准了。区别真的有玩

j*y2016-12-20 08:12

8 楼

彼此彼此

w*g2016-12-20 08:12

9 楼

btree是磁盘数据结构，如果是内存操作，就是overengineer了，不如红黑树。数据结
构问题貌似和服务器架构没啥关系。

solution

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

: This is a simplified version of a real problem we encountered.
: Your solutions will preferably be implemented in Go. We'll also consider
: solutions implemented in Python (or other languages on request), but since
: Go can be learned in approximately a day, we really do prefer a solution
: written in Go.
: We're building a directed graph.
: The graph consists of Nodes connected by Edges.
: Each Node has an ID (int64).
: Each Node keeps track of its outgoing Edges (list of ids).
: There might be thousands of outgoing Edges.

y*n2016-12-20 08:12

10 楼

错了吧，如果说三个版的话，应该是
postdoc
EB1
biology
---- 中国人都生物的能做到faculty的很少，倒是其他专业的多些

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

: 【以下文字转载自 WaterWorld 讨论区】
: 发信人: kayaka (jimm), 信区: WaterWorld
: 标题: 有三个版的人特爱装逼
: 发信站: BBS 未名空间站 (Fri Nov 11 10:07:52 2011, 美东)
: Faculty
: EB1
: Biology
: 这三个版灌水的基本都同一拨人。

b*u2016-12-20 08:12

11 楼

48帧的坏评都是说看起来不像电影，像高清电视什么的。这正是因为电影的24帧太tm落
后了。
"The Hobbit in the 48 format resembles an incredibly high-definition
simulcast of “The Metropolitan Opera Live from Middle-earth." – Chicago
Tribune
Exactly my experience.

【在 s*****j 的大作中提到】

: 报纸上评论很差. 尤其那个48帧, 说看起来还不如以前BBC拍的mini series
: 需要去验证一下.

s*e2016-12-20 08:12

12 楼

可能这个题目的作者也没有想清楚,好像只要选一个BST就可以了?
doubly linked list能做到 initialize是nlogn(排序),剩下CRUD都是log n因为doubly
linked list可以binary search
关于架构,这个只是考虑到如果是maintain多个node(原题说只考虑一个node,one-to-
many),因为node之间的out-going edges是独立的,所以可以每个node都独立maintain一
个红黑树或者doubly linked list,只有删除node的时候需要互相通讯一下.

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

: btree是磁盘数据结构，如果是内存操作，就是overengineer了，不如红黑树。数据结
: 构问题貌似和服务器架构没啥关系。
:
: solution

n*o2016-12-20 08:12

13 楼

你把军版漏了
军版一群小将拿绿卡爱党爱国，站在道德制高点上装逼

z*a2016-12-20 08:12

14 楼

补充一论据，这帮什么博士博后确实大部分人都很垃圾
因为我家里有人是在医科学院工作，所以了解到好多生物或医学专业的博士博后利用院
里提供的公派出国机会到了美国，同时拿着公派奖学金和美国老板的工资，然后就逾
期不留，打死也不回去，最后国内的学院只能做除名的处理，损失了多年投入的心血和
资金。
结果现在这帮EB1还舔着脸说他们是精英人才，我看是忘恩负义不知羞耻的垃圾人渣，
他们能提出这样的投诉信倒也合理，很符合他们一贯的萎缩风格。

i*o2016-12-20 08:12

15 楼

一群loser自己都不愿意闻自己拉出来的东西的家伙，然后拿这些shi去骗eb1。自以为
是，而且不愿意别人说出事实，大概因此eb1 删我的帖子吧。
那个谁的英文是真心烂。

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

k*a2016-12-20 08:12

16 楼

嘿嘿，话不要说那么白嘛。

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

: 补充一论据，这帮什么博士博后确实大部分人都很垃圾
: 因为我家里有人是在医科学院工作，所以了解到好多生物或医学专业的博士博后利用院
: 里提供的公派出国机会到了美国，同时拿着公派奖学金和美国老板的工资，然后就逾
: 期不留，打死也不回去，最后国内的学院只能做除名的处理，损失了多年投入的心血和
: 资金。
: 结果现在这帮EB1还舔着脸说他们是精英人才，我看是忘恩负义不知羞耻的垃圾人渣，
: 他们能提出这样的投诉信倒也合理，很符合他们一贯的萎缩风格。

y*n2016-12-20 08:12

17 楼

生物是试验科学（靠，到底是不是科学我现在也不确定了），有试验有数据就可以发文
章，这比其他专业来的要容易的多。这就造成国内的土博过来实验室里混几年就办EB1
了，其实很多人在社会上的生存能力很差，拿了绿卡还是混实验室。

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

k*a2016-12-20 08:12

18 楼

生物量大，能做到faculty的绝对数量不少。

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

: 错了吧，如果说三个版的话，应该是
: postdoc
: EB1
: biology
: ---- 中国人都生物的能做到faculty的很少，倒是其他专业的多些