l****i
发帖数: 230 | 1 多谢大家的bless，刚刚recruiter通知，Amazon决定给我offer了。看来攒人品太重要
了。
Amazon一般PhD毕业research scientist或SDE给多少钱啊？有知道的透露一下
现在手头还有6、7个onsite，决定拖一阵子再答复，有什么技巧吗？ 谢谢大家了，等
决定了offer散尽家财发包子。
另外，昨天面了MS，貌似也准备给offer了，等一下上面经。
================================================================
fresh PhD;面试research scientist position
1.Job talk一小时，audience七八个人，主要是interviewer
2.老印SDE，问了一些research的问题，然后coding，判断二叉树是不是BST，因为题目
都很简单答得比较顺利，老印SDE表示非常满意
3.老印director，lunch interview，瞎聊，问我“如果amazon要想在竞争者中脱颖而
出做得更好怎么办”我答“要hire top talents”，接着这个话题瞎聊了聊，还算开心
4.韩国MM研究员，research面试，总体满意
5.老印SDE；这个环节答的不好，不知道给了什么样的feedback
问题: 给一个选课的AOV网络(比如要选machine learning必须先修完Algorithm)，总计
n门课，每学期最多可以选k门课，找最快修完所有课的schedule
Follow up: 如果没门课只在给定的学期开设，怎么办？
这一面发挥不好，一个是题目比较生僻，另外，graph这块自己不是很熟，没有信心按
时写完程序。所以最后只写了一个拓扑排序的code，而且鬼使神差用了邻接矩阵做data
structure，导致只写出了O(n^3)的程序
6.两个白人SDE，主要是其中一个在面，另外一个自始至终没说话。
问题: 有一个大的catalog，总共有500Million个entry，每个entry内容是 （ID，
document），每个document大小约10KB，不同的ID对应的document可能相同，怎样设计
一个程序，对每个给定的一个ID，找出与该ID对应着相同的document的所有其他ID。
Follow Up: 如果每台机器内存只有1GB，硬盘100GB，怎么做
这是我第一次被面到大数据的问题，比较慌，关键不知道他们要考什么，所以瞎答一气
：开始考虑用hash table,document做Key，ID做value，conflicts时用链表(chaining)
，问题是hash function的计算可能开销比较大；后来乱说，是不是可以基于document
排序，他们好像没有反对，所以就答是不是可以把数据按segment load到每个机器的内
存，排序index，然后按tree的形式merge.
7. ABC manager,聊了聊research，聊得比较开心。
结束 | q***y
发帖数: 236 | | f*******t
发帖数: 7549 | | c*******r
发帖数: 610 | | t********3
发帖数: 567 | | p*****2
发帖数: 21240 | 6 最后一题三个hashtable？
hashcode->document
hashcode->IDs
ID->hashcode | p*****2
发帖数: 21240 | | l****i
发帖数: 230 | 8 不行啊，你要比较两个document，判断是不是内容相同
【在 p*****2 的大作中提到】
: 最后一题三个hashtable？
: hashcode->document
: hashcode->IDs
: ID->hashcode
| p*****2
发帖数: 21240 | 9
有一个想法就是用PriorityQueue代替普通Queue在Toposort算法里。用邻接的课程数来
排序。这样总是取最多邻接课程的课程来学习先。这样能优化，但是还要想一下是不是
能保证最优。O(nlogn)复杂度。
【在 p*****2 的大作中提到】
: 第五个有点麻烦。得想想。
| p*****2
发帖数: 21240 | 10
内容相同应该是相同的hashcode吧？
【在 l****i 的大作中提到】
: 不行啊，你要比较两个document，判断是不是内容相同
| | | l*m
发帖数: 1048 | 11 最后一题应该是考如何快速踢出不同的document，对于相同的ID，使用ramdom 方法比较
文档。不同就剔除，相同就继续找下一个random位置比较，再不行就只能从头到尾比较
了。
【在 p*****2 的大作中提到】
: 第五个有点麻烦。得想想。
| p*****2
发帖数: 21240 | 12
比较
没看明白。我题意理解错了吗？而且你说的是第六题吧？
【在 l*m 的大作中提到】
: 最后一题应该是考如何快速踢出不同的document，对于相同的ID，使用ramdom 方法比较
: 文档。不同就剔除，相同就继续找下一个random位置比较，再不行就只能从头到尾比较
: 了。
| l*m
发帖数: 1048 | 13 sorry，是第六题。
【在 p*****2 的大作中提到】
:
: 比较
: 没看明白。我题意理解错了吗？而且你说的是第六题吧？
| p*****2
发帖数: 21240 | 14
我想过了。应该能保证最优。晚上实现一下。
【在 p*****2 的大作中提到】
:
: 比较
: 没看明白。我题意理解错了吗？而且你说的是第六题吧？
| t********3
发帖数: 567 | 15 有道理 ，但是不是邻接课程数量的问题吧
比如这个图，课程A～H
A -> B
C -> D
B -> D
E->G
F->G
D->H
G->H
如果给每个课程一个weight，离最终课程H的距离，
A ＝ 3
B = C = 2
E = F = 2
D = G = 1
H = 0
应该从距离最大的开始修吧
还有，一个课程可不可以是多个课程的先修条件？
【在 p*****2 的大作中提到】
:
: 我想过了。应该能保证最优。晚上实现一下。
| p*****2
发帖数: 21240 | 16
还有，一个课程可不可以是多个课程的先修条件？
可以呀。所以我是用这个来排序的。
【在 t********3 的大作中提到】
: 有道理 ，但是不是邻接课程数量的问题吧
: 比如这个图，课程A～H
: A -> B
: C -> D
: B -> D
: E->G
: F->G
: D->H
: G->H
: 如果给每个课程一个weight，离最终课程H的距离，
| j*******l
发帖数: 19 | | p*****2
发帖数: 21240 | 18 我写了一下，用的greedy的算法。没想到反例，但是感觉也不容易证明。
from heapq import *
class Node:
def __init__(self, val):
self.val=val
self.In=set()
self.Out=set()
def __cmp__(self, other):
if len(self.Out)
return 1
elif len(self.Out)>len(other.Out):
return -1
else:
return 0
def __str__(self):
return self.val+":"+str(self.In)+":"+str(self.Out)
courses=[['D','A'],['D','B'],['E','B'],['F','A'],['F','C'],['H','B'],['I','A
'],['I','D']]
dict={}
for i in courses:
a=i[0]
b=i[1]
if not dict.has_key(a):
dict[a]=Node(a)
if not dict.has_key(b):
dict[b]=Node(b)
dict[a].In.add(b)
dict[b].Out.add(a)
hq=[]
for i in dict.keys():
if len(dict[i].In)==0:
heappush(hq,dict[i])
k=2 #2 courses each semester
sem=1
count=min(k,len(hq))
while len(hq)!=0:
n=heappop(hq)
print "semester"+str(sem)+":"+n.val
for i in n.Out:
dict[i].In.remove(n.val)
if len(dict[i].In)==0:
heappush(hq,dict[i])
count-=1
if count==0:
sem+=1
count=min(k,len(hq))
| l****i
发帖数: 230 | 19 二师兄你太牛了,膜拜
【在 p*****2 的大作中提到】
: 我写了一下，用的greedy的算法。没想到反例，但是感觉也不容易证明。
: from heapq import *
: class Node:
: def __init__(self, val):
: self.val=val
: self.In=set()
: self.Out=set()
: def __cmp__(self, other):
: if len(self.Out): return 1
| A******o
发帖数: 231 | 20 co-
【在 l****i 的大作中提到】
: 二师兄你太牛了,膜拜
| | | s*********5
发帖数: 514 | 21 关于课程排序，如果是这样的：
a1, a2 -> b1 （上b1之前，要先上a1, a2)
a3, a4 -> b2
a5, a6 -> b3
b1, b2, b3 -> c1
BUT a4, b3, ONLY available in semester 4 (S4)
然后每个学期只能上2节课，
(starting no incoming edge: a1, a2, a3, a4, a5, a6)
S1: a1, a2 (a3, a4, a5, a6, b1)
S2: a5, a6 (a3, a4, b1, b3)
S3: b1, a3 (a4, b3)
S4: a4, b3 (b2)
S5: b2
S6: c1
这样用什么算法？
我想的是先找出longest link, 就是找出需要最久才能完成的那个link, 然后reduce
its length, then update the length, and continue
这里的关键是如何计算longest link, 我认为每个课程（node)要有其在每个level（
level 3 means it can be finished at semester 3) 的prerequisite的个数，然后如
果只有指定semester available, 还要加入空转的level。 比如这个例子中，
c1: level 1: 5; level 2：1； level 3: 0; level 4:2; level 5:1; 根据以上信息
来计算自己的level (这里自己是level 6) | s*********5
发帖数: 514 | 22 How about this graph, with maximum classes of 2 for each semester:
a->b->c->d, e, f, g, h, i (6 semesters needed to finish all, but 4
semesters to finish any)
y,z->x->w->u->v (5 semesters needed to finish v)
The best strategy is to do this:
a, y
b, z
c, w
...
but you may do y, z first if you are greedy
Even if your have a smart algorithm, which gives you 6 on d,e, f,..., then
how about this:
a1->b1->c1->d1
a1,a2,a3->b2->c2
a2, a3->b3->c3
a2, a3->b4->c4
a1 has a max distance of 4
a2, a3 have max distances of 3
but we need to take a2, a3 here first | s*********5
发帖数: 514 | 23 这个是不是要先用SHA-2（better and stronger than MD5)把所有document搞出一个
unique hash value, 然后搞个hash table, 通过ID找SHA-2. 再做个reverse lookup
table, 每个SHA-2都列出其相应的ID list
6.两个白人SDE，主要是其中一个在面，另外一个自始至终没说话。
问题: 有一个大的catalog，总共有500Million个entry，每个entry内容是 （ID，
document），每个document大小约10KB，不同的ID对应的document可能相同，怎样设计
一个程序，对每个给定的一个ID，找出与该ID对应着相同的document的所有其他ID。
Follow Up: 如果每台机器内存只有1GB，硬盘100GB，怎么做
【在 l****i 的大作中提到】
: 二师兄你太牛了,膜拜
| p*****2
发帖数: 21240 | 24
对呀。就是我那个思路吧？
【在 s*********5 的大作中提到】
: 这个是不是要先用SHA-2（better and stronger than MD5)把所有document搞出一个
: unique hash value, 然后搞个hash table, 通过ID找SHA-2. 再做个reverse lookup
: table, 每个SHA-2都列出其相应的ID list
:
: 6.两个白人SDE，主要是其中一个在面，另外一个自始至终没说话。
: 问题: 有一个大的catalog，总共有500Million个entry，每个entry内容是 （ID，
: document），每个document大小约10KB，不同的ID对应的document可能相同，怎样设计
: 一个程序，对每个给定的一个ID，找出与该ID对应着相同的document的所有其他ID。
: Follow Up: 如果每台机器内存只有1GB，硬盘100GB，怎么做
| p*****2
发帖数: 21240 | 25
Even if your have a smart algorithm, which gives you 6 on d,e, f,..., then
how about this:
a1->b1->c1->d1
a1,a2,a3->b2->c2
a2, a3->b3->c3
a2, a3->b4->c4
a1 has a max distance of 4
a2, a3 have max distances of 3
but we need to take a2, a3 here first
这个case，我的算法会take a2,a3
【在 s*********5 的大作中提到】
: How about this graph, with maximum classes of 2 for each semester:
: a->b->c->d, e, f, g, h, i (6 semesters needed to finish all, but 4
: semesters to finish any)
: y,z->x->w->u->v (5 semesters needed to finish v)
: The best strategy is to do this:
: a, y
: b, z
: c, w
: ...
: but you may do y, z first if you are greedy
| j********x
发帖数: 2330 | 26 greedy只有在每门只是至多另一门课的先修课程的情况下是正确的，证明在下面的论文
里：
http://www.jstor.org/stable/pdfplus/167050.pdf?acceptTC=true
845页以后的部分，比较麻烦。
如果是任意的先后关系，则问题是np hard。经典的scheduling问题。
一般的算法分析可以大概猜出这道题在一般情况下是np hard这个结论。greedy应该是
一个很明显的近似算法，至于其他就看面试官心情了。
另外lz面什么方向的职位，怎么问这么奇葩的算法。。。
后面的document查重我以前问过类似的题，我提到的做法是从文件里的任意位置取少量
字符做digest。用digest做hash key，将放到hash table里，另设一个
table存放（这里假设ID是线性排列的整数，如果不是同样做hash table
）。找重在两个表里搜索就行。
假设160bit，20byte的digest，ID为4byte，每个表大概是10G内存，总共消耗20G，看
情况吧。
数据量更大就上mapreduce，原理类似。这个应该是他们想问的东西，或者是类似的分
布式处理平台。
【在 p*****2 的大作中提到】
: 我写了一下，用的greedy的算法。没想到反例，但是感觉也不容易证明。
: from heapq import *
: class Node:
: def __init__(self, val):
: self.val=val
: self.In=set()
: self.Out=set()
: def __cmp__(self, other):
: if len(self.Out): return 1
| p*****2
发帖数: 21240 | 27
这么麻烦。我觉得面试能把greedy的写出来就不错了。
【在 j********x 的大作中提到】
: greedy只有在每门只是至多另一门课的先修课程的情况下是正确的，证明在下面的论文
: 里：
: http://www.jstor.org/stable/pdfplus/167050.pdf?acceptTC=true
: 845页以后的部分，比较麻烦。
: 如果是任意的先后关系，则问题是np hard。经典的scheduling问题。
: 一般的算法分析可以大概猜出这道题在一般情况下是np hard这个结论。greedy应该是
: 一个很明显的近似算法，至于其他就看面试官心情了。
: 另外lz面什么方向的职位，怎么问这么奇葩的算法。。。
: 后面的document查重我以前问过类似的题，我提到的做法是从文件里的任意位置取少量
: 字符做digest。用digest做hash key，将放到hash table里，另设一个
| t*********7
发帖数: 255 | | m******s
发帖数: 1469 | 29 Zan and Bless!
【在 l****i 的大作中提到】
: 二师兄你太牛了,膜拜
| j********x
发帖数: 2330 | 30 scheduling都这种德行，看的简单，搞起来麻烦。。。
【在 p*****2 的大作中提到】
:
: 这么麻烦。我觉得面试能把greedy的写出来就不错了。
| | | l****i
发帖数: 230 | 31 我靠，听你这么一说我越来越觉得是被印度阿三故意刁难了
【在 j********x 的大作中提到】
: greedy只有在每门只是至多另一门课的先修课程的情况下是正确的，证明在下面的论文
: 里：
: http://www.jstor.org/stable/pdfplus/167050.pdf?acceptTC=true
: 845页以后的部分，比较麻烦。
: 如果是任意的先后关系，则问题是np hard。经典的scheduling问题。
: 一般的算法分析可以大概猜出这道题在一般情况下是np hard这个结论。greedy应该是
: 一个很明显的近似算法，至于其他就看面试官心情了。
: 另外lz面什么方向的职位，怎么问这么奇葩的算法。。。
: 后面的document查重我以前问过类似的题，我提到的做法是从文件里的任意位置取少量
: 字符做digest。用digest做hash key，将放到hash table里，另设一个
| p*****2
发帖数: 21240 | 32
没办法呀。这题没几个人不挂吧？我觉得面试写个toposort就可以了。
【在 l****i 的大作中提到】
: 我靠，听你这么一说我越来越觉得是被印度阿三故意刁难了
| h******0
发帖数: 427 | | l****i
发帖数: 230 | 34 多谢大家的bless，刚刚recruiter通知，Amazon决定给我offer了。看来攒人品太重要
了。
Amazon一般PhD毕业research scientist或SDE给多少钱啊？有知道的透露一下
现在手头还有6、7个onsite，决定拖一阵子再答复，有什么技巧吗？ 谢谢大家了，等
决定了offer散尽家财发包子。
另外，昨天面了MS，貌似也准备给offer了，等一下上面经。 | z****8
发帖数: 125 | 35 cong~~~~LZ牛啊~~~~多多拿offer~~~ | y********0
发帖数: 638 | 36 恭喜..真是牛人中的牛人啊.
【在 l****i 的大作中提到】
: 多谢大家的bless，刚刚recruiter通知，Amazon决定给我offer了。看来攒人品太重要
: 了。
: Amazon一般PhD毕业research scientist或SDE给多少钱啊？有知道的透露一下
: 现在手头还有6、7个onsite，决定拖一阵子再答复，有什么技巧吗？ 谢谢大家了，等
: 决定了offer散尽家财发包子。
: 另外，昨天面了MS，貌似也准备给offer了，等一下上面经。
| t**********h
发帖数: 2273 | 37 真牛逼，A和M都拿了，慢慢侃价吧
【在 l****i 的大作中提到】
: 多谢大家的bless，刚刚recruiter通知，Amazon决定给我offer了。看来攒人品太重要
: 了。
: Amazon一般PhD毕业research scientist或SDE给多少钱啊？有知道的透露一下
: 现在手头还有6、7个onsite，决定拖一阵子再答复，有什么技巧吗？ 谢谢大家了，等
: 决定了offer散尽家财发包子。
: 另外，昨天面了MS，貌似也准备给offer了，等一下上面经。
| v*********9
发帖数: 2457 | | p*****2
发帖数: 21240 | | d*********e
发帖数: 190 | | | | A********a
发帖数: 1846 | | h****p
发帖数: 87 | | x*****0
发帖数: 452 | | s*********e
发帖数: 70 | |
|
