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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题主要考虑稀疏图的存储吧,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我当场给的解法是: 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我当场给的解法是: 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : sort by第一个column不如直接scan,留下0的,只要O(n)啊
|
x**y 发帖数: 70 | 9 我觉得只有SORT后, 你才知道什么时候STOP, 然后移到下一个COLUNM. 否则, 你还是要
扫描一个COLUMN的所有元素.
【在 k*p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : sort by第一个column不如直接scan,留下0的,只要O(n)啊
|
k*p 发帖数: 1526 | 10 你sort不也要扫描当前column剩下的所有元素么?
你假设有一半非零,所以得到1/2nlog(1/2 n)
那我也可以做同样假设,这样scan第二列只有1/2n
【在 x**y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得只有SORT后, 你才知道什么时候STOP, 然后移到下一个COLUNM. 否则, 你还是要 : 扫描一个COLUMN的所有元素.
|
|
|
x**y 发帖数: 70 | 11 不需要. 只要碰到 1, 就知道剩下的都是 1 啦. 如果你不SORT, 除非你建立新2D
array (n/2 by n), 你还是要在原始 N*N array 里看第二列所有元素啊.
【在 k*p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的想法是先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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不需要. 只要碰到 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的point是,你的sort需要nlogn,不是sort完看1或0
|
b****n 发帖数: 84 | 16 只有0/1的话,sort是O(n)
【在 k*p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 只有0/1的话,sort是O(n)
|
s********k 发帖数: 6180 | 19 这题有这么复杂吗?while (!(one row|0)) return else next row
最坏O(N),最好O(1)吧
【在 b****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 只有0/1的话,sort是O(n)
|
x**y 发帖数: 70 | 20 看题不仔细. 是 N*N MATRIX. 你的方法最坏和平均都是O(N^2).
【在 s********k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题有这么复杂吗?while (!(one row|0)) return else next row : 最坏O(N),最好O(1)吧
|
|
|
s*******r 发帖数: 47 | 21 应该是的,最坏情况是O(n*n). 但sort显然需要额外的空间。
【在 b****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 只有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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 同意,不用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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 同意,不用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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个解法好。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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. 有几百万 NODES IN GRAPH, 用什么数据结构来代表, 各有什么优缺点? : 2. N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0 : 的那一行. 平均O()和 WORST CASE O() 是多少?
|