d**k 发帖数: 797 | 1 昨天面的,估计我没有达到考官的预期值,应该是fail了
给你一堆ads(广告),和一个广告,以及一个现成的function可以用来算出两个广告
之间的similarity, similarity是一个0到100的整数。(0是最similar的)
要求在这一堆广告里面找出和这个广告最similar的k个广告 |
z****e 发帖数: 54598 | |
z****e 发帖数: 54598 | |
S******1 发帖数: 216 | |
q********c 发帖数: 1774 | 5 是二爷面的吧。
【在 d**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 昨天面的,估计我没有达到考官的预期值,应该是fail了 : 给你一堆ads(广告),和一个广告,以及一个现成的function可以用来算出两个广告 : 之间的similarity, similarity是一个0到100的整数。(0是最similar的) : 要求在这一堆广告里面找出和这个广告最similar的k个广告
|
d**k 发帖数: 797 | 6 不是,二爷给递进去的
面的应该不是中国人
有口音,应该也不是老美
【在 q********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是二爷面的吧。
|
d**k 发帖数: 797 | 7 晕死
我天天在版上看,怎么就没看到这个必考题呢
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : top k看来是最近的必考题
|
M**a 发帖数: 848 | |
|
j**********3 发帖数: 3211 | |
d**k 发帖数: 797 | 10 why?
【在 M**a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : lz几年工作经验啦。
|
|
|
w****r 发帖数: 15252 | |
d**k 发帖数: 797 | 12 不是让你算联系
算联系的function是给定的,直接调用就行
主要还是输出kth elements
【在 w****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 找关键词?广告之间有什么联系啊
|
w****r 发帖数: 15252 | 13 那你讲讲吧,学习学习
【在 d**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是让你算联系 : 算联系的function是给定的,直接调用就行 : 主要还是输出kth elements
|
d**k 发帖数: 797 | 14 我没有答对阿
不过楼上不时有人说
建size 为k的max heap
把所有的n个similarity扔进去再取出来
【在 w****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那你讲讲吧,学习学习
|
w****r 发帖数: 15252 | 15 那和排序找最大的有什么区别啊
【在 d**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我没有答对阿 : 不过楼上不时有人说 : 建size 为k的max heap : 把所有的n个similarity扔进去再取出来
|
d**k 发帖数: 797 | 16 省点点时间吧
【在 w****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那和排序找最大的有什么区别啊
|
w****r 发帖数: 15252 | 17 没看出来省了,你说说怎么省了
【在 d**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 省点点时间吧
|
d**k 发帖数: 797 | 18 好像确实也不省阿
【在 w****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没看出来省了,你说说怎么省了
|
W*********y 发帖数: 481 | 19 locality sensitive hashing |
v*****y 发帖数: 68 | 20 如果面试官期待的是heap的算法的话,这个题真的不难。类似的题还有很多啊,什么找
出用户访问最多的k个网站,离原点最近的k个点……
楼上说的locality sensitive hashing能给讲讲吗? |
|
|
d**k 发帖数: 797 | 21 我不知道他是要heap还是quick selection
但是如果是要heap, 我岂不是还是自己实现一个heap insert function?
【在 v*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果面试官期待的是heap的算法的话,这个题真的不难。类似的题还有很多啊,什么找 : 出用户访问最多的k个网站,离原点最近的k个点…… : 楼上说的locality sensitive hashing能给讲讲吗?
|
g*******7 发帖数: 32 | 22 排序是nlog(n), Heap是nlog(k)
【在 d**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好像确实也不省阿
|
v*****y 发帖数: 68 | 23 至于时间和空间,当然比排序好的多了,排序时nlogn,用heap的话是nlogk,空间也只
用k |
v*****y 发帖数: 68 | 24
priorityQueue啊,除非面试官不同意。
【在 d**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不知道他是要heap还是quick selection : 但是如果是要heap, 我岂不是还是自己实现一个heap insert function?
|
g*********e 发帖数: 14401 | 25 当然是用quick select比较快
heap的方法太straight forward |
d**k 发帖数: 797 | 26 用heap也可以做成 klog(n)
这俩哪个更省?
【在 g*******7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 排序是nlog(n), Heap是nlog(k)
|
l*****a 发帖数: 14598 | 27 怎么看出来的呢?
二爷不给我递。。。:(
【在 S******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是二爷的组啊,呼唤二爷....
|
z****e 发帖数: 54598 | 28 二爷的组还不好认?
二爷天天挂嘴边的nodejs和clojure
其他组一般不做要求
只有他们组在用,尤其是clojure
big data组要求etl&hibernate
goods组也不要求
很容易区分
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怎么看出来的呢? : 二爷不给我递。。。:(
|
z****e 发帖数: 54598 | 29 klog(n)的话消耗的空间太夸张
不可能建一个复杂度为n或者是跟n有关的内存块
因为n往往意味着大数据,默认是内存装不下
k远小于n,一般都是log(k)*n
读n用streaming
【在 d**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用heap也可以做成 klog(n) : 这俩哪个更省?
|
l********1 发帖数: 24 | 30 这个题我做了,我开始也说的是heap,然后要求提高,你应该问他similarity如何定义
,他会告诉你是(1-100),然后他期待的其实是类似桶排序的。 |
|
|
l********1 发帖数: 24 | 31 这个题我做了,我开始也说的是heap,然后要求提高,你应该问他similarity如何定义
,他会告诉你是(1-100),然后他期待的其实是类似桶排序的。 |
b*********t 发帖数: 170 | 32 similarity没有相同的值才能桶排序吧?如果有最小的k个similarity都是1,怎么桶排
序?
【在 l********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题我做了,我开始也说的是heap,然后要求提高,你应该问他similarity如何定义 : ,他会告诉你是(1-100),然后他期待的其实是类似桶排序的。
|
l********1 发帖数: 24 | 33 相同的就放在后面的链表里,你找到k个后自动返回就好。
【在 b*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : similarity没有相同的值才能桶排序吧?如果有最小的k个similarity都是1,怎么桶排 : 序?
|
z****e 发帖数: 54598 | 34 我觉得水桶排序这里的理解可能是map reduce
【在 b*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : similarity没有相同的值才能桶排序吧?如果有最小的k个similarity都是1,怎么桶排 : 序?
|
l********1 发帖数: 24 | 35 最后不用真正的排序,从水桶后往前找k个元素
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得水桶排序这里的理解可能是map reduce
|
S***A 发帖数: 133 | 36 我觉得counting sort也可以啊,要是数很多的话用radix sort也行啊。
:这个题我做了,我开始也说的是heap,然后要求提高,你应该问他similarity如何定
义,他会告诉你是(1-100),然后他期待的其实是类似桶排序的。
……
【在 l********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最后不用真正的排序,从水桶后往前找k个元素
|
b*********t 发帖数: 170 | 37 链表可以,这样可以做到O(n),应该是最快了
【在 l********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 相同的就放在后面的链表里,你找到k个后自动返回就好。
|
z****e 发帖数: 54598 | 38 那就是先通过分clustering来归类大数据?
用这种方式来优化n
把n变成lgn
最后是lgk * lg n
【在 l********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最后不用真正的排序,从水桶后往前找k个元素
|
l********1 发帖数: 24 | 39 恩 我就是提到 bucket sort和radix sort后,面试官好像觉得还不错,我就继续说了。
【在 S***A 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得counting sort也可以啊,要是数很多的话用radix sort也行啊。 : : :这个题我做了,我开始也说的是heap,然后要求提高,你应该问他similarity如何定 : 义,他会告诉你是(1-100),然后他期待的其实是类似桶排序的。 : ……
|
z****e 发帖数: 54598 | 40 所以key是grouping?
了。
【在 l********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 恩 我就是提到 bucket sort和radix sort后,面试官好像觉得还不错,我就继续说了。
|
|
|
S***A 发帖数: 133 | 41 相同的值可以放在一个bucket里啊
:similarity没有相同的值才能桶排序吧?如果有最小的k个similarity都是1,怎么桶
排序?
:
:
:【 在 leetcoder1 (mitbbsCoder) 的大作中提到: 】
:: 这个题我做了,我开始也说的是heap,然后要求提高,你应该问他similarity如何
定义
:: ,他会告诉你是(1-100),然后他期待的其实是类似桶排序的。
:
……
【在 b*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 链表可以,这样可以做到O(n),应该是最快了
|
z****e 发帖数: 54598 | 42 我大概明白了
heap没有错
这是第一步,复杂度是lg k * n
但是n太大,可以进一步降低n的复杂度
这个时候用top down方式
随便你用,就是分成一堆的clustering
这样你就可以不用遍历所有的n
而可以只找你想要的那一个group里面的数据就好了
这个可以提前做点处理,比如对于similarity是0-9的集中存放
10-19的放另外一个group,然后找的时候,就找0-9这个group就好了 |
z****e 发帖数: 54598 | 43 sim是相互
a和b相似,b和a也相似
所以先看你这个广告在哪个group里面
然后就找这个group
big data说这个就是cluster |
z****e 发帖数: 54598 | 44 ln k是算法复杂度
n怎么处理是统计
big data处理第一步就是找similarity
这个组是big data组? |
S***A 发帖数: 133 | 45 too optimistic,你怎么知道你的一个group会/不会cover k个值?
:我大概明白了
:heap没有错
:这是第一步,复杂度是lg k * n
:但是n太大,可以进一步降低n的复杂度
:这个时候用top down方式
:随便你用,就是分成一堆的clustering
:这样你就可以不用遍历所有的n
……
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : ln k是算法复杂度 : n怎么处理是统计 : big data处理第一步就是找similarity : 这个组是big data组?
|
z****e 发帖数: 54598 | 46 假设当然是k<
k非常小,比如10,20这种
n非常大,几十万肯定不只,几百万至少了
【在 S***A 的大作中提到】![](/moin_static193/solenoid/img/up.png) : too optimistic,你怎么知道你的一个group会/不会cover k个值? : : :我大概明白了 : :heap没有错 : :这是第一步,复杂度是lg k * n : :但是n太大,可以进一步降低n的复杂度 : :这个时候用top down方式 : :随便你用,就是分成一堆的clustering : :这样你就可以不用遍历所有的n : ……
|
S***A 发帖数: 133 | 47 你没明白我的意思,假设k为100,你第一个bucket装了10个,第二个装了30,第三个可
能没有,第四个装了80个,你怎么找呢?而且你可能不知道哪个bucket里装多少吧?
:假设当然是k<<n啦
:k非常小,比如10,20这种
:n非常大,几十万肯定不只,几百万至少了
:【 在 SEKKA (努力备考中......) 的大作中提到: 】
:: too optimistic,你怎么知道你的一个group会/不会cover k个值?
:: :我大概明白了
:: :heap没有错
……
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设当然是k<: k非常小,比如10,20这种 : n非常大,几十万肯定不只,几百万至少了
|
z****e 发帖数: 54598 | |
S***A 发帖数: 133 | 49 我觉得这道题你说出O(n)的算法就行了吧。
:假设当然是k<<n啦
:k非常小,比如10,20这种
:n非常大,几十万肯定不只,几百万至少了
:【 在 SEKKA (努力备考中......) 的大作中提到: 】
:: too optimistic,你怎么知道你的一个group会/不会cover k个值?
:: :我大概明白了
:: :heap没有错
……
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 想到这里有种豁然开朗的感觉 : 接轨了
|
z****e 发帖数: 54598 | 50 你没看懂我的意思
我没有说heap是错的,还是用heap对付内存
你没有必要改成桶排序,对于内存里面的k个数据来说
我对n做处理,而不是k
我说的不是算法,或者不是简单的heap, bucket这种内存算法
优化也不见得只能优化内存呀
【在 S***A 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你没明白我的意思,假设k为100,你第一个bucket装了10个,第二个装了30,第三个可 : 能没有,第四个装了80个,你怎么找呢?而且你可能不知道哪个bucket里装多少吧? : : :假设当然是k<<n啦 : :k非常小,比如10,20这种 : :n非常大,几十万肯定不只,几百万至少了 : :【 在 SEKKA (努力备考中......) 的大作中提到: 】 : :: too optimistic,你怎么知道你的一个group会/不会cover k个值? : :: :我大概明白了 : :: :heap没有错
|
|
|
z****e 发帖数: 54598 | 51 我觉得可以,我面肯定过了
【在 S***A 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得这道题你说出O(n)的算法就行了吧。 : : :假设当然是k<<n啦 : :k非常小,比如10,20这种 : :n非常大,几十万肯定不只,几百万至少了 : :【 在 SEKKA (努力备考中......) 的大作中提到: 】 : :: too optimistic,你怎么知道你的一个group会/不会cover k个值? : :: :我大概明白了 : :: :heap没有错 : ……
|
L***s 发帖数: 1148 | |