~~问两道AMAZON电面题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

~~问两道AMAZON电面题

~~问两道AMAZON电面题# JobHunting - 待字闺中

x*y2010-11-10 08:11

1 楼

1. 有几百万 NODES IN GRAPH, 用什么数据结构来代表, 各有什么优缺点?
2. N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0
的那一行. 平均O()和 WORST CASE O() 是多少?

c*j2010-11-10 08:11

2 楼

1. adjacency list? linked list. slower than adj matrix. however too large
for sparse.
2. 类似binary search 思想？上一半 sum，下一半sum比，少的一半中有，之后知道
之后再在这半中 divide and conquer?

x*y2010-11-10 08:11

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*x2010-11-10 08:11

4 楼

第一题主要考虑稀疏图的存储吧，sparse matrix相关的可以看看
第二题，可以考虑random algo；
任选一列，排除有“1”的行；
在余下的行继续这么搞；
复杂度取决于“1”分布的比例；worst case当然是N^2

x*y2010-11-10 08:11

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*y2010-11-10 08:11

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*p2010-11-10 08:11

7 楼

sort by第一个column不如直接scan，留下0的，只要O(n)啊

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

x*y2010-11-10 08:11

8 楼

那你扫描第二个 column 不又要看N个元素, 变成 O(N^2) 啊!?

【在 k*p 的大作中提到】

: sort by第一个column不如直接scan，留下0的，只要O(n)啊

x*y2010-11-10 08:11

9 楼

我觉得只有SORT后, 你才知道什么时候STOP, 然后移到下一个COLUNM. 否则, 你还是要
扫描一个COLUMN的所有元素.

【在 k*p 的大作中提到】

: sort by第一个column不如直接scan，留下0的，只要O(n)啊

k*p2010-11-10 08:11

10 楼

你sort不也要扫描当前column剩下的所有元素么？
你假设有一半非零，所以得到1/2nlog(1/2 n)
那我也可以做同样假设，这样scan第二列只有1/2n

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

: 我觉得只有SORT后, 你才知道什么时候STOP, 然后移到下一个COLUNM. 否则, 你还是要
: 扫描一个COLUMN的所有元素.

x*y2010-11-10 08:11

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*a2010-11-10 08:11

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*y2010-11-10 08:11

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*p2010-11-10 08:11

14 楼

我的point是，你的sort需要nlogn，不是sort完看1或0

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

: 不需要. 只要碰到 1, 就知道剩下的都是 1 啦. 如果你不SORT, 除非你建立新2D
: array (n/2 by n), 你还是要在原始 N*N array 里看第二列所有元素啊.

x*y2010-11-10 08:11

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*n2010-11-10 08:11

16 楼

只有0/1的话，sort是O(n)

【在 k*p 的大作中提到】

: 我的point是，你的sort需要nlogn，不是sort完看1或0

r*d2010-11-10 08:11

17 楼

把每一行转成一个二进制度的数，看这个数是不是等于0?
不过前提是那个数组已经放在一个string 数组里面了
或者XOR每一列的所有数字，看看哪行总是保持在0?

x*y2010-11-10 08:11

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*k2010-11-10 08:11

19 楼

这题有这么复杂吗？while （！（one row|0）） return else next row
最坏O(N),最好O(1)吧

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

: 只有0/1的话，sort是O(n)

x*y2010-11-10 08:11

20 楼

看题不仔细. 是 N*N MATRIX. 你的方法最坏和平均都是O(N^2).

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

: 这题有这么复杂吗？while （！（one row|0）） return else next row
: 最坏O(N),最好O(1)吧

s*r2010-11-10 08:11

21 楼

应该是的,最坏情况是O(n*n). 但sort显然需要额外的空间。

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

: 只有0/1的话，sort是O(n)

d*j2010-11-10 08:11

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*g2010-11-10 08:11

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*62010-11-10 08:11

24 楼

用set记录行号的话，默认情况下c++ access set的时间复杂度似乎是logn吧。。

m*e2010-11-10 08:11

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*v2010-11-10 08:11

26 楼

空间是O(n)
但时间是O(n^2)

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

: 同意，不用sort
: 但是用Queue来记录还需要检查的行号。
: 一开始1......n入队。
: 第一遍，扫描第一列，如果为1，抛弃，如果为0，重新加到对尾。
: 以此类推。直到Queue的size为1.
: 时间O(n)
: 空间O(n)

z*t2010-11-10 08:11

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*s2010-11-10 08:11

28 楼

这个解法好。set/unsorted_set这里大材小用了。
不过worst case还是O(N^2)。

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

B*n2010-11-10 08:11

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*32010-11-10 08:11

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() 是多少?