y***e
发帖数: 32 | 1 Updated的题目。
1. 给定一个directed graph和一个s节点和一个d节点，判断s和d的距离是否<=3。距离
定义为s和d之间最短路径上link的数目。如果d是s的邻居，则距离为1。
注意，这个directed graph使用adjacent array来表示一个节点的所有neighbors，并
且每个节点最多有n个neighbors。每个节点都有一个Idx，并且每个节点的adjacent
array都是sorted。例如1有邻居2和3，那么1的adjacent array是[2,3] (sorted)
直接的BSF解法时间复杂度是O(n^3)。
要求设计Solution是时间 O(n^2)。
2. 设计一个hash table，实现set（int key，int val）和get（int key）
3. 给定一个整数array A (长度为n)，求出另外一个array B，使得B[i] = A[0]A[1]..
.A[i - 1]A[i + 1]...A[n - 1] (i.e., A[i] is missing from B[i])
如果不可以用除法，如何解？要求solution是时间O(n)
4. 给出n个点，求最多点的数目(这些点在一条直线), leetcode原题 |
c*******r
发帖数: 610 | |
q********c
发帖数: 1774 | 3 bless! 请问有什么system design的题吗？你面的是infra还是applications?
..
【在 y***e 的大作中提到】
: Updated的题目。
: 1. 给定一个directed graph和一个s节点和一个d节点，判断s和d的距离是否<=3。距离
: 定义为s和d之间最短路径上link的数目。如果d是s的邻居，则距离为1。
: 注意，这个directed graph使用adjacent array来表示一个节点的所有neighbors，并
: 且每个节点最多有n个neighbors。每个节点都有一个Idx，并且每个节点的adjacent
: array都是sorted。例如1有邻居2和3，那么1的adjacent array是[2,3] (sorted)
: 直接的BSF解法时间复杂度是O(n^3)。
: 要求设计Solution是时间 O(n^2)。
: 2. 设计一个hash table，实现set（int key，int val）和get（int key）
: 3. 给定一个整数array A (长度为n)，求出另外一个array B，使得B[i] = A[0]A[1]..
|
c*******r
发帖数: 610 | 4 可能第二题设计hash table就算design了吧，有很多东西需要讨论。
【在 q********c 的大作中提到】
: bless! 请问有什么system design的题吗？你面的是infra还是applications?
:
: ..
|
M*****D
发帖数: 22 | 5 1. 给定一个directed graph和一个s节点和一个d节点，判断s和d的距离是否<=3。距离
定义为s和d之间最短路径上link的数目。如果d是s的邻居，则距离为1。
注意，这个directed graph使用adjacent array来表示一个节点的所有neighbors。每
个节点都有一个Idx，并且每个节点的adjacent array都是sorted。例如1有邻居2和3，
那么1的adjacent array是[2,3] (sorted)
只觉得就是个循环3遍的BFS。。这题的“注意”有什么需要特别注意的吗。。是不是和
BFS搜索的state标记有关？有人能帮忙解释吗 |
c*******r
发帖数: 610 | 6 假设给定s 和 d的 vertex IDX，直接从s开始用bfs,用一个队列维持（vertex index,
level)的数对，初始时， push (s, 1),然后把s的neighbors push 到队列里，增加当
前的层数。 比如s=1, 如果1的邻居为2,3， 那么push (2,2), (3,2)到队列中，表示1
的neighbors 2 and 3 have level =2.
如果发现在某一个节点的neighbor为d，计算s,d层数之间的距离，看看是否<=3.
是这样吗？应该不需要几次bfs吧？
请指出错误我好学习，谢谢！
【在 M*****D 的大作中提到】
: 1. 给定一个directed graph和一个s节点和一个d节点，判断s和d的距离是否<=3。距离
: 定义为s和d之间最短路径上link的数目。如果d是s的邻居，则距离为1。
: 注意，这个directed graph使用adjacent array来表示一个节点的所有neighbors。每
: 个节点都有一个Idx，并且每个节点的adjacent array都是sorted。例如1有邻居2和3，
: 那么1的adjacent array是[2,3] (sorted)
: 只觉得就是个循环3遍的BFS。。这题的“注意”有什么需要特别注意的吗。。是不是和
: BFS搜索的state标记有关？有人能帮忙解释吗
|
M*****D
发帖数: 22 | 7 哦，我所说的几次bfs就是有一个counter，然后当
while(!queue.isEmpty()){
counter++; //比如一开始queue只有1入队列，这时候counter就是1.然后2，3入了
，这时候counter就是2了
if(counter>3) return false;
.....//找neighbor放入队列
}
我不需要额外的level来对应每一个node 不过我需要一个state标志来标识这个node是
否被visited
我不知道这个sorted neighbor有什么特别用意
,
1
【在 c*******r 的大作中提到】
: 假设给定s 和 d的 vertex IDX，直接从s开始用bfs,用一个队列维持（vertex index,
: level)的数对，初始时， push (s, 1),然后把s的neighbors push 到队列里，增加当
: 前的层数。 比如s=1, 如果1的邻居为2,3， 那么push (2,2), (3,2)到队列中，表示1
: 的neighbors 2 and 3 have level =2.
: 如果发现在某一个节点的neighbor为d，计算s,d层数之间的距离，看看是否<=3.
: 是这样吗？应该不需要几次bfs吧？
: 请指出错误我好学习，谢谢！
|
c*******r
发帖数: 610 | 8 我也想不清楚，如果说要利用这个排序的特点，可能有特别用意，否则没有什么必要吧？
等待高人
【在 M*****D 的大作中提到】
: 哦，我所说的几次bfs就是有一个counter，然后当
: while(!queue.isEmpty()){
: counter++; //比如一开始queue只有1入队列，这时候counter就是1.然后2，3入了
: ，这时候counter就是2了
: if(counter>3) return false;
: .....//找neighbor放入队列
: }
: 我不需要额外的level来对应每一个node 不过我需要一个state标志来标识这个node是
: 否被visited
: 我不知道这个sorted neighbor有什么特别用意
|
l***i
发帖数: 1309 | |
x****k
发帖数: 34 | 10 第一题，从s开始，查看n个邻居，再查看n^2个邻居的邻居，第三步，对于n^2的节点，
查看它们的邻居。因为adjacency list是sorted，可以用binary search来检查d在不在
其中。这样整个复杂度是O(n^2 log(n))。
请教，有办法做到O(n^2)么？
第三题看起来容易，先算log(B(i)) = log(A(0)) + log(A(1)) + ...
只用log, +, -, exp，避开了除法。这样对不对？ |
|
|
h****g
发帖数: 105 | 11 我觉得那个求最短路径的可能可以这么做：1.先查看s在不在d的邻居里，若在返回true
否则进行2. 2. 看s的邻居和d邻居有没有共同的节点，nlgn。若有返回true，否则进
行3. 3.剩下的点看有没有即在s的邻居里又在d的邻居里，如果有返回true 否则返回
false |
h*******e
发帖数: 1377 | 12 我觉得第一题还是O(n^3) 阿， bfs 顶多在第三层的时候用个二分加速一下，但是不
改变复杂度啊。 |
e***l
发帖数: 710 | |
h*******e
发帖数: 1377 | 14 哦，对你说的对。先搜索source点 distance 为2的点集合 O(N^2)，然后用哈希判断
是否和destination点 的O（N） 邻居集合有交集， 复杂度 O(N^2)
这个距离要求是三还是挺好的，要是距离是五什么的就需要双向搜索，代码就很变得很
难了。
【在 e***l 的大作中提到】
: 不一样。同时从起点和终点开始搜
|
x****k
发帖数: 34 | 15 还是不很明白。如果是undirected graph这没问题。可这是direcetd graph，所以
source点 distance 为2的点集合 与 destination点 的O（N） 邻居集合 完全可以没
有交集，但是destination点距离source为3。
【在 h*******e 的大作中提到】
: 哦，对你说的对。先搜索source点 distance 为2的点集合 O(N^2)，然后用哈希判断
: 是否和destination点 的O（N） 邻居集合有交集， 复杂度 O(N^2)
: 这个距离要求是三还是挺好的，要是距离是五什么的就需要双向搜索，代码就很变得很
: 难了。
|
r*******k
发帖数: 1423 | 16 第三题
想到的是弄两个辅助向量
A(0) A(0)*A(1) A(0)A(1)A(2) ...
A(n) A(n)A(n-1) ....
这两个向量再乘起来就可以了
复杂度不高
空间也可以不额外占用
【在 x****k 的大作中提到】
: 第一题，从s开始，查看n个邻居，再查看n^2个邻居的邻居，第三步，对于n^2的节点，
: 查看它们的邻居。因为adjacency list是sorted，可以用binary search来检查d在不在
: 其中。这样整个复杂度是O(n^2 log(n))。
: 请教，有办法做到O(n^2)么？
: 第三题看起来容易，先算log(B(i)) = log(A(0)) + log(A(1)) + ...
: 只用log, +, -, exp，避开了除法。这样对不对？
|
m******e
发帖数: 82 | |
s**********k
发帖数: 88 | 18 第一题，能不能用Dijkstra算法？ Dijkstra算法的复杂度是 O(n^2) 或者 O(nlogn)
（用heap)。是不是我漏掉了什么。
..
【在 y***e 的大作中提到】
: Updated的题目。
: 1. 给定一个directed graph和一个s节点和一个d节点，判断s和d的距离是否<=3。距离
: 定义为s和d之间最短路径上link的数目。如果d是s的邻居，则距离为1。
: 注意，这个directed graph使用adjacent array来表示一个节点的所有neighbors，并
: 且每个节点最多有n个neighbors。每个节点都有一个Idx，并且每个节点的adjacent
: array都是sorted。例如1有邻居2和3，那么1的adjacent array是[2,3] (sorted)
: 直接的BSF解法时间复杂度是O(n^3)。
: 要求设计Solution是时间 O(n^2)。
: 2. 设计一个hash table，实现set（int key，int val）和get（int key）
: 3. 给定一个整数array A (长度为n)，求出另外一个array B，使得B[i] = A[0]A[1]..
|
s**********k
发帖数: 88 | 19 已放在队列里的vertex的level可能会减少。
,
1
【在 c*******r 的大作中提到】
: 假设给定s 和 d的 vertex IDX，直接从s开始用bfs,用一个队列维持（vertex index,
: level)的数对，初始时， push (s, 1),然后把s的neighbors push 到队列里，增加当
: 前的层数。 比如s=1, 如果1的邻居为2,3， 那么push (2,2), (3,2)到队列中，表示1
: 的neighbors 2 and 3 have level =2.
: 如果发现在某一个节点的neighbor为d，计算s,d层数之间的距离，看看是否<=3.
: 是这样吗？应该不需要几次bfs吧？
: 请指出错误我好学习，谢谢！
|
h*******e
发帖数: 1377 | 20 俄确实，无向图那么做可以达到O（n^2)， 至于有向图， 似乎在第三层二分加速后复
杂度是O(n^2 logn)
【在 x****k 的大作中提到】
: 还是不很明白。如果是undirected graph这没问题。可这是direcetd graph，所以
: source点 distance 为2的点集合 与 destination点 的O（N） 邻居集合 完全可以没
: 有交集，但是destination点距离source为3。
|
|
|
f*********s
发帖数: 69 | |
y***e
发帖数: 32 | 22 对不起，你们的分析是对的，原题是undirected graph。上面的分析也都是对的。我已
经把原题的表示改了。
【在 h*******e 的大作中提到】
: 俄确实，无向图那么做可以达到O（n^2)， 至于有向图， 似乎在第三层二分加速后复
: 杂度是O(n^2 logn)
|
r*******k
发帖数: 1423 | 23 第一个题，是双向dijkstra搜索么？
从s走2步
t走1步
是n^2级的
判断是否有正反向都搜到的节点
距离
，并
..
【在 y***e 的大作中提到】
: Updated的题目。
: 1. 给定一个directed graph和一个s节点和一个d节点，判断s和d的距离是否<=3。距离
: 定义为s和d之间最短路径上link的数目。如果d是s的邻居，则距离为1。
: 注意，这个directed graph使用adjacent array来表示一个节点的所有neighbors，并
: 且每个节点最多有n个neighbors。每个节点都有一个Idx，并且每个节点的adjacent
: array都是sorted。例如1有邻居2和3，那么1的adjacent array是[2,3] (sorted)
: 直接的BSF解法时间复杂度是O(n^3)。
: 要求设计Solution是时间 O(n^2)。
: 2. 设计一个hash table，实现set（int key，int val）和get（int key）
: 3. 给定一个整数array A (长度为n)，求出另外一个array B，使得B[i] = A[0]A[1]..
|
y***n
发帖数: 1594 | 24 2 和 3 不是一样的吗？
3 应该是看 s 的邻居的邻居 和 d 的邻居的邻居有没有共同点？
true
【在 h****g 的大作中提到】
: 我觉得那个求最短路径的可能可以这么做：1.先查看s在不在d的邻居里，若在返回true
: 否则进行2. 2. 看s的邻居和d邻居有没有共同的节点，nlgn。若有返回true，否则进
: 行3. 3.剩下的点看有没有即在s的邻居里又在d的邻居里，如果有返回true 否则返回
: false
|
s******i
发帖数: 236 | |
w********2
发帖数: 111 | 26 第3题有点没思路，不能用除法，始终只能想到O（nlgn），如何到O(N)的，求楼主帮忙 |
m*******d
发帖数: 20 | 27 第3题:先计算LEFT[I]=LEFT[I-1]*A[I-1],with LEFT[0]=1, 用时O(n), 然后计算RIGHT
[I]=A[I-1]*RIGHT[I+1],那么B[I]=LEFT[I-1]*RIGHT[I+1].总共用时O(N)
【在 w********2 的大作中提到】
: 第3题有点没思路，不能用除法，始终只能想到O（nlgn），如何到O(N)的，求楼主帮忙
|
