a******t
发帖数: 34 | 1 given an array of n elements, find if there is a subset of 3 elements sum up
to value T
with time complexity O(nlgn).
Given a M*N matrix A in which all the elements in a row and all the elements
in a column are strictly
increasing. Find a path from the smallest element (ie A[0][0]) to the
largest element (ie A[M-1][N-1])
such that the sum of the elements in the path is maximum. Time Complexity O(
m+n). Use efficient space. |
g*******y
发帖数: 1930 | 2 貌似两个都做不出来的。
up
elements
O(
【在 a******t 的大作中提到】
: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T
: with time complexity O(nlgn).
: Given a M*N matrix A in which all the elements in a row and all the elements
: in a column are strictly
: increasing. Find a path from the smallest element (ie A[0][0]) to the
: largest element (ie A[M-1][N-1])
: such that the sum of the elements in the path is maximum. Time Complexity O(
: m+n). Use efficient space.
|
G**********s
发帖数: 70 | 3 1.版上讨论过，n^2 最佳了，nlgn不可能的
2.两边之和大于第三边，所以途径最多点的就是maximum把。 |
a******t
发帖数: 34 | 4 小尾羊
首先谢谢你的回答。
再次祝贺拿到Google offer. |
s*****i
发帖数: 355 | 5 第一题能用辅助hashmap吗？排序以后两指针一头一尾，用T减去这两个数的和，查询差
值是不是在hashmap里
up
elements
O(
【在 a******t 的大作中提到】
: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T
: with time complexity O(nlgn).
: Given a M*N matrix A in which all the elements in a row and all the elements
: in a column are strictly
: increasing. Find a path from the smallest element (ie A[0][0]) to the
: largest element (ie A[M-1][N-1])
: such that the sum of the elements in the path is maximum. Time Complexity O(
: m+n). Use efficient space.
|
B*****t
发帖数: 335 | 6 1. O(nlgn) can be achieved by using FFT under some conditions. But generally
the best algorithm to find a subset of 3 elements sum up
to a given value T is O(n^2). The relationship is like radix sort vs quick
sort. But I doubt the interviewers from MS would ask such kind of questions.
2. I don't think there is such kind of algorithms with O(m+n) complexity. |
t*********n
发帖数: 1292 | |
h**k
发帖数: 3368 | 8
这里需要考虑任何两个数的和，所以复杂度是O(n*n)
【在 s*****i 的大作中提到】
: 第一题能用辅助hashmap吗？排序以后两指针一头一尾，用T减去这两个数的和，查询差
: 值是不是在hashmap里
:
: up
: elements
: O(
|
b****r
发帖数: 1272 | 9 2. 只想到dp O(m*n)
有更好的法子？
up
elements
O(
【在 a******t 的大作中提到】
: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T
: with time complexity O(nlgn).
: Given a M*N matrix A in which all the elements in a row and all the elements
: in a column are strictly
: increasing. Find a path from the smallest element (ie A[0][0]) to the
: largest element (ie A[M-1][N-1])
: such that the sum of the elements in the path is maximum. Time Complexity O(
: m+n). Use efficient space.
|
c******f
发帖数: 2144 | |
h*******x
发帖数: 12808 | 11 第一题，排序一下，是nlogn，然后用n次找两个数和为T-n3的算法，但是这样是n^2啊
？谁知道nlogn的啊
up
elements
O(
【在 a******t 的大作中提到】
: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T
: with time complexity O(nlgn).
: Given a M*N matrix A in which all the elements in a row and all the elements
: in a column are strictly
: increasing. Find a path from the smallest element (ie A[0][0]) to the
: largest element (ie A[M-1][N-1])
: such that the sum of the elements in the path is maximum. Time Complexity O(
: m+n). Use efficient space.
|
