由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - ~~问两道AMAZON电面题
相关主题
Amazon 电面题, 觉得不可能再优化了!求分析这题的时间复杂度
Amazon 电面题, 觉得不可能再优化了!拓扑排序
一道rocket f 电面题find kth element in n*n sorted matrix
算法一问一个NxN矩阵每行每列都sort好,如何排序?
这两道题(CareerCup 150)的答案是不是有问题啊?一个特别的inplace merge two sorted arrays
请教一个题目一道电面题
问一道F家面试题数组中找和为0的3个数,4个数
抛砖引玉:Careercup 150题中的错误问个Facebook 电面题
相关话题的讨论汇总
话题: matrix话题: column话题: sort话题: scan话题: idx
进入JobHunting版参与讨论
1 (共1页)
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的所有元素.

相关主题
请教一个题目求分析这题的时间复杂度
问一道F家面试题拓扑排序
抛砖引玉:Careercup 150题中的错误find kth element in n*n sorted matrix
进入JobHunting版参与讨论
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)吧

相关主题
一个NxN矩阵每行每列都sort好,如何排序?数组中找和为0的3个数,4个数
一个特别的inplace merge two sorted arrays问个Facebook 电面题
一道电面题google电面题
进入JobHunting版参与讨论
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() 是多少?

1 (共1页)
进入JobHunting版参与讨论
相关主题
问个Facebook 电面题这两道题(CareerCup 150)的答案是不是有问题啊?
google电面题请教一个题目
贡献两道google面试题问一道F家面试题
贡献G电 估计挂了抛砖引玉:Careercup 150题中的错误
Amazon 电面题, 觉得不可能再优化了!求分析这题的时间复杂度
Amazon 电面题, 觉得不可能再优化了!拓扑排序
一道rocket f 电面题find kth element in n*n sorted matrix
算法一问一个NxN矩阵每行每列都sort好,如何排序?
相关话题的讨论汇总
话题: matrix话题: column话题: sort话题: scan话题: idx