TSC EB1-B PP 过（12-31-2012） - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Immigration - 落地生根

TSC EB1-B PP 过（12-31-2012）

TSC EB1-B PP 过（12-31-2012）# Immigration - 落地生根

d*k2013-01-01 08:01

1 楼

昨天面的，估计我没有达到考官的预期值，应该是fail了
给你一堆ads（广告），和一个广告，以及一个现成的function可以用来算出两个广告
之间的similarity, similarity是一个0到100的整数。（0是最similar的）
要求在这一堆广告里面找出和这个广告最similar的k个广告

x*p2013-01-01 08:01

2 楼

2012最后一天收到的，早上是clock stop，下午变成了approval。
12/10 mailed to TSC
12/11 delivered to TSC
12/13 RD (NO EMAIL SENT TO LAWYER OR EMPLOYER，
only EMPLOYER received Receipt Notice by mail on 12/20/2012)
12/20 PP filed
12/26 PP clock started
12/31 AD
找的郭律师，很认真负责和实在，回信回电话很及时，对推荐信要求比较严格，花了很
长那个时间，也许是我理解能力不行，但是按照要求写完前几封就好写多了。
希望自己485早日file，早日approve！
从这版上了解了很多信息，谢谢大家，也希望版上所有人新的一年都能够有好消息，心
想事成！

z*e2013-01-01 08:01

3 楼

top k question阿
建heap

w*s2013-01-01 08:01

4 楼

cong

z*e2013-01-01 08:01

5 楼

top k看来是最近的必考题

l*l2013-01-01 08:01

6 楼

cong

S*12013-01-01 08:01

7 楼

这是二爷的组啊，呼唤二爷....

I*r2013-01-01 08:01

8 楼

Cong

q*c2013-01-01 08:01

9 楼

是二爷面的吧。

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

: 昨天面的，估计我没有达到考官的预期值，应该是fail了
: 给你一堆ads（广告），和一个广告，以及一个现成的function可以用来算出两个广告
: 之间的similarity, similarity是一个0到100的整数。（0是最similar的）
: 要求在这一堆广告里面找出和这个广告最similar的k个广告

c*n2013-01-01 08:01

10 楼

cong

d*k2013-01-01 08:01

11 楼

不是，二爷给递进去的
面的应该不是中国人
有口音，应该也不是老美

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

: 是二爷面的吧。

s*62013-01-01 08:01

12 楼

恭喜

d*k2013-01-01 08:01

13 楼

晕死
我天天在版上看，怎么就没看到这个必考题呢

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

: top k看来是最近的必考题

L*S2013-01-01 08:01

14 楼

gxgx！

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

: 2012最后一天收到的，早上是clock stop，下午变成了approval。
: 12/10 mailed to TSC
: 12/11 delivered to TSC
: 12/13 RD (NO EMAIL SENT TO LAWYER OR EMPLOYER，
: only EMPLOYER received Receipt Notice by mail on 12/20/2012)
: 12/20 PP filed
: 12/26 PP clock started
: 12/31 AD
: 找的郭律师，很认真负责和实在，回信回电话很及时，对推荐信要求比较严格，花了很
: 长那个时间，也许是我理解能力不行，但是按照要求写完前几封就好写多了。

M*a2013-01-01 08:01

15 楼

lz几年工作经验啦。

l*22013-01-01 08:01

16 楼

GXGX!

j*32013-01-01 08:01

17 楼

马克

d*n2013-01-01 08:01

18 楼

恭喜

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

d*k2013-01-01 08:01

19 楼

why?

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

: lz几年工作经验啦。

r*r2013-01-01 08:01

20 楼

cong

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

w*r2013-01-01 08:01

21 楼

找关键词？广告之间有什么联系啊

g*12013-01-01 08:01

22 楼

cong

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

d*k2013-01-01 08:01

23 楼

不是让你算联系
算联系的function是给定的，直接调用就行
主要还是输出kth elements

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

: 找关键词？广告之间有什么联系啊

a*n2013-01-01 08:01

24 楼

gxgx

w*r2013-01-01 08:01

25 楼

那你讲讲吧，学习学习

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

: 不是让你算联系
: 算联系的function是给定的，直接调用就行
: 主要还是输出kth elements

B*a2013-01-01 08:01

26 楼

恭喜

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

d*k2013-01-01 08:01

27 楼

我没有答对阿
不过楼上不时有人说
建size 为k的max heap
把所有的n个similarity扔进去再取出来

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

: 那你讲讲吧，学习学习

e*p2013-01-01 08:01

28 楼

gxgx!

w*r2013-01-01 08:01

29 楼

那和排序找最大的有什么区别啊

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

: 我没有答对阿
: 不过楼上不时有人说
: 建size 为k的max heap
: 把所有的n个similarity扔进去再取出来

H*12013-01-01 08:01

30 楼

恭喜

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

d*k2013-01-01 08:01

31 楼

省点点时间吧

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

: 那和排序找最大的有什么区别啊

G*n2013-01-01 08:01

32 楼

Big cong!

w*r2013-01-01 08:01

33 楼

没看出来省了，你说说怎么省了

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

: 省点点时间吧

d*g2013-01-01 08:01

34 楼

cong and bless your 485!

d*k2013-01-01 08:01

35 楼

好像确实也不省阿

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

: 没看出来省了，你说说怎么省了

n*s2013-01-01 08:01

36 楼

gxgx!

W*y2013-01-01 08:01

37 楼

locality sensitive hashing

c*l2013-01-01 08:01

38 楼

Gx

★ 发自iPhone App: ChineseWeb 7.7

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

v*y2013-01-01 08:01

39 楼

如果面试官期待的是heap的算法的话，这个题真的不难。类似的题还有很多啊，什么找
出用户访问最多的k个网站，离原点最近的k个点……
楼上说的locality sensitive hashing能给讲讲吗？

L*u2013-01-01 08:01

40 楼

Cong~

d*k2013-01-01 08:01

41 楼

我不知道他是要heap还是quick selection
但是如果是要heap, 我岂不是还是自己实现一个heap insert function?

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

: 如果面试官期待的是heap的算法的话，这个题真的不难。类似的题还有很多啊，什么找
: 出用户访问最多的k个网站，离原点最近的k个点……
: 楼上说的locality sensitive hashing能给讲讲吗？

l*22013-01-01 08:01

42 楼

GXGX!

g*72013-01-01 08:01

43 楼

排序是nlog(n), Heap是nlog(k)

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

: 好像确实也不省阿

v*y2013-01-01 08:01

44 楼

至于时间和空间，当然比排序好的多了，排序时nlogn，用heap的话是nlogk，空间也只
用k

v*y2013-01-01 08:01

45 楼

priorityQueue啊,除非面试官不同意。

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

: 我不知道他是要heap还是quick selection
: 但是如果是要heap, 我岂不是还是自己实现一个heap insert function?

g*e2013-01-01 08:01

46 楼

当然是用quick select比较快
heap的方法太straight forward

d*k2013-01-01 08:01

47 楼

用heap也可以做成 klog(n)
这俩哪个更省？

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

: 排序是nlog(n), Heap是nlog(k)

l*a2013-01-01 08:01

48 楼

怎么看出来的呢？
二爷不给我递。。。：（

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

: 这是二爷的组啊，呼唤二爷....

z*e2013-01-01 08:01

49 楼

二爷的组还不好认？
二爷天天挂嘴边的nodejs和clojure
其他组一般不做要求
只有他们组在用，尤其是clojure
big data组要求etl&hibernate
goods组也不要求
很容易区分

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

: 怎么看出来的呢？
: 二爷不给我递。。。：（

z*e2013-01-01 08:01

50 楼

klog(n)的话消耗的空间太夸张
不可能建一个复杂度为n或者是跟n有关的内存块
因为n往往意味着大数据，默认是内存装不下
k远小于n，一般都是log(k)*n
读n用streaming

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

: 用heap也可以做成 klog(n)
: 这俩哪个更省？

l*12013-01-01 08:01

51 楼

这个题我做了，我开始也说的是heap，然后要求提高，你应该问他similarity如何定义
，他会告诉你是(1-100)，然后他期待的其实是类似桶排序的。

l*12013-01-01 08:01

52 楼

这个题我做了，我开始也说的是heap，然后要求提高，你应该问他similarity如何定义
，他会告诉你是(1-100)，然后他期待的其实是类似桶排序的。

b*t2013-01-01 08:01

53 楼

similarity没有相同的值才能桶排序吧？如果有最小的k个similarity都是1，怎么桶排
序？

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

: 这个题我做了，我开始也说的是heap，然后要求提高，你应该问他similarity如何定义
: ，他会告诉你是(1-100)，然后他期待的其实是类似桶排序的。

l*12013-01-01 08:01

54 楼

相同的就放在后面的链表里，你找到k个后自动返回就好。

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

: similarity没有相同的值才能桶排序吧？如果有最小的k个similarity都是1，怎么桶排
: 序？

z*e2013-01-01 08:01

55 楼

我觉得水桶排序这里的理解可能是map reduce

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

: similarity没有相同的值才能桶排序吧？如果有最小的k个similarity都是1，怎么桶排
: 序？

l*12013-01-01 08:01

56 楼

最后不用真正的排序，从水桶后往前找k个元素

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

: 我觉得水桶排序这里的理解可能是map reduce

S*A2013-01-01 08:01

57 楼

我觉得counting sort也可以啊，要是数很多的话用radix sort也行啊。

：这个题我做了，我开始也说的是heap，然后要求提高，你应该问他similarity如何定
义，他会告诉你是(1-100)，然后他期待的其实是类似桶排序的。
……

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

: 最后不用真正的排序，从水桶后往前找k个元素

b*t2013-01-01 08:01

58 楼

链表可以，这样可以做到O(n)，应该是最快了

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

: 相同的就放在后面的链表里，你找到k个后自动返回就好。

z*e2013-01-01 08:01

59 楼

那就是先通过分clustering来归类大数据？
用这种方式来优化n
把n变成lgn
最后是lgk * lg n

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

: 最后不用真正的排序，从水桶后往前找k个元素

l*12013-01-01 08:01

60 楼

恩我就是提到 bucket sort和radix sort后，面试官好像觉得还不错，我就继续说了。

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

: 我觉得counting sort也可以啊，要是数很多的话用radix sort也行啊。
:
: ：这个题我做了，我开始也说的是heap，然后要求提高，你应该问他similarity如何定
: 义，他会告诉你是(1-100)，然后他期待的其实是类似桶排序的。
: ……

z*e2013-01-01 08:01

61 楼

所以key是grouping？

了。

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

: 恩我就是提到 bucket sort和radix sort后，面试官好像觉得还不错，我就继续说了。

S*A2013-01-01 08:01

62 楼

相同的值可以放在一个bucket里啊

：similarity没有相同的值才能桶排序吧？如果有最小的k个similarity都是1，怎么桶
排序？
：
：
：【在 leetcoder1 (mitbbsCoder) 的大作中提到: 】
：: 这个题我做了，我开始也说的是heap，然后要求提高，你应该问他similarity如何
定义
：: ，他会告诉你是(1-100)，然后他期待的其实是类似桶排序的。
：
……

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

: 链表可以，这样可以做到O(n)，应该是最快了

z*e2013-01-01 08:01

63 楼

我大概明白了
heap没有错
这是第一步，复杂度是lg k * n
但是n太大，可以进一步降低n的复杂度
这个时候用top down方式
随便你用，就是分成一堆的clustering
这样你就可以不用遍历所有的n
而可以只找你想要的那一个group里面的数据就好了
这个可以提前做点处理，比如对于similarity是0-9的集中存放
10-19的放另外一个group，然后找的时候，就找0－9这个group就好了

z*e2013-01-01 08:01

64 楼

sim是相互
a和b相似，b和a也相似
所以先看你这个广告在哪个group里面
然后就找这个group
big data说这个就是cluster

z*e2013-01-01 08:01

65 楼

ln k是算法复杂度
n怎么处理是统计
big data处理第一步就是找similarity
这个组是big data组？

S*A2013-01-01 08:01

66 楼

too optimistic，你怎么知道你的一个group会/不会cover k个值？

：我大概明白了
：heap没有错
：这是第一步，复杂度是lg k * n
：但是n太大，可以进一步降低n的复杂度
：这个时候用top down方式
：随便你用，就是分成一堆的clustering
：这样你就可以不用遍历所有的n
……

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

: ln k是算法复杂度
: n怎么处理是统计
: big data处理第一步就是找similarity
: 这个组是big data组？

z*e2013-01-01 08:01

67 楼

假设当然是k<k非常小，比如10,20这种
n非常大，几十万肯定不只，几百万至少了

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

: too optimistic，你怎么知道你的一个group会/不会cover k个值？
:
: ：我大概明白了
: ：heap没有错
: ：这是第一步，复杂度是lg k * n
: ：但是n太大，可以进一步降低n的复杂度
: ：这个时候用top down方式
: ：随便你用，就是分成一堆的clustering
: ：这样你就可以不用遍历所有的n
: ……

S*A2013-01-01 08:01

68 楼

你没明白我的意思，假设k为100，你第一个bucket装了10个，第二个装了30，第三个可
能没有，第四个装了80个，你怎么找呢？而且你可能不知道哪个bucket里装多少吧？

：假设当然是k<<n啦
：k非常小，比如10,20这种
：n非常大，几十万肯定不只，几百万至少了
：【在 SEKKA (努力备考中......) 的大作中提到: 】
：: too optimistic，你怎么知道你的一个group会/不会cover k个值？
：: ：我大概明白了
：: ：heap没有错
……

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

: 假设当然是k<: k非常小，比如10,20这种
: n非常大，几十万肯定不只，几百万至少了

z*e2013-01-01 08:01

69 楼

想到这里有种豁然开朗的感觉
接轨了

S*A2013-01-01 08:01

70 楼

我觉得这道题你说出O(n)的算法就行了吧。

：假设当然是k<<n啦
：k非常小，比如10,20这种
：n非常大，几十万肯定不只，几百万至少了
：【在 SEKKA (努力备考中......) 的大作中提到: 】
：: too optimistic，你怎么知道你的一个group会/不会cover k个值？
：: ：我大概明白了
：: ：heap没有错
……

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

: 想到这里有种豁然开朗的感觉
: 接轨了

z*e2013-01-01 08:01

71 楼

你没看懂我的意思
我没有说heap是错的，还是用heap对付内存
你没有必要改成桶排序，对于内存里面的k个数据来说
我对n做处理，而不是k
我说的不是算法，或者不是简单的heap, bucket这种内存算法
优化也不见得只能优化内存呀

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

: 你没明白我的意思，假设k为100，你第一个bucket装了10个，第二个装了30，第三个可
: 能没有，第四个装了80个，你怎么找呢？而且你可能不知道哪个bucket里装多少吧？
:
: ：假设当然是k<<n啦
: ：k非常小，比如10,20这种
: ：n非常大，几十万肯定不只，几百万至少了
: ：【在 SEKKA (努力备考中......) 的大作中提到: 】
: ：: too optimistic，你怎么知道你的一个group会/不会cover k个值？
: ：: ：我大概明白了
: ：: ：heap没有错

z*e2013-01-01 08:01

72 楼

我觉得可以，我面肯定过了

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

: 我觉得这道题你说出O(n)的算法就行了吧。
:
: ：假设当然是k<<n啦
: ：k非常小，比如10,20这种
: ：n非常大，几十万肯定不只，几百万至少了
: ：【在 SEKKA (努力备考中......) 的大作中提到: 】
: ：: too optimistic，你怎么知道你的一个group会/不会cover k个值？
: ：: ：我大概明白了
: ：: ：heap没有错
: ……

L*s2013-01-01 08:01

73 楼

整数，那就计数排序好了