包子急求帮助－－－关于推荐信，如何回复，谢谢 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Immigration - 落地生根

包子急求帮助－－－关于推荐信，如何回复，谢谢

包子急求帮助－－－关于推荐信，如何回复，谢谢# Immigration - 落地生根

y*e2013-01-28 08:01

1 楼

Updated的题目。
1. 给定一个directed graph和一个s节点和一个d节点，判断s和d的距离是否<=3。距离
定义为s和d之间最短路径上link的数目。如果d是s的邻居，则距离为1。
注意，这个directed graph使用adjacent array来表示一个节点的所有neighbors，并
且每个节点最多有n个neighbors。每个节点都有一个Idx，并且每个节点的adjacent
array都是sorted。例如1有邻居2和3，那么1的adjacent array是[2,3] (sorted)
直接的BSF解法时间复杂度是O(n^3)。
要求设计Solution是时间 O(n^2)。
2. 设计一个hash table，实现set（int key，int val）和get（int key）
3. 给定一个整数array A (长度为n)，求出另外一个array B，使得B[i] = A[0]A[1]..
.A[i - 1]A[i + 1]...A[n - 1] (i.e., A[i] is missing from B[i])
如果不可以用除法，如何解？要求solution是时间O(n)
4. 给出n个点，求最多点的数目(这些点在一条直线), leetcode原题

w*u2013-01-28 08:01

2 楼

在要推荐信，
1，有个老板同意了，他把email转给了他的秘书，让秘书帮忙联系我。可能秘书搞不清
楚，她写email说“Please also include addresses and instructions for
submitting Letter of Support.”
请问大家我该如何回复她呢？怎么跟她解释让她把信扫描给我？非常感谢！
2，还有一个老板也同意了，不过他说这是第一次写这个，啥也不懂，但是他会考虑给
我写，不过他在email里说“Can you send me the link (or a pdf) for the
immigration service that describes the requirement for an outside expert (
and other requirements) just so I understand more what the government is
looking for? Also should I wish to speak to someone who knows you, with whom
should I speak?”
请问哪里能找到他要的link或者document？还是我就直接move on了？谢谢

c*r2013-01-28 08:01

3 楼

mark.

e*p2013-01-28 08:01

4 楼

这不是挺好吗？你正好说我写个draft给你们改，你们要是同意就签个字扫描了email了
给我。

q*c2013-01-28 08:01

5 楼

bless! 请问有什么system design的题吗？你面的是infra还是applications?

..

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

: Updated的题目。
: 1. 给定一个directed graph和一个s节点和一个d节点，判断s和d的距离是否<=3。距离
: 定义为s和d之间最短路径上link的数目。如果d是s的邻居，则距离为1。
: 注意，这个directed graph使用adjacent array来表示一个节点的所有neighbors，并
: 且每个节点最多有n个neighbors。每个节点都有一个Idx，并且每个节点的adjacent
: array都是sorted。例如1有邻居2和3，那么1的adjacent array是[2,3] (sorted)
: 直接的BSF解法时间复杂度是O(n^3)。
: 要求设计Solution是时间 O(n^2)。
: 2. 设计一个hash table，实现set（int key，int val）和get（int key）
: 3. 给定一个整数array A (长度为n)，求出另外一个array B，使得B[i] = A[0]A[1]..

w*u2013-01-28 08:01

6 楼

我一开始就说写draft给他了。第一个估计是秘书不懂，我该如何回复她让她把信直接
扫描给我呢？第二个老板要link或者具体材料说明，还要个认识我的人的联系方式，要
talk，唉。该怎么办？

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

: 这不是挺好吗？你正好说我写个draft给你们改，你们要是同意就签个字扫描了email了
: 给我。

c*r2013-01-28 08:01

7 楼

可能第二题设计hash table就算design了吧，有很多东西需要讨论。

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

: bless! 请问有什么system design的题吗？你面的是infra还是applications?
:
: ..

w*u2013-01-28 08:01

8 楼

再顶一下，需要帮助啊

M*D2013-01-28 08:01

9 楼

1. 给定一个directed graph和一个s节点和一个d节点，判断s和d的距离是否<=3。距离
定义为s和d之间最短路径上link的数目。如果d是s的邻居，则距离为1。
注意，这个directed graph使用adjacent array来表示一个节点的所有neighbors。每
个节点都有一个Idx，并且每个节点的adjacent array都是sorted。例如1有邻居2和3，
那么1的adjacent array是[2,3] (sorted)
只觉得就是个循环3遍的BFS。。这题的“注意”有什么需要特别注意的吗。。是不是和
BFS搜索的state标记有关？有人能帮忙解释吗

f*s2013-01-28 08:01

10 楼

这两个都很积极的在帮助啊，干嘛要move on。
直接写信解释说我的draft letter是找我的移民律师咨询过的，都是按照政府的标准写
的。请直接签名扫描给我就行了。

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

: 再顶一下，需要帮助啊

c*r2013-01-28 08:01

11 楼

假设给定s 和 d的 vertex IDX，直接从s开始用bfs,用一个队列维持（vertex index,
level)的数对，初始时， push (s, 1),然后把s的neighbors push 到队列里，增加当
前的层数。比如s=1, 如果1的邻居为2,3，那么push (2,2), (3,2)到队列中，表示1
的neighbors 2 and 3 have level =2.
如果发现在某一个节点的neighbor为d，计算s,d层数之间的距离，看看是否<=3.
是这样吗？应该不需要几次bfs吧？
请指出错误我好学习，谢谢！

【在 M*****D 的大作中提到】

: 1. 给定一个directed graph和一个s节点和一个d节点，判断s和d的距离是否<=3。距离
: 定义为s和d之间最短路径上link的数目。如果d是s的邻居，则距离为1。
: 注意，这个directed graph使用adjacent array来表示一个节点的所有neighbors。每
: 个节点都有一个Idx，并且每个节点的adjacent array都是sorted。例如1有邻居2和3，
: 那么1的adjacent array是[2,3] (sorted)
: 只觉得就是个循环3遍的BFS。。这题的“注意”有什么需要特别注意的吗。。是不是和
: BFS搜索的state标记有关？有人能帮忙解释吗

e*p2013-01-28 08:01

12 楼

第一个就直接跟他秘书说，你会发给他一个Draft请他改，改好后请签字然后扫描email
给你。既然他答应了，让秘书和你联系，该怎么做你就怎么跟她说，没什么不好意思的
，语气柔和些就行了。
第二个你可以告诉他一个大纲（就是每段该写些什么内容），或者把官网上对eb1的要
求发给他看看，同时强调你可以给他个draft。要talk的话，可以给他你老板的联系方
式，然后去跟老板通个气（如果你老板罩你的话）。
祝好运！

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

: 我一开始就说写draft给他了。第一个估计是秘书不懂，我该如何回复她让她把信直接
: 扫描给我呢？第二个老板要link或者具体材料说明，还要个认识我的人的联系方式，要
: talk，唉。该怎么办？

M*D2013-01-28 08:01

13 楼

哦，我所说的几次bfs就是有一个counter，然后当
while(!queue.isEmpty()){
counter++; //比如一开始queue只有1入队列，这时候counter就是1.然后2，3入了
，这时候counter就是2了
if(counter>3) return false;
.....//找neighbor放入队列
}
我不需要额外的level来对应每一个node 不过我需要一个state标志来标识这个node是
否被visited
我不知道这个sorted neighbor有什么特别用意

,
1

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

: 假设给定s 和 d的 vertex IDX，直接从s开始用bfs,用一个队列维持（vertex index,
: level)的数对，初始时， push (s, 1),然后把s的neighbors push 到队列里，增加当
: 前的层数。比如s=1, 如果1的邻居为2,3，那么push (2,2), (3,2)到队列中，表示1
: 的neighbors 2 and 3 have level =2.
: 如果发现在某一个节点的neighbor为d，计算s,d层数之间的距离，看看是否<=3.
: 是这样吗？应该不需要几次bfs吧？
: 请指出错误我好学习，谢谢！

f*s2013-01-28 08:01

14 楼

我的包子

whom

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

: 在要推荐信，
: 1，有个老板同意了，他把email转给了他的秘书，让秘书帮忙联系我。可能秘书搞不清
: 楚，她写email说“Please also include addresses and instructions for
: submitting Letter of Support.”
: 请问大家我该如何回复她呢？怎么跟她解释让她把信扫描给我？非常感谢！
: 2，还有一个老板也同意了，不过他说这是第一次写这个，啥也不懂，但是他会考虑给
: 我写，不过他在email里说“Can you send me the link (or a pdf) for the
: immigration service that describes the requirement for an outside expert (
: and other requirements) just so I understand more what the government is
: looking for? Also should I wish to speak to someone who knows you, with whom

c*r2013-01-28 08:01

15 楼

我也想不清楚，如果说要利用这个排序的特点，可能有特别用意，否则没有什么必要吧？
等待高人

【在 M*****D 的大作中提到】

: 哦，我所说的几次bfs就是有一个counter，然后当
: while(!queue.isEmpty()){
: counter++; //比如一开始queue只有1入队列，这时候counter就是1.然后2，3入了
: ，这时候counter就是2了
: if(counter>3) return false;
: .....//找neighbor放入队列
: }
: 我不需要额外的level来对应每一个node 不过我需要一个state标志来标识这个node是
: 否被visited
: 我不知道这个sorted neighbor有什么特别用意

w*u2013-01-28 08:01

16 楼

包子已发，谢谢！

l*i2013-01-28 08:01

17 楼

听说L家有题库，有没有人来确认一下是不是真的。

A*n2013-01-28 08:01

18 楼

推荐人同意后还有两道门槛，你跨过后才能拿到推荐信，而且是你想要的推荐信。
1.向对方解说这个推荐信的前因后果。显然，你现在在这个门槛前面。移民局从来没有
要求推荐信，所以，解释起来非一句两句就能说清楚。（1）什么是EB1？标准是什么？
（2）按照大家的经验，都是由您这样的（独立）推荐人来评价向移民局做reference，
所以请您帮忙（有些律师的网页上提到需要推荐信，可给其这个link）。如果可能，让
你的律师直接或间接解释这些最好。（个人的经验，从每个细节进行了详细解释。有一
个推荐人回信：Too much, just tell what I need to do。哈，要得就是这个！）
2.推荐信最后有你本人来起草。这是个说话的技巧，“To save your time”是比较冠
冕堂皇的理由。“You only need to do a signature”是很粗鲁的。这一步走不好，
没有拿到起草推荐信的权利，推荐人自己起草信，那这封信估计不会是你想要的。

x*k2013-01-28 08:01

19 楼

第一题，从s开始，查看n个邻居，再查看n^2个邻居的邻居，第三步，对于n^2的节点，
查看它们的邻居。因为adjacency list是sorted，可以用binary search来检查d在不在
其中。这样整个复杂度是O(n^2 log(n))。
请教，有办法做到O(n^2)么？
第三题看起来容易，先算log(B(i)) = log(A(0)) + log(A(1)) + ...
只用log, +, -, exp，避开了除法。这样对不对？

w*u2013-01-28 08:01

20 楼

很有用的信息，非常感谢，包子奉上：）

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

: 推荐人同意后还有两道门槛，你跨过后才能拿到推荐信，而且是你想要的推荐信。
: 1.向对方解说这个推荐信的前因后果。显然，你现在在这个门槛前面。移民局从来没有
: 要求推荐信，所以，解释起来非一句两句就能说清楚。（1）什么是EB1？标准是什么？
: （2）按照大家的经验，都是由您这样的（独立）推荐人来评价向移民局做reference，
: 所以请您帮忙（有些律师的网页上提到需要推荐信，可给其这个link）。如果可能，让
: 你的律师直接或间接解释这些最好。（个人的经验，从每个细节进行了详细解释。有一
: 个推荐人回信：Too much, just tell what I need to do。哈，要得就是这个！）
: 2.推荐信最后有你本人来起草。这是个说话的技巧，“To save your time”是比较冠
: 冕堂皇的理由。“You only need to do a signature”是很粗鲁的。这一步走不好，
: 没有拿到起草推荐信的权利，推荐人自己起草信，那这封信估计不会是你想要的。

h*g2013-01-28 08:01

21 楼

我觉得那个求最短路径的可能可以这么做：1.先查看s在不在d的邻居里，若在返回true
否则进行2. 2. 看s的邻居和d邻居有没有共同的节点，nlgn。若有返回true，否则进
行3. 3.剩下的点看有没有即在s的邻居里又在d的邻居里，如果有返回true 否则返回
false

w*y2013-01-28 08:01

22 楼

对第一个要给一个比较简单但是清楚的解释，秘书没有决定权，所以你不说清楚，她会
一直问，沟通会比较麻烦，容易拖下来。之后你可以提供一个Draft，说是给她参考。
第二个是那个老板亲自弄的话，你提供一个PDF的解释文档，把重点标出来。再直接给
一个Draft，不妨直接告诉他就是你律师帮你弄的Draft，估计他大概改一点也就给你签
了。多提供你们系里几个他认识的人，让他talk吧。这些人都很忙，不会太较劲的。

h*e2013-01-28 08:01

23 楼

我觉得第一题还是O(n^3) 阿， bfs 顶多在第三层的时候用个二分加速一下，但是不
改变复杂度啊。

t*12013-01-28 08:01

24 楼

ding

e*l2013-01-28 08:01

25 楼

不一样。同时从起点和终点开始搜

h*e2013-01-28 08:01

26 楼

哦，对你说的对。先搜索source点 distance 为2的点集合 O(N^2)，然后用哈希判断
是否和destination点的O（N）邻居集合有交集，复杂度 O(N^2)
这个距离要求是三还是挺好的，要是距离是五什么的就需要双向搜索，代码就很变得很
难了。

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

: 不一样。同时从起点和终点开始搜

x*k2013-01-28 08:01

27 楼

还是不很明白。如果是undirected graph这没问题。可这是direcetd graph，所以
source点 distance 为2的点集合与 destination点的O（N）邻居集合完全可以没
有交集，但是destination点距离source为3。

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

: 哦，对你说的对。先搜索source点 distance 为2的点集合 O(N^2)，然后用哈希判断
: 是否和destination点的O（N）邻居集合有交集，复杂度 O(N^2)
: 这个距离要求是三还是挺好的，要是距离是五什么的就需要双向搜索，代码就很变得很
: 难了。

r*k2013-01-28 08:01

28 楼

第三题
想到的是弄两个辅助向量
A(0) A(0)*A(1) A(0)A(1)A(2) ...
A(n) A(n)A(n-1) ....
这两个向量再乘起来就可以了
复杂度不高
空间也可以不额外占用

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

: 第一题，从s开始，查看n个邻居，再查看n^2个邻居的邻居，第三步，对于n^2的节点，
: 查看它们的邻居。因为adjacency list是sorted，可以用binary search来检查d在不在
: 其中。这样整个复杂度是O(n^2 log(n))。
: 请教，有办法做到O(n^2)么？
: 第三题看起来容易，先算log(B(i)) = log(A(0)) + log(A(1)) + ...
: 只用log, +, -, exp，避开了除法。这样对不对？

m*e2013-01-28 08:01

29 楼

mark

s*k2013-01-28 08:01

30 楼

第一题，能不能用Dijkstra算法？ Dijkstra算法的复杂度是 O(n^2) 或者 O(nlogn)
（用heap)。是不是我漏掉了什么。

..

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

s*k2013-01-28 08:01

31 楼

已放在队列里的vertex的level可能会减少。

,
1

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

h*e2013-01-28 08:01

32 楼

俄确实，无向图那么做可以达到O（n^2)，至于有向图，似乎在第三层二分加速后复
杂度是O(n^2 logn)

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

: 还是不很明白。如果是undirected graph这没问题。可这是direcetd graph，所以
: source点 distance 为2的点集合与 destination点的O（N）邻居集合完全可以没
: 有交集，但是destination点距离source为3。

f*s2013-01-28 08:01

33 楼

mark

y*e2013-01-28 08:01

34 楼

对不起，你们的分析是对的，原题是undirected graph。上面的分析也都是对的。我已
经把原题的表示改了。

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

: 俄确实，无向图那么做可以达到O（n^2)，至于有向图，似乎在第三层二分加速后复
: 杂度是O(n^2 logn)

r*k2013-01-28 08:01

35 楼

第一个题，是双向dijkstra搜索么？
从s走2步
t走1步
是n^2级的
判断是否有正反向都搜到的节点

距离
，并
..

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

y*n2013-01-28 08:01

36 楼

2 和 3 不是一样的吗？
3 应该是看 s 的邻居的邻居和 d 的邻居的邻居有没有共同点？

true

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

: 我觉得那个求最短路径的可能可以这么做：1.先查看s在不在d的邻居里，若在返回true
: 否则进行2. 2. 看s的邻居和d邻居有没有共同的节点，nlgn。若有返回true，否则进
: 行3. 3.剩下的点看有没有即在s的邻居里又在d的邻居里，如果有返回true 否则返回
: false

s*i2013-01-28 08:01

37 楼

mark

w*22013-01-28 08:01

38 楼

第3题有点没思路，不能用除法，始终只能想到O（nlgn），如何到O(N)的，求楼主帮忙

m*d2013-01-28 08:01

39 楼

第3题:先计算LEFT[I]=LEFT[I-1]*A[I-1],with LEFT[0]=1, 用时O(n), 然后计算RIGHT
[I]=A[I-1]*RIGHT[I+1],那么B[I]=LEFT[I-1]*RIGHT[I+1].总共用时O(N)

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

: 第3题有点没思路，不能用除法，始终只能想到O（nlgn），如何到O(N)的，求楼主帮忙