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 那个那么厚， ３０ 多章。 topological sort 不算很基本了，它是 dfs 的
变种。我每次看完没多久就忘记。实在是因为用的很少。
【在 h******k 的大作中提到】
: MIT的书，每章基本算法，都搞懂也没多少时间。
: 这题你要立马说用拓扑排序，原理大致不错，code就算磕磕巴巴，估计也让过了。
|
n******n
发帖数: 12088 | 25 图论算法是相对重要的一章，很多本科课程会覆盖。拓扑培训又是基本的图论算法，应
用非常广泛。
事实上离散数学里也很可能讲到。
【在 t*********d 的大作中提到】
: clrs 那个那么厚， ３０ 多章。 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 的大作中提到】
: 只能考你刚背过的文章才公平，是这个道理吗？
|
