i**********e
发帖数: 1145 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: ihasleetcode (1337coder), 信区: JobHunting
标 题: 一道热门的 Google 面试题
发信站: BBS 未名空间站 (Thu Jan 27 21:06:18 2011, 美东)
最近非常热门的一道 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 |
z****e
发帖数: 2024 | 2 你说得那个样式矩阵的题是O(n).因为不是sum的kth，而是矩阵元素的kth。也不用什么
算法，拐几个弯一直找到底就行了。
但是那个sum（a，b）如何O(n)? |
g**e
发帖数: 6127 | 3 search 是拐弯找吧，找矩阵kth怎么拐弯找？
这个sum(a,b)就可以转换成杨氏矩阵，特殊的地方在于行与行，列与列直接的差是固定
的，
如果没这个特殊条件，应该不可能O(n)
【在 z****e 的大作中提到】
: 你说得那个样式矩阵的题是O(n).因为不是sum的kth，而是矩阵元素的kth。也不用什么
: 算法，拐几个弯一直找到底就行了。
: 但是那个sum（a，b）如何O(n)?
|
z****e
发帖数: 2024 | 4 k如果不算const的话，是不能O(n).
Ytable的extract-min操作本身就是线性。
【在 g**e 的大作中提到】
: search 是拐弯找吧，找矩阵kth怎么拐弯找？
: 这个sum(a,b)就可以转换成杨氏矩阵，特殊的地方在于行与行，列与列直接的差是固定
: 的，
: 如果没这个特殊条件，应该不可能O(n)
|
g**e
发帖数: 6127 | 5 k=m*n吧，不能算线性。如果extract min k次，复杂度是o(k(m+n))吧
但是这是个特殊的杨氏矩阵，但是想不出来该怎么利用。
【在 z****e 的大作中提到】
: k如果不算const的话，是不能O(n).
: Ytable的extract-min操作本身就是线性。
|
g*********s
发帖数: 1782 | 6 怎么转换成杨矩的？
【在 g**e 的大作中提到】
: k=m*n吧，不能算线性。如果extract min k次，复杂度是o(k(m+n))吧
: 但是这是个特殊的杨氏矩阵，但是想不出来该怎么利用。
|
z****e
发帖数: 2024 | 7 sum(a,b)就是。
【在 g*********s 的大作中提到】
: 怎么转换成杨矩的？
|
g*********s
发帖数: 1782 | 8 那这个转换过程不就是M*N吗？
【在 z****e 的大作中提到】
: sum(a,b)就是。
|
z****e
发帖数: 2024 | 9 不需要都算出来的。lazyevaluation。
【在 g*********s 的大作中提到】
: 那这个转换过程不就是M*N吗？
|
h********e
发帖数: 1972 | 10 这题是能O(n)的。。但我能想到的是一片80年代的stoc paper，。前面提到这个sum用
矩阵表示，就是个行单调和列单调矩阵。这种矩阵里面找第k大数能用线性时间i.e., O
(矩阵变长的和)。算法我记得是个分治。很tricky。证明大概有5页。5年前国内有个
google的人拿这个矩阵而不是sum的题目来问我，叫我给他个简单解法做答案，我知道
那片论文，比较无语，跟他说没法做。。那个拐几个弯的方法，是求矩阵里面是否存在
一个数k，而不是求第k大。
显然google要的不是这种解，，，我们现在从两个数组得到的矩阵比单调矩阵来的更多
信息。努力想想应该有比较容易的方法做出来。 |
|
|
Y**r
发帖数: 88 | 11 // my pseudo code
// recursively find k
// A, B are the two arrays
MaxPair findMax(int k)
{
if (k==1) return {0, 0};
{x, y} = findMax(k-1);
if (A[x] + B[y+1]) < (A[x+1] + B[y])
{
return {x+1, y};
}
else
{
return {x, y+1};
}
}
|
i**********e
发帖数: 1145 | 12 【 以下文字转载自 JobHunting 讨论区 】
发信人: ihasleetcode (1337coder), 信区: JobHunting
标 题: 一道热门的 Google 面试题
发信站: BBS 未名空间站 (Thu Jan 27 21:06:18 2011, 美东)
最近非常热门的一道 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 |
z****e
发帖数: 2024 | 13 你说得那个样式矩阵的题是O(n).因为不是sum的kth，而是矩阵元素的kth。也不用什么
算法，拐几个弯一直找到底就行了。
但是那个sum（a，b）如何O(n)? |
g**e
发帖数: 6127 | 14 search 是拐弯找吧，找矩阵kth怎么拐弯找？
这个sum(a,b)就可以转换成杨氏矩阵，特殊的地方在于行与行，列与列直接的差是固定
的，
如果没这个特殊条件，应该不可能O(n)
【在 z****e 的大作中提到】
: 你说得那个样式矩阵的题是O(n).因为不是sum的kth，而是矩阵元素的kth。也不用什么
: 算法，拐几个弯一直找到底就行了。
: 但是那个sum（a，b）如何O(n)?
|
z****e
发帖数: 2024 | 15 k如果不算const的话，是不能O(n).
Ytable的extract-min操作本身就是线性。
【在 g**e 的大作中提到】
: search 是拐弯找吧，找矩阵kth怎么拐弯找？
: 这个sum(a,b)就可以转换成杨氏矩阵，特殊的地方在于行与行，列与列直接的差是固定
: 的，
: 如果没这个特殊条件，应该不可能O(n)
|
g**e
发帖数: 6127 | 16 k=m*n吧，不能算线性。如果extract min k次，复杂度是o(k(m+n))吧
但是这是个特殊的杨氏矩阵，但是想不出来该怎么利用。
【在 z****e 的大作中提到】
: k如果不算const的话，是不能O(n).
: Ytable的extract-min操作本身就是线性。
|
g*********s
发帖数: 1782 | 17 怎么转换成杨矩的？
【在 g**e 的大作中提到】
: k=m*n吧，不能算线性。如果extract min k次，复杂度是o(k(m+n))吧
: 但是这是个特殊的杨氏矩阵，但是想不出来该怎么利用。
|
z****e
发帖数: 2024 | 18 sum(a,b)就是。
【在 g*********s 的大作中提到】
: 怎么转换成杨矩的？
|
g*********s
发帖数: 1782 | 19 那这个转换过程不就是M*N吗？
【在 z****e 的大作中提到】
: sum(a,b)就是。
|
z****e
发帖数: 2024 | 20 不需要都算出来的。lazyevaluation。
【在 g*********s 的大作中提到】
: 那这个转换过程不就是M*N吗？
|
|
|
h********e
发帖数: 1972 | 21 这题是能O(n)的。。但我能想到的是一片80年代的stoc paper，。前面提到这个sum用
矩阵表示，就是个行单调和列单调矩阵。这种矩阵里面找第k大数能用线性时间i.e., O
(矩阵变长的和)。算法我记得是个分治。很tricky。证明大概有5页。5年前国内有个
google的人拿这个矩阵而不是sum的题目来问我，叫我给他个简单解法做答案，我知道
那片论文，比较无语，跟他说没法做。。那个拐几个弯的方法，是求矩阵里面是否存在
一个数k，而不是求第k大。
显然google要的不是这种解，，，我们现在从两个数组得到的矩阵比单调矩阵来的更多
信息。努力想想应该有比较容易的方法做出来。 |
Y**r
发帖数: 88 | 22 // my pseudo code
// recursively find k
// A, B are the two arrays
MaxPair findMax(int k)
{
if (k==1) return {0, 0};
{x, y} = findMax(k-1);
if (A[x] + B[y+1]) < (A[x+1] + B[y])
{
return {x+1, y};
}
else
{
return {x, y+1};
}
}
|
g***l
发帖数: 2753 | 23 google这是在找数学家吗?
O
【在 h********e 的大作中提到】
: 这题是能O(n)的。。但我能想到的是一片80年代的stoc paper，。前面提到这个sum用
: 矩阵表示，就是个行单调和列单调矩阵。这种矩阵里面找第k大数能用线性时间i.e., O
: (矩阵变长的和)。算法我记得是个分治。很tricky。证明大概有5页。5年前国内有个
: google的人拿这个矩阵而不是sum的题目来问我，叫我给他个简单解法做答案，我知道
: 那片论文，比较无语，跟他说没法做。。那个拐几个弯的方法，是求矩阵里面是否存在
: 一个数k，而不是求第k大。
: 显然google要的不是这种解，，，我们现在从两个数组得到的矩阵比单调矩阵来的更多
: 信息。努力想想应该有比较容易的方法做出来。
|
p*********t
发帖数: 2690 | 24 google的博士很多。
【在 g***l 的大作中提到】
: google这是在找数学家吗?
:
: O
|
s*****9
发帖数: 93 | 25 搜了一下有人说是这篇文章：
http://epubs.siam.org/action/showAbstract?page=14&volume=13&iss
O
【在 h********e 的大作中提到】
: 这题是能O(n)的。。但我能想到的是一片80年代的stoc paper，。前面提到这个sum用
: 矩阵表示，就是个行单调和列单调矩阵。这种矩阵里面找第k大数能用线性时间i.e., O
: (矩阵变长的和)。算法我记得是个分治。很tricky。证明大概有5页。5年前国内有个
: google的人拿这个矩阵而不是sum的题目来问我，叫我给他个简单解法做答案，我知道
: 那片论文，比较无语，跟他说没法做。。那个拐几个弯的方法，是求矩阵里面是否存在
: 一个数k，而不是求第k大。
: 显然google要的不是这种解，，，我们现在从两个数组得到的矩阵比单调矩阵来的更多
: 信息。努力想想应该有比较容易的方法做出来。
|
s*****9
发帖数: 93 | 26 我感觉用堆的方法也许就是log(n)的，但是不知道如何能分析证明。
因为感觉堆的size可以始终维持的比较小，入堆和出堆的速率可能用amortized的分析
是大体持平的。
is
【在 i**********e 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: ihasleetcode (1337coder), 信区: JobHunting
: 标 题: 一道热门的 Google 面试题
: 发信站: BBS 未名空间站 (Thu Jan 27 21:06:18 2011, 美东)
: 最近非常热门的一道 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
: 本版又讨论过，但是好像没什么结果。
|
l*********s
发帖数: 5409 | |
b*****n
发帖数: 2324 | 28 这个M*N的矩阵的信息足够多了，每个子矩阵的最小值一定在同一个角，先根据k圈出前
几行加若干个，然后在比较边上的值，比圈进来的最小值大，就把最小值换掉，新的最
小值一定还在这个形状的几个角当中，排列这几个角，再圈，直到圈出来的比圈边界外
的所有相邻值都大，这个局部优化一下应该是能做到O（N)的。对不？
is
【在 i**********e 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: ihasleetcode (1337coder), 信区: JobHunting
: 标 题: 一道热门的 Google 面试题
: 发信站: BBS 未名空间站 (Thu Jan 27 21:06:18 2011, 美东)
: 最近非常热门的一道 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
: 本版又讨论过，但是好像没什么结果。
|
T****e
发帖数: 1072 | 29 我的想法是做一个排序Queue.开始放最大和。去掉队头后把往右往下两分支的数字排序
后放入。使队头永远是当前最大数，队列永远保持排序，这样去掉队头后就可以用二分
法插入新分支的数。
还要保证每个数不被重复加入 |
n******t
发帖数: 4406 | 30 这种东西实际中半点毛用没有。
is
【在 i**********e 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: ihasleetcode (1337coder), 信区: JobHunting
: 标 题: 一道热门的 Google 面试题
: 发信站: BBS 未名空间站 (Thu Jan 27 21:06:18 2011, 美东)
: 最近非常热门的一道 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
: 本版又讨论过，但是好像没什么结果。
|
|
|
c*********t
发帖数: 1861 | 31 merge sort a and b, then find max i and j st i*j |
