i*****h 发帖数: 1534 | 1 想避开system design所以投了SET, 电面聊了一堆怎么测试,最后剩20分钟老印说只有
一题,题目如下,面试的时候让我自己写个Pair class,然后开始做题要求返回 List<
Node>,我写了一半就超时了。哪个大牛给解一下吧,我没想明白怎么做。
Write a function that receives a set of node dependencies and return a list
of nodes such that the independent nodes are generated first.
- For example, Input= { (A, B), (B, C) (D, C) } where a pair (A, B)
indicates that node A depends on node B. Output= [C, B, D, A]
- Another example, Input = { (A B) (B C) (E A) (Q B) (Q C)} could generate [
C B A Q E].
- Small example. I = { (A B) (B C) } O = [C B A] |
i*****h 发帖数: 1534 | 2 网上搜了下好像可以用topological sort 做? 大牛们给指点下吧,谢谢 |
t*********r 发帖数: 387 | |
h******k 发帖数: 810 | |
i*****h 发帖数: 1534 | 5 LC都刷了,没碰到啊。。。。
【在 h******k 的大作中提到】 : 楼主,好好复习下再去面吧,不然机会都浪费了。
|
i*****h 发帖数: 1534 | |
n******n 发帖数: 12088 | 7 拓扑排序都没准备,刷LC不够
【在 i*****h 的大作中提到】 : LC都刷了,没碰到啊。。。。
|
i*****h 发帖数: 1534 | 8 老印上来就说让我用hashmap做,没想到其他方法 |
l********r 发帖数: 7 | 9 拓扑排序,边用邻接表存,存入度,每次找入度为0的输出,然后更新邻接表,直到输
出所有节点。O(n+e)
List<
list
[
【在 i*****h 的大作中提到】 : 想避开system design所以投了SET, 电面聊了一堆怎么测试,最后剩20分钟老印说只有 : 一题,题目如下,面试的时候让我自己写个Pair class,然后开始做题要求返回 List< : Node>,我写了一半就超时了。哪个大牛给解一下吧,我没想明白怎么做。 : Write a function that receives a set of node dependencies and return a list : of nodes such that the independent nodes are generated first. : - For example, Input= { (A, B), (B, C) (D, C) } where a pair (A, B) : indicates that node A depends on node B. Output= [C, B, D, A] : - Another example, Input = { (A B) (B C) (E A) (Q B) (Q C)} could generate [ : C B A Q E]. : - Small example. I = { (A B) (B C) } O = [C B A]
|
M**********g 发帖数: 59 | 10 这是个伪代码,挺直观的
L← Empty list that will contain the sorted elements
//这个会找吧?就是先得到一个集合,里面的顶点没有任何依赖
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
foreach node m with an edge e from n to m do
remove edge e from thegraph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least onecycle)
else
return L (a topologically sortedorder)
【在 i*****h 的大作中提到】 : 网上搜了下好像可以用topological sort 做? 大牛们给指点下吧,谢谢
|
|
|
i*****h 发帖数: 1534 | 11 我其实面完自己就搜出来用什么方法了,但是还是想看看code怎么写,能给贴个code吗?
好像版上大家都觉得这题很简单,我以前还真没碰到过这种题。多谢了 |
l********r 发帖数: 7 | |
h******k 发帖数: 810 | 13 MIT的书,每章基本算法,都搞懂也没多少时间。
这题你要立马说用拓扑排序,原理大致不错,code就算磕磕巴巴,估计也让过了。
【在 i*****h 的大作中提到】 : LC都刷了,没碰到啊。。。。
|
i*****h 发帖数: 1534 | 14 没做出来认栽,没想到SET会出这种题。
难怪没人肯贴面经就因为你这种说风凉话的人太多了,还磕磕巴巴就过了,做梦了吧,
老印能出这题我就猜到结果了。
【在 h******k 的大作中提到】 : MIT的书,每章基本算法,都搞懂也没多少时间。 : 这题你要立马说用拓扑排序,原理大致不错,code就算磕磕巴巴,估计也让过了。
|
n******n 发帖数: 12088 | 15 太敏感。这个确实是图论基本算法,DFS的典型应用。
【在 i*****h 的大作中提到】 : 没做出来认栽,没想到SET会出这种题。 : 难怪没人肯贴面经就因为你这种说风凉话的人太多了,还磕磕巴巴就过了,做梦了吧, : 老印能出这题我就猜到结果了。
|
i*****h 发帖数: 1534 | 16 还真没敏感,一上来就让我用hashmap,至于你们说的存链表啊dfs啊我也说了,code真
是没时间写完。都说了认栽了,但我不自贱,lc该刷的都刷了,热门面经该看的也看了
,没啥好自我检讨的了。自问比烙印老白做的多的多。
活该中国人找工作这样,反正个个都自贱,搞死了也只会躲家里哭,互相检讨,还挺有
意思的。
【在 n******n 的大作中提到】 : 太敏感。这个确实是图论基本算法,DFS的典型应用。
|
h******k 发帖数: 810 | 17 真心没笑话你,本来还想推荐你看ACM辅导材料的,现在吓得不敢说了。
你太紧张了,身份没问题的话,好好休息几周,再战江湖。
【在 i*****h 的大作中提到】 : 没做出来认栽,没想到SET会出这种题。 : 难怪没人肯贴面经就因为你这种说风凉话的人太多了,还磕磕巴巴就过了,做梦了吧, : 老印能出这题我就猜到结果了。
|
i*****h 发帖数: 1534 | 18 看的再多也抵不住烙印声势浩大,面到现在什么情况大家自己心里清楚,完全不在于看
多看少。
你还是我都只是随时会被人扔掉的棋子罢了,谁笑谁都不重要。你要真好心就多贴点面
经造福下大众。
【在 h******k 的大作中提到】 : 真心没笑话你,本来还想推荐你看ACM辅导材料的,现在吓得不敢说了。 : 你太紧张了,身份没问题的话,好好休息几周,再战江湖。
|
b**********5 发帖数: 7881 | 19 放你妈的狗屁! 那本书, 人家一个学期的课, 也基本就是上一半, 还是简单的上。
。。
【在 h******k 的大作中提到】 : MIT的书,每章基本算法,都搞懂也没多少时间。 : 这题你要立马说用拓扑排序,原理大致不错,code就算磕磕巴巴,估计也让过了。
|
h******k 发帖数: 810 | 20 那你以前上过数据结构的课吗?上过,很多东西就是复习下吧。
一个学期的课,也就是一周两节四小时十几周,你一天8小时,五六个周末够了吧。
【在 b**********5 的大作中提到】 : 放你妈的狗屁! 那本书, 人家一个学期的课, 也基本就是上一半, 还是简单的上。 : 。。
|
|
|
d******a 发帖数: 238 | 21 烙印要搞你你题做对了都没用。。烙印对中国人敌意很大
真是没时间写完。都说了认栽了,但我不自贱,lc该刷的都刷了,热门面经该看的也看
了,没啥好自我检讨的了。自问比烙印老白做的多的多。
有意思的。 |
i*****h 发帖数: 1534 | 22 听够你的废话了,右/左上角点X 不送
【在 h******k 的大作中提到】 : 那你以前上过数据结构的课吗?上过,很多东西就是复习下吧。 : 一个学期的课,也就是一周两节四小时十几周,你一天8小时,五六个周末够了吧。
|
x********u 发帖数: 1150 | 23 猴姐, 我顶你.
啃那本书不是上策.
【在 b**********5 的大作中提到】 : 放你妈的狗屁! 那本书, 人家一个学期的课, 也基本就是上一半, 还是简单的上。 : 。。
|
t*********d 发帖数: 1103 | 24 clrs 那个那么厚, 30 多章。 topological sort 不算很基本了,它是 dfs 的
变种。我每次看完没多久就忘记。实在是因为用的很少。
【在 h******k 的大作中提到】 : MIT的书,每章基本算法,都搞懂也没多少时间。 : 这题你要立马说用拓扑排序,原理大致不错,code就算磕磕巴巴,估计也让过了。
|
n******n 发帖数: 12088 | 25 图论算法是相对重要的一章,很多本科课程会覆盖。拓扑培训又是基本的图论算法,应
用非常广泛。
事实上离散数学里也很可能讲到。
【在 t*********d 的大作中提到】 : clrs 那个那么厚, 30 多章。 topological sort 不算很基本了,它是 dfs 的 : 变种。我每次看完没多久就忘记。实在是因为用的很少。
|
d****n 发帖数: 397 | 26 这个算法比较有名。但是写起来还是比较麻烦的,我花了几十分钟写,又花了几十分钟
debug。加起来肯定超过半个小时了,再加上面试时候紧张,还真不好说。
这是我写的
import java.util.*;
public class Solution {
private int f;
public ArrayList sort(ArrayList >
list) {
HashMap m = new HashMap ();
HashMap visited = new HashMap
Character> ();
int l = list.size();
int i,f;
this.f = 0;
for(i = 0; i < l; i ++) {
char ca = list.get(i).A;
char cb = list.get(i).B;
m.put(ca, 0);
m.put(cb, 0);
visited.put(ca, 'w');
visited.put(cb, 'w');
}
for (char A : m.keySet()) {
if (visited.get(A) == 'w') {
dfs_visit(A, list, visited, m);
}
}
System.out.println(m);
ArrayList res = new ArrayList(m.keySet());
Collections.sort(res, new Comparator () {
@Override
public int compare(Character A, Character B) {
return m.get(A).compareTo(m.get(B));
}
});
return res;
}
public void dfs_visit(char A, ArrayList >
list, HashMap visited, HashMap m) {
if (visited.get(A) == 'w') {
visited.put(A, 'g');
for (Pair p : list) {
if(p.A == A && visited.get(p.B) == 'w') {
dfs_visit(p.B, list, visited, m);
}
}
}
visited.put(A, 'b');
m.put(A, this.f);
this.f ++;
return;
}
public static void main(String[] args) {
Pair p1 = new Pair('A', 'B');
Pair p2 = new Pair('B', 'C');
Pair p3 = new Pair('E', 'A');
Pair p4 = new Pair('Q', 'B');
Pair p5 = new Pair('Q', 'C');
ArrayList > list = new ArrayList
Character, Character> > ();
list.add(p1); list.add(p2); list.add(p3); list.add(p4); list.add(p5);
Solution s = new Solution();
System.out.println(s.sort(list));
}
}
class Pair {
public K A;
public T B;
public Pair(K A, T B) {
this.A = A;
this.B = B;
}
}
List<
list
[
【在 i*****h 的大作中提到】 : 想避开system design所以投了SET, 电面聊了一堆怎么测试,最后剩20分钟老印说只有 : 一题,题目如下,面试的时候让我自己写个Pair class,然后开始做题要求返回 List< : Node>,我写了一半就超时了。哪个大牛给解一下吧,我没想明白怎么做。 : Write a function that receives a set of node dependencies and return a list : of nodes such that the independent nodes are generated first. : - For example, Input= { (A, B), (B, C) (D, C) } where a pair (A, B) : indicates that node A depends on node B. Output= [C, B, D, A] : - Another example, Input = { (A B) (B C) (E A) (Q B) (Q C)} could generate [ : C B A Q E]. : - Small example. I = { (A B) (B C) } O = [C B A]
|
i*****h 发帖数: 1534 | 27 我看一下,多谢了!
>
【在 d****n 的大作中提到】 : 这个算法比较有名。但是写起来还是比较麻烦的,我花了几十分钟写,又花了几十分钟 : debug。加起来肯定超过半个小时了,再加上面试时候紧张,还真不好说。 : 这是我写的 : import java.util.*; : public class Solution { : private int f; : public ArrayList sort(ArrayList > : list) { : HashMap m = new HashMap (); : HashMap visited = new HashMap
|
y*****e 发帖数: 712 | 28 还一天8小时。。。醉了,lz有工作,一天2-3小时都够累的了,有些人真是站着说话不
腰疼。
【在 h******k 的大作中提到】 : 那你以前上过数据结构的课吗?上过,很多东西就是复习下吧。 : 一个学期的课,也就是一周两节四小时十几周,你一天8小时,五六个周末够了吧。
|
b**********5 发帖数: 7881 | 29 我没工作, 一天刷一二个题, 都累死了。。。
【在 y*****e 的大作中提到】 : 还一天8小时。。。醉了,lz有工作,一天2-3小时都够累的了,有些人真是站着说话不 : 腰疼。
|
h******k 发帖数: 810 | 30 周末...
【在 y*****e 的大作中提到】 : 还一天8小时。。。醉了,lz有工作,一天2-3小时都够累的了,有些人真是站着说话不 : 腰疼。
|
|
|
i*****h 发帖数: 1534 | 31 装B装什么呀,中国人里就是太多你们这种人了,妒人有笑人无。刚反映过来这种sb题
目就是高端黑给出的,20分钟无bug你写给我看看,不是读书读的多嘛,你把书背出来
了也没用,这题根本不适合面试用,何况还是电面。碰到高端黑还真不好说什么,没法
投诉。
到时候给你出这种题,我就等着看你自己怎么写检讨了,别说倒霉啊,你印度三大爷叫
你回家看书去了。
【在 n******n 的大作中提到】 : 图论算法是相对重要的一章,很多本科课程会覆盖。拓扑培训又是基本的图论算法,应 : 用非常广泛。 : 事实上离散数学里也很可能讲到。
|
n******n 发帖数: 12088 | 32 适合不适合,不是你说了算。如果这道不适合,难道LC上那些就适合?大部分比拓扑排
序偏。
合着你做过的才适合?没见过的都不适合?说实话你够幸运了。G禁了很多经典,新题
不断,而你拿到的是教科书的经典算法。
【在 i*****h 的大作中提到】 : 装B装什么呀,中国人里就是太多你们这种人了,妒人有笑人无。刚反映过来这种sb题 : 目就是高端黑给出的,20分钟无bug你写给我看看,不是读书读的多嘛,你把书背出来 : 了也没用,这题根本不适合面试用,何况还是电面。碰到高端黑还真不好说什么,没法 : 投诉。 : 到时候给你出这种题,我就等着看你自己怎么写检讨了,别说倒霉啊,你印度三大爷叫 : 你回家看书去了。
|
i*****h 发帖数: 1534 | 33 你要考人文采不考论文也不考散文。来,三字经默写一遍,小时候可都读过,够照顾你
吧。是这个道理吗?
【在 n******n 的大作中提到】 : 适合不适合,不是你说了算。如果这道不适合,难道LC上那些就适合?大部分比拓扑排 : 序偏。 : 合着你做过的才适合?没见过的都不适合?说实话你够幸运了。G禁了很多经典,新题 : 不断,而你拿到的是教科书的经典算法。
|
n******n 发帖数: 12088 | 34 只能考你刚背过的文章才公平,是这个道理吗?
【在 i*****h 的大作中提到】 : 你要考人文采不考论文也不考散文。来,三字经默写一遍,小时候可都读过,够照顾你 : 吧。是这个道理吗?
|
i*****h 发帖数: 1534 | 35 三哥三姐考吗? 老白考吗? 为什么只有老中考? 要不要再自我检讨下,因为洋大人
在考验我啊
【在 n******n 的大作中提到】 : 只能考你刚背过的文章才公平,是这个道理吗?
|