x**y
发帖数: 70 | 1 1. 有几百万 NODES IN GRAPH, 用什么数据结构来代表, 各有什么优缺点?
2. N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0
的那一行. 平均O()和 WORST CASE O() 是多少? |
c**j
发帖数: 103 | 2 1. adjacency list? linked list. slower than adj matrix. however too large
for sparse.
2. 类似binary search 思想？ 上一半 sum，下一半sum比，少的一半中有，之后知道
之后再在这半中 divide and conquer? |
x**y
发帖数: 70 | 3 brute force 是扫描每一行,遍历整个 matrix, O(N^2). interviewer 说有更好的. 你
的好像不对, 第一, 扫描多次, 第二, 应该和SUM 无关.
【在 c**j 的大作中提到】
: 1. adjacency list? linked list. slower than adj matrix. however too large
: for sparse.
: 2. 类似binary search 思想？ 上一半 sum，下一半sum比，少的一半中有，之后知道
: 之后再在这半中 divide and conquer?
|
j********x
发帖数: 2330 | 4 第一题主要考虑稀疏图的存储吧，sparse matrix相关的可以看看
第二题，可以考虑random algo；
任选一列，排除有“1”的行；
在余下的行继续这么搞；
复杂度取决于“1”分布的比例；worst case当然是N^2 |
x**y
发帖数: 70 | 5 我当场给的解法是: SORT BY第一个COLUMN, 是 1 的行都不用考虑了, 在是 0 的行里
再SORT BY 第二个COLUMN, 是 1 的行也不用再考虑了... 假设平均每次能排除一半行
数, 整个要用 n*logn + n/2*log(n/2) + n/4 * log(n/4) + ... + 1 operations.因
为不用扫描所有的 ENTRY, 所以平均应该比 O(N^2) 好. 但不确定这个类似等比数列求
和最后是 nlogn 吗?
【在 j********x 的大作中提到】
: 第一题主要考虑稀疏图的存储吧，sparse matrix相关的可以看看
: 第二题，可以考虑random algo；
: 任选一列，排除有“1”的行；
: 在余下的行继续这么搞；
: 复杂度取决于“1”分布的比例；worst case当然是N^2
|
x**y
发帖数: 70 | 6 换句话说,
O() = n*logn + n/2*log(n/2) + n/4 * log(n/4) + ... + 1
最后是 O(nlogn) 吗?
类似思想: 找 kth largest element in int array 是:
n + n/2 + n/4 + ... 1
最后是 O(N)
【在 x**y 的大作中提到】
: 我当场给的解法是: SORT BY第一个COLUMN, 是 1 的行都不用考虑了, 在是 0 的行里
: 再SORT BY 第二个COLUMN, 是 1 的行也不用再考虑了... 假设平均每次能排除一半行
: 数, 整个要用 n*logn + n/2*log(n/2) + n/4 * log(n/4) + ... + 1 operations.因
: 为不用扫描所有的 ENTRY, 所以平均应该比 O(N^2) 好. 但不确定这个类似等比数列求
: 和最后是 nlogn 吗?
|
k*p
发帖数: 1526 | 7 sort by第一个column不如直接scan，留下0的，只要O(n)啊
【在 x**y 的大作中提到】
: 我当场给的解法是: SORT BY第一个COLUMN, 是 1 的行都不用考虑了, 在是 0 的行里
: 再SORT BY 第二个COLUMN, 是 1 的行也不用再考虑了... 假设平均每次能排除一半行
: 数, 整个要用 n*logn + n/2*log(n/2) + n/4 * log(n/4) + ... + 1 operations.因
: 为不用扫描所有的 ENTRY, 所以平均应该比 O(N^2) 好. 但不确定这个类似等比数列求
: 和最后是 nlogn 吗?
|
x**y
发帖数: 70 | 8 那你扫描第二个 column 不又要看N个元素, 变成 O(N^2) 啊!?
【在 k*p 的大作中提到】
: sort by第一个column不如直接scan，留下0的，只要O(n)啊
|
x**y
发帖数: 70 | 9 我觉得只有SORT后, 你才知道什么时候STOP, 然后移到下一个COLUNM. 否则, 你还是要
扫描一个COLUMN的所有元素.
【在 k*p 的大作中提到】
: sort by第一个column不如直接scan，留下0的，只要O(n)啊
|
k*p
发帖数: 1526 | 10 你sort不也要扫描当前column剩下的所有元素么？
你假设有一半非零，所以得到1/2nlog(1/2 n)
那我也可以做同样假设，这样scan第二列只有1/2n
【在 x**y 的大作中提到】
: 我觉得只有SORT后, 你才知道什么时候STOP, 然后移到下一个COLUNM. 否则, 你还是要
: 扫描一个COLUMN的所有元素.
|
|
|
x**y
发帖数: 70 | 11 不需要. 只要碰到 1, 就知道剩下的都是 1 啦. 如果你不SORT, 除非你建立新2D
array (n/2 by n), 你还是要在原始 N*N array 里看第二列所有元素啊.
【在 k*p 的大作中提到】
: 你sort不也要扫描当前column剩下的所有元素么？
: 你假设有一半非零，所以得到1/2nlog(1/2 n)
: 那我也可以做同样假设，这样scan第二列只有1/2n
|
j****a
发帖数: 55 | 12 我的想法是先matrix multiply一下，之后就scan n就好了，前提是，matrix multiply
比scan快. Theoretically that's not true, but in practice it might be. Some
machines (GPU) are built to do matrix multiplications. |
x**y
发帖数: 70 | 13 好像你的方法不是正解. 我当时的解法, INTERVIEWER 没说错, 只是让我分析O(). 当时
under pressure, 心想比N^2好的, 只能是 nlogn. 现在想想, 那我得证明 average
case: nlogn + n/2log(n/2) + n/4log(n/4) + ... + 1 ==> O(nlogn).
按理说, 电面题应该不是太难, 有牛牛知道这题标准解法吗?
multiply
【在 j****a 的大作中提到】
: 我的想法是先matrix multiply一下，之后就scan n就好了，前提是，matrix multiply
: 比scan快. Theoretically that's not true, but in practice it might be. Some
: machines (GPU) are built to do matrix multiplications.
|
k*p
发帖数: 1526 | 14 我的point是，你的sort需要nlogn，不是sort完看1或0
【在 x**y 的大作中提到】
: 不需要. 只要碰到 1, 就知道剩下的都是 1 啦. 如果你不SORT, 除非你建立新2D
: array (n/2 by n), 你还是要在原始 N*N array 里看第二列所有元素啊.
|
x**y
发帖数: 70 | 15 sorting by first column needs to consider n elements, but sorting by second
column only needs to consider the (already sorted) rows whose first element
is 0. You sort on less elements each time -- that's my idea.
【在 k*p 的大作中提到】
: 我的point是，你的sort需要nlogn，不是sort完看1或0
|
b****n
发帖数: 84 | 16 只有0/1的话，sort是O(n)
【在 k*p 的大作中提到】
: 我的point是，你的sort需要nlogn，不是sort完看1或0
|
r******d
发帖数: 308 | 17 把每一行转成一个二进制度的数， 看这个数是不是等于0?
不过前提是那个数组已经放在一个string 数组里面了
或者XOR每一列的所有数字， 看看哪行总是保持在0? |
x**y
发帖数: 70 | 18 This is a good point, now I think overall average case is n + n/2 + n/4 + ..
. + 1 ==> O(N)!
【在 b****n 的大作中提到】
: 只有0/1的话，sort是O(n)
|
s********k
发帖数: 6180 | 19 这题有这么复杂吗？while （！（one row|0）） return else next row
最坏O(N),最好O(1)吧
【在 b****n 的大作中提到】
: 只有0/1的话，sort是O(n)
|
x**y
发帖数: 70 | 20 看题不仔细. 是 N*N MATRIX. 你的方法最坏和平均都是O(N^2).
【在 s********k 的大作中提到】
: 这题有这么复杂吗？while （！（one row|0）） return else next row
: 最坏O(N),最好O(1)吧
|
|
|
s*******r
发帖数: 47 | 21 应该是的,最坏情况是O(n*n). 但sort显然需要额外的空间。
【在 b****n 的大作中提到】
: 只有0/1的话，sort是O(n)
|
d****j
发帖数: 293 | 22 Sort的话不如直接弄个Set来表示目前candidate行的行号
刚开始，1-N个数全放进去
扫描第一列，检查Set的(行号,第一列)是否为1，是就删掉
扫描第二列，检查Set中剩下的行号的第二列是否为1，是就删掉
....
如果每次能删掉1/2的话，复杂度不就是
(N + N/2 + N/4 + N/8 +....)*O(set_operation) = 2N*O(set_operation)
Set如果用hash实现，查找删除就是O(1), 总共就是O(N)
如果用BST实现，总共就是O(NlgN) |
f***g
发帖数: 214 | 23 同意，不用sort
但是用Queue来记录还需要检查的行号。
一开始1......n入队。
第一遍，扫描第一列，如果为1，抛弃，如果为0，重新加到对尾。
以此类推。直到Queue的size为1.
时间O(n)
空间O(n)
【在 d****j 的大作中提到】
: Sort的话不如直接弄个Set来表示目前candidate行的行号
: 刚开始，1-N个数全放进去
: 扫描第一列，检查Set的(行号,第一列)是否为1，是就删掉
: 扫描第二列，检查Set中剩下的行号的第二列是否为1，是就删掉
: ....
: 如果每次能删掉1/2的话，复杂度不就是
: (N + N/2 + N/4 + N/8 +....)*O(set_operation) = 2N*O(set_operation)
: Set如果用hash实现，查找删除就是O(1), 总共就是O(N)
: 如果用BST实现，总共就是O(NlgN)
|
e**********6
发帖数: 78 | 24 用set记录行号的话，默认情况下c++ access set的时间复杂度似乎是logn吧。。 |
m*****e
发帖数: 47 | 25 No need to sort. Just scan column by column. At each step, eliminate rows
that have the value 1. Even if you do a counting sort, it include a
scanning step. |
l*****v
发帖数: 498 | 26 空间是O(n)
但时间是O(n^2)
【在 f***g 的大作中提到】
: 同意，不用sort
: 但是用Queue来记录还需要检查的行号。
: 一开始1......n入队。
: 第一遍，扫描第一列，如果为1，抛弃，如果为0，重新加到对尾。
: 以此类推。直到Queue的size为1.
: 时间O(n)
: 空间O(n)
|
z****t
发帖数: 1090 | 27 我好象记得以前phd qualify exam中有类似这样的题 好象是找第一个非0元素 类似
想法 也是O(n)
..
【在 x**y 的大作中提到】
: This is a good point, now I think overall average case is n + n/2 + n/4 + ..
: . + 1 ==> O(N)!
|
g*********s
发帖数: 1782 | 28 这个解法好。set/unsorted_set这里大材小用了。
不过worst case还是O(N^2)。
【在 f***g 的大作中提到】
: 同意，不用sort
: 但是用Queue来记录还需要检查的行号。
: 一开始1......n入队。
: 第一遍，扫描第一列，如果为1，抛弃，如果为0，重新加到对尾。
: 以此类推。直到Queue的size为1.
: 时间O(n)
: 空间O(n)
|
B********n
发帖数: 384 | 29 同意
best case: 第一列有N-1个1, 复杂度 = N = O(N)
worst case: 只有最后一列有1, 复杂度 = N^2 = O(N^2)
average case: 每个位置是1的概率大约是1/2, 复杂度 = N + N/2 + N/4 + ... = 2N
= O(N)
【在 g*********s 的大作中提到】
: 这个解法好。set/unsorted_set这里大材小用了。
: 不过worst case还是O(N^2)。
|
l*********3
发帖数: 26 | 30 Use random algorithm.
push 1-N into a queue q.
while ( !found )
begin
column_idx = random number from 1 to N.
while ( !q.empty() )
begin
pop a row number row_idx from q.
check Matrix[row_idx][column_idx]
if it is zero
push row_idx into an another queue q'.
endif
endwhile
if size(q')==1
then
found the row, and return
endif
q = q'
endwhile
The runtime of this algorithm is depended on the probability of 1 in the
matrix. If we assume the probablility of 1 in the matrix is p. In each
iteration, we can expect that pN rows are removed. Thus,
In iteration 1, we scan N numbers,
In iteration 2, we scan (1-p)N numbers,
in iteration 3, we scan (1-p)(1-p)N numbers
...
So, we need -log_(1-p)N iterations, the randomized runtime of the algorithm
is O(N/p). If p is fixed, that is O(N).
Of course, the worse case is O(N^2).
【在 x**y 的大作中提到】
: 1. 有几百万 NODES IN GRAPH, 用什么数据结构来代表, 各有什么优缺点?
: 2. N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0
: 的那一行. 平均O()和 WORST CASE O() 是多少?
|
