Re: 国内的婚姻真是毁人三观啊 (转载) - 未名空间MITBBS历史存档

Re: 国内的婚姻真是毁人三观啊 (转载)# Joke - 肚皮舞运动

f*22013-06-13 07:06

1 楼

M个数放到了N个数组里，每个数组都是升序，长度不一
找第K个最小的元素
我这是最近面到的。
我首先抛出了找K的经典解法， Selection Algorithm + Median of Medians, 当然它
是针对一个无序的数组。如果每个数组都比K长，我可以取每个数组的前K个，视它为一
个一维无序数组。这个给否了。
我又抛出 Median of Two Sorted Arrays, 分4区，然后抛弃1区的解法，给否了。
我又抛出海量数据处理Top-K的典型解法， Max-Heap，假如数组非常大。给否了。
大家有木有好方法，有一点要注意的是，分析K相对于数组长度，解法也许不同。

p*i2013-06-13 07:06

2 楼

刚搬来湾区，在一个欧洲小公司做engineer，感觉同事老板都比较注重仪容。请教哪里
的美容院又好又实惠的？简单清洁护理就好。还有请推荐好的发屋或者师傅。好的服饰
小店也需要。可爱的就算了，30了，需要大方，职业，干练型。谢谢。还有我住南湾。

J*n2013-06-13 07:06

3 楼

【以下文字转载自 WaterWorld 讨论区】
发信人: urbanhunter (纵横四海), 信区: WaterWorld
标题: Re: 国内的婚姻真是毁人三观啊
发信站: BBS 未名空间站 (Wed Jun 12 17:00:36 2013, 美东)
的确毁三观，要是在古代，这个表妹估计就嫁给你了。

k*t2013-06-13 07:06

4 楼

用N个指针＋min_heap＋counter，N个指针一开始都指向每个数组的第一个元素，并把N
个指针对应的值放到min_heap, 产生一个最小的值，
do {pop, 同时找出pop出去元素所在的数组，++counter, 该数组的当前指针再往前移
动一位，并把该指针的值放入min_heap} 直到counter等于k。这个方法相对于max_heap
的好处就是不需要将M个数都放到heap中去。说不定还有更好的解法，等待牛人解答。

n*y2013-06-13 07:06

5 楼

never too late to be cute...

l*y2013-06-13 07:06

6 楼

我就看见俩字 “嫉妒”

p*22013-06-13 07:06

7 楼

把N
heap
如果K＝＝M？

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

: 用N个指针＋min_heap＋counter，N个指针一开始都指向每个数组的第一个元素，并把N
: 个指针对应的值放到min_heap, 产生一个最小的值，
: do {pop, 同时找出pop出去元素所在的数组，++counter, 该数组的当前指针再往前移
: 动一位，并把该指针的值放入min_heap} 直到counter等于k。这个方法相对于max_heap
: 的好处就是不需要将M个数都放到heap中去。说不定还有更好的解法，等待牛人解答。

p*i2013-06-13 07:06

8 楼

有没有建议啊，好像没人气咧。湾区美女们去哪美容？

k*22013-06-13 07:06

9 楼

用过两年的dfbb和用过十几年的法拉利，还真说不定谁更值钱。

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

: 【以下文字转载自 WaterWorld 讨论区】
: 发信人: urbanhunter (纵横四海), 信区: WaterWorld
: 标题: Re: 国内的婚姻真是毁人三观啊
: 发信站: BBS 未名空间站 (Wed Jun 12 17:00:36 2013, 美东)
: 的确毁三观，要是在古代，这个表妹估计就嫁给你了。

c*p2013-06-13 07:06

10 楼

Mark

l*32013-06-13 07:06

11 楼

奶奶们估计提供不了什么可行性建议，
不一定非要去美容院呀，自己平时多注意点就行了。不过发型非常重要。。

k*t2013-06-13 07:06

12 楼

这个方法还是linear的。突然想起来有个求kth element of two sorted elements的题
, 比较优的方法用binary search的方法做的，感觉可以借鉴binary search的方法。不
知是否好点啦。

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

:
: 把N
: heap
: 如果K＝＝M？

h*y2013-06-13 07:06

13 楼

阿姨级别的，估计也不用了
哈哈

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

: 奶奶们估计提供不了什么可行性建议，
: 不一定非要去美容院呀，自己平时多注意点就行了。不过发型非常重要。。

p*22013-06-13 07:06

14 楼

有可能。不过代码不太好写呀。

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

: 这个方法还是linear的。突然想起来有个求kth element of two sorted elements的题
: , 比较优的方法用binary search的方法做的，感觉可以借鉴binary search的方法。不
: 知是否好点啦。

k*t2013-06-13 07:06

15 楼

大华边上的花想蓉可以吧.

s*52013-06-13 07:06

16 楼

maxheap也不需要把数都放进去啊。放k个就行。

把N
heap

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

: 用N个指针＋min_heap＋counter，N个指针一开始都指向每个数组的第一个元素，并把N
: 个指针对应的值放到min_heap, 产生一个最小的值，
: do {pop, 同时找出pop出去元素所在的数组，++counter, 该数组的当前指针再往前移
: 动一位，并把该指针的值放入min_heap} 直到counter等于k。这个方法相对于max_heap
: 的好处就是不需要将M个数都放到heap中去。说不定还有更好的解法，等待牛人解答。

m*r2013-06-13 07:06

17 楼

http://www.yelp.com/biz/nan-el-beauty-care-cupertino
我用来用去，什么花想容等等，比较过4家，这家是里面比较好的，服务质量一直有保
证，
其他的地方要么是按摩时间很短，不充分，要么是没有真正用好的product敷面膜。有
一家台湾开的，在milpitas，甚至用我的美丽日记来敷脸，还贼贵。花想容的那家，
用国内产的一个没有注册商标的牌子，不知道广东什么地方产的伪劣产品。

k*t2013-06-13 07:06

18 楼

确实。继续求更好的方法

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

:
: 有可能。不过代码不太好写呀。

T*J2013-06-13 07:06

19 楼

奔个吧，妹妹，一定会收到很多好的建议的，姐妹阿姨奶奶见了照片自然就话多了
，呵呵

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

: 刚搬来湾区，在一个欧洲小公司做engineer，感觉同事老板都比较注重仪容。请教哪里
: 的美容院又好又实惠的？简单清洁护理就好。还有请推荐好的发屋或者师傅。好的服饰
: 小店也需要。可爱的就算了，30了，需要大方，职业，干练型。谢谢。还有我住南湾。

a*u2013-06-13 07:06

20 楼

sorted!这么重要的条件，你的方法一方法三都没有用！
应该用类似merge sorted array/linkedlist的一个方法，用一个size为N的min heap,
时间复杂度O(k)

p*i2013-06-13 07:06

21 楼

是叫采意的那家吗？我路过要过名片，价格看起来不算很贵，还没试过，是你说的那家
么？

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

: http://www.yelp.com/biz/nan-el-beauty-care-cupertino
: 我用来用去，什么花想容等等，比较过4家，这家是里面比较好的，服务质量一直有保
: 证，
: 其他的地方要么是按摩时间很短，不充分，要么是没有真正用好的product敷面膜。有
: 一家台湾开的，在milpitas，甚至用我的美丽日记来敷脸，还贼贵。花想容的那家，
: 用国内产的一个没有注册商标的牌子，不知道广东什么地方产的伪劣产品。

a*u2013-06-13 07:06

22 楼

我说的就这个方法。面试的时候这个方法就够用了，如果有更好的当然是bonus，这个
都没给出来就想更fancy的方法就不合适了。

把N
heap

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

: 用N个指针＋min_heap＋counter，N个指针一开始都指向每个数组的第一个元素，并把N
: 个指针对应的值放到min_heap, 产生一个最小的值，
: do {pop, 同时找出pop出去元素所在的数组，++counter, 该数组的当前指针再往前移
: 动一位，并把该指针的值放入min_heap} 直到counter等于k。这个方法相对于max_heap
: 的好处就是不需要将M个数都放到heap中去。说不定还有更好的解法，等待牛人解答。

p*i2013-06-13 07:06

23 楼

那发型屋有什么好推荐？

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

: 奶奶们估计提供不了什么可行性建议，
: 不一定非要去美容院呀，自己平时多注意点就行了。不过发型非常重要。。

f*22013-06-13 07:06

24 楼

我要是面人，觉得答出这个也就行了。这个hirING Bar是有点高。
提过用heap，不过还没说完就给直接否定了。显然不是他想要的，应该还有最优的，
可能是分治，某种分治。
你说的这个大致是 O（K*logK）time， O（K) space, for the heap of size K.
讨论讨论K相对M的情况。。。有没有新点子。
==
我说的就这个方法。面试的时候这个方法就够用了，如果有更好的当然是bonus，这个
都没给出来就想更fancy的方法就不合适了。

把N
heap

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

: 用N个指针＋min_heap＋counter，N个指针一开始都指向每个数组的第一个元素，并把N
: 个指针对应的值放到min_heap, 产生一个最小的值，
: do {pop, 同时找出pop出去元素所在的数组，++counter, 该数组的当前指针再往前移
: 动一位，并把该指针的值放入min_heap} 直到counter等于k。这个方法相对于max_heap
: 的好处就是不需要将M个数都放到heap中去。说不定还有更好的解法，等待牛人解答。

s*n2013-06-13 07:06

25 楼

真是人跟人不一样
俺以前的大老板是英国人，那个不讲究
天天都是khaki裤子加一件白色短袖衬衫，
而且一买买5套，一个星期5天轮流换
不知道的还以为他每天都穿同一件衣服
他自己都说，衣服没必要那么讲究
能穿不破不脏不暴露就行了
engineer需要穿那么正式么？再怎么讲究
也就头发干净点，穿上面business casual
怎么也够了吧，难道还天天business suit？
又不是marketing需要见客户

f*22013-06-13 07:06

26 楼

K很小，min heap, O（K*logK）time 是可行的，
K接近M，视为无序一维的，median of medians, O(M) 更好。
这些讨论是假设单机内存可以装得下M。征更好的解。。

，

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

: 我要是面人，觉得答出这个也就行了。这个hirING Bar是有点高。
: 提过用heap，不过还没说完就给直接否定了。显然不是他想要的，应该还有最优的，
: 可能是分治，某种分治。
: 你说的这个大致是 O（K*logK）time， O（K) space, for the heap of size K.
: 讨论讨论K相对M的情况。。。有没有新点子。
: ==
: 我说的就这个方法。面试的时候这个方法就够用了，如果有更好的当然是bonus，这个
: 都没给出来就想更fancy的方法就不合适了。
:
: 把N

a*u2013-06-13 07:06

27 楼

你好像理解错了，heap size是N，不是K，你再仔细看一下

，

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

: 我要是面人，觉得答出这个也就行了。这个hirING Bar是有点高。
: 提过用heap，不过还没说完就给直接否定了。显然不是他想要的，应该还有最优的，
: 可能是分治，某种分治。
: 你说的这个大致是 O（K*logK）time， O（K) space, for the heap of size K.
: 讨论讨论K相对M的情况。。。有没有新点子。
: ==
: 我说的就这个方法。面试的时候这个方法就够用了，如果有更好的当然是bonus，这个
: 都没给出来就想更fancy的方法就不合适了。
:
: 把N

e*82013-06-13 07:06

28 楼

这题我记得programming problems上好象有(selection in big data)

f*22013-06-13 07:06

29 楼

展开说说？这是书吗？

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

: 这题我记得programming problems上好象有(selection in big data)

f*22013-06-13 07:06

30 楼

谢谢纠正

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

: 你好像理解错了，heap size是N，不是K，你再仔细看一下
:
: ，

f*22013-06-13 07:06

31 楼

说详细点？

有可能。不过代码不太好写呀。

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

: 这个方法还是linear的。突然想起来有个求kth element of two sorted elements的题
: , 比较优的方法用binary search的方法做的，感觉可以借鉴binary search的方法。不
: 知是否好点啦。

s*n2013-06-13 07:06

32 楼

Mark

g*e2013-06-13 07:06

33 楼

master node随机选个数t，发送给slave nodes，每个node找出比t小的个数返回master
node。如果加起来等于K，结束。否则抛弃一半，继续找。
这算法没意思，应该直接引申到怎么从n个node选master node的leader election设计
。当然像半海大牛那样直接说zookeeper就完事了

的题
。不

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

: 说详细点？
:
: 有可能。不过代码不太好写呀。

z*e2013-06-13 07:06

34 楼

原来是变形的mapreduce题呀
一开始被一堆数组迷惑了，还以为是算法题呢

master

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

: master node随机选个数t，发送给slave nodes，每个node找出比t小的个数返回master
: node。如果加起来等于K，结束。否则抛弃一半，继续找。
: 这算法没意思，应该直接引申到怎么从n个node选master node的leader election设计
: 。当然像半海大牛那样直接说zookeeper就完事了
:
: 的题
: 。不

h*p2013-06-13 07:06

35 楼

mark