男猫就是比女猫大方 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>pets - 心有所宠

男猫就是比女猫大方

男猫就是比女猫大方# pets - 心有所宠

i*e2010-05-30 07:05

1 楼

最近非常热门的一道 google 题，大家讨论讨论.
Two reverse sorted arrays A and B have been given.
such that size of A is m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B. such that k < m*n
本版又讨论过，但是好像没什么结果。
http://www.mitbbs.com/article_t/JobHunting/31684697.html
这题其实可以转换成另外以下的题目（杨式矩阵）：
Given a N*N Matrix.
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.
我想到一个利用堆的解法，可以达到 O(k log min(m, n)).
但看网上 google 要求的最优解法好像是 O(n).
不知道各位大侠有没有任何好的思路.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

u*r2010-05-30 07:05

2 楼

请问用AMEX买iPhone, iPad3会给多一年的warranty么？
谢谢指点！

Y*i2010-05-30 07:05

3 楼

昨天晚上去别人家作客,大概５个月前我去过他们家,当时看到他们家的一对兄妹奶猫,
大概５－６个月大吧,当时两孩子都被妈妈抱出来,很紧张，性格上都差不多.昨天去了,
两孩子都成大猫了,性格上的差异一下子就看出来了.我们进门,就看见男孩子过来迎接
我们,一点都不shy，跟着我们走来走去,还任你抱任你摸的.我问女孩子呢?主人说,很害
羞,在楼上躲着呢.然后我们在他们家差不多５个小时的时间里,男猫一直和我们很
social，女猫唯一露面在我们大家玩气球的时候,大概前后不到５分钟,就又回闺房去躲
着了,真是千金大小姐呀.

g*s2010-05-30 07:05

4 楼

为什么要reverse sorted?

b is

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

: 最近非常热门的一道 google 题，大家讨论讨论.
: Two reverse sorted arrays A and B have been given.
: such that size of A is m and size of B is n
: You need to find the k th largest sum (a+b) where a is taken from A and b is
: taken from B. such that k < m*n
: 本版又讨论过，但是好像没什么结果。
: http://www.mitbbs.com/article_t/JobHunting/31684697.html
: 这题其实可以转换成另外以下的题目（杨式矩阵）：
: Given a N*N Matrix.
: All rows are sorted, and all columns are sorted.

s*g2010-05-30 07:05

5 楼

should be

t*n2010-05-30 07:05

6 楼

...你来我家就不这么想了....

i*e2010-05-30 07:05

7 楼

这是题目愿意呀。
就是 A 和 B sorted in descending order 的意思。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

: 为什么要reverse sorted?
:
: b is

S*82010-05-30 07:05

8 楼

主要是丢了管赔比较爽

i*p2010-05-30 07:05

9 楼

我家是相反的

g*s2010-05-30 07:05

10 楼

我的意思是说正排序问题应该等价吧。

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

: 这是题目愿意呀。
: 就是 A 和 B sorted in descending order 的意思。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

g*y2010-05-30 07:05

11 楼

why not？

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

: 请问用AMEX买iPhone, iPad3会给多一年的warranty么？
: 谢谢指点！

w*s2010-05-30 07:05

12 楼

我们家2个太监见到生人就躲房子里去了，怎么拖都拖不出来

了,

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

: 昨天晚上去别人家作客,大概５个月前我去过他们家,当时看到他们家的一对兄妹奶猫,
: 大概５－６个月大吧,当时两孩子都被妈妈抱出来,很紧张，性格上都差不多.昨天去了,
: 两孩子都成大猫了,性格上的差异一下子就看出来了.我们进门,就看见男孩子过来迎接
: 我们,一点都不shy，跟着我们走来走去,还任你抱任你摸的.我问女孩子呢?主人说,很害
: 羞,在楼上躲着呢.然后我们在他们家差不多５个小时的时间里,男猫一直和我们很
: social，女猫唯一露面在我们大家玩气球的时候,大概前后不到５分钟,就又回闺房去躲
: 着了,真是千金大小姐呀.

i*e2010-05-30 07:05

13 楼

哦，原来这个意思。
是的，都一样是等价的。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

: 我的意思是说正排序问题应该等价吧。

b*22010-05-30 07:05

14 楼

这个怎么证明，另外，如果屏幕跌坏了也管赔吗？

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

: 主要是丢了管赔比较爽

p*f2010-05-30 07:05

15 楼

我家两个都是迎送型的，无论生熟男女。

i*e2010-05-30 07:05

16 楼

My solution using a heap and an array that maps indices from A to B.
const int MAX_M = 100;
const int MAX_N = 100;
typedef pair Pair;
int findKthLargestSum(int A[], int m, int B[], int n, int k) {
priority_queue Q;
int AToB[MAX_M] = {0}; // keep track of each col's indices that's
traversed.
// pushes all elements of the first row into heap
for (int i = 0; i < m; i++)
Q.push(Pair(A[i]+B[0], i));
// loop k-1 times to find the first k-1 elements
for (int i = 0; i < k-1; i++) {
Pair largest = Q.top();
Q.pop();
AToB[largest.second]++;
// push its next element in the current col (next row)
if (AToB[largest.second] < n)
Q.push(Pair(A[largest.second]+B[AToB[largest.second]], largest.second));
}
return Q.top().first;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

S*82010-05-30 07:05

17 楼

有police report就可以一般，摔坏了就不知道了，恐怕不管

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

: 这个怎么证明，另外，如果屏幕跌坏了也管赔吗？

o*e2010-05-30 07:05

18 楼

女猫很乖。男猫既胆小又不亲人。

了,

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

j*e2010-05-30 07:05

19 楼

How about trying to find the kth smallest element
in the N*N matrix?
If you draw a line from
A[1, k] to A[k,1] in the matrix, would the kth smallest element sit
somewhere on this line?
For example, will the 4th smallest element will be among
a[4,1], a[3,2], a[2,3], a[1,4]?

a*42010-05-30 07:05

20 楼

原价一定可以，要是iphone $199+两年合同恐怕不行

s*o2010-05-30 07:05

21 楼

我们家也是，男猫kitty看到陌生人就蹭，女猫听到开门声就躲床底下。。。

i*e2010-05-30 07:05

22 楼

To answer your question, No.
Counter example:
A = [9 8 7 6]
B = [9 7 2 1]
9 8 7 1
9 18 17 16 10
7 16 15 14 8
2 11 10 9 3
1 10 9 8 2
The 4th element (16) is not on any of A[4,1], a[3,2], a[2,3], a[1,4].
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

z*i2010-05-30 07:05

23 楼

可以的
我master card iphone 199 都cover

m*t2010-05-30 07:05

24 楼

我家是反的啊。

f*42010-05-30 07:05

25 楼

原帖里说有O(1)的解法真是太弓虽了。。。

a*y2010-05-30 07:05

26 楼

我家豆是，对男的来客都很大方，过去闻闻加蹭腿，老沉着了
可一见女的就不成了，害羞的赶紧往家躲

d*c2010-05-30 07:05

27 楼

这有篇paper提到了这个问题：
http://www.springerlink.com/content/ph106337753883w3/

s*o2010-05-30 07:05

28 楼

想起来上次家里来客人，一个人很怕猫，kitty那叫蹭的起劲啊，走哪跟哪。另一个人
很喜欢猫，刚想去碰碰kitty，就被咬了口。。。

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

: 我家豆是，对男的来客都很大方，过去闻闻加蹭腿，老沉着了
: 可一见女的就不成了，害羞的赶紧往家躲

a*y2010-05-30 07:05

29 楼

读过的一个vet写的关于猫的文章
里面回答的一个疑问就是，为什么有时候猫反而会主动去亲近那些不喜欢猫的人？
那个vet的解释是，不喜欢猫的人会忽略它们，不会特意去看猫或者凑过去，所以猫猫
会将这种肢体语言误解为对它们的喜爱
相反那些爱猫人可能过于激动，会一直盯着看，甚至想摸，猫会把eye contact和伸手
定义为攻击的信号，所以反而会紧张和攻击人

【在 s*******o 的大作中提到】

: 想起来上次家里来客人，一个人很怕猫，kitty那叫蹭的起劲啊，走哪跟哪。另一个人
: 很喜欢猫，刚想去碰碰kitty，就被咬了口。。。

s*o2010-05-30 07:05

30 楼

很奇怪的是，上次我带他去vet那，就用leash栓着，很多人过来摸他，他也蹭别人。

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

: 读过的一个vet写的关于猫的文章
: 里面回答的一个疑问就是，为什么有时候猫反而会主动去亲近那些不喜欢猫的人？
: 那个vet的解释是，不喜欢猫的人会忽略它们，不会特意去看猫或者凑过去，所以猫猫
: 会将这种肢体语言误解为对它们的喜爱
: 相反那些爱猫人可能过于激动，会一直盯着看，甚至想摸，猫会把eye contact和伸手
: 定义为攻击的信号，所以反而会紧张和攻击人

a*y2010-05-30 07:05

31 楼

呵呵，是因为有leash束缚吗？或者气氛不同:)
反正这个解释不是每猫适用
俺家小豆就有他自己的判断方法

【在 s*******o 的大作中提到】

: 很奇怪的是，上次我带他去vet那，就用leash栓着，很多人过来摸他，他也蹭别人。