有人吃melatonin吗？好不好 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PennySaver - 省钱一族

有人吃melatonin吗？好不好

有人吃melatonin吗？好不好# PennySaver - 省钱一族

i*h2011-10-11 07:10

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]

l*f2011-10-11 07:10

2 楼

rt，最近睡眠不好，不想吃安眠葯，不知道这个melatonin好不好？有没有人吃？

i*h2011-10-11 07:10

3 楼

网上搜了下好像可以用topological sort 做？大牛们给指点下吧，谢谢

p*y2011-10-11 07:10

4 楼

有人吃了有效，有人吃了无效。
如果吃了没反应，还不如吃OTC那些轻剂量的sleeping aid，成效比较显着也不会上瘾
。

t*r2011-10-11 07:10

5 楼

http://en.wikipedia.org/wiki/Topological_sorting#Algorithms

l*f2011-10-11 07:10

6 楼

哦，那决定不吃了，谢谢。

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

: 有人吃了有效，有人吃了无效。
: 如果吃了没反应，还不如吃OTC那些轻剂量的sleeping aid，成效比较显着也不会上瘾
: 。

h*k2011-10-11 07:10

7 楼

楼主，好好复习下再去面吧，不然机会都浪费了。

b*92011-10-11 07:10

8 楼

据说给狗吃，可以让狗毛有光泽

i*h2011-10-11 07:10

9 楼

LC都刷了，没碰到啊。。。。

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

: 楼主，好好复习下再去面吧，不然机会都浪费了。

p*y2011-10-11 07:10

10 楼

暈，不会吧？狗不能乱吃人类的成药的呀。比如阿斯匹灵，狗吃了会死的。

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

: 据说给狗吃，可以让狗毛有光泽

i*h2011-10-11 07:10

11 楼

楼上的谁给贴个code吧

t*s2011-10-11 07:10

12 楼

对我很有效，吃了就能睡着
从3mg一粒开始吃

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

: rt，最近睡眠不好，不想吃安眠葯，不知道这个melatonin好不好？有没有人吃？

n*n2011-10-11 07:10

13 楼

拓扑排序都没准备，刷LC不够

【在 i*****h 的大作中提到】

: LC都刷了，没碰到啊。。。。

f*12011-10-11 07:10

14 楼

我也吃过，有效
我只有在睡不着的时候吃。
几个月没吃完一小瓶

i*h2011-10-11 07:10

15 楼

老印上来就说让我用hashmap做，没想到其他方法

l*r2011-10-11 07:10

16 楼

拓扑排序，边用邻接表存，存入度，每次找入度为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*g2011-10-11 07:10

17 楼

这是个伪代码，挺直观的
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*h2011-10-11 07:10

18 楼

我其实面完自己就搜出来用什么方法了，但是还是想看看code怎么写，能给贴个code吗？
好像版上大家都觉得这题很简单，我以前还真没碰到过这种题。多谢了

l*r2011-10-11 07:10

19 楼

这题是考数据结构，算法伪代码都一样的。
用邻接表O（n+e）
代码：
http://blog.csdn.net/tengweitw/article/details/17304311

h*k2011-10-11 07:10

20 楼

MIT的书，每章基本算法，都搞懂也没多少时间。
这题你要立马说用拓扑排序，原理大致不错，code就算磕磕巴巴，估计也让过了。

【在 i*****h 的大作中提到】

: LC都刷了，没碰到啊。。。。

i*h2011-10-11 07:10

21 楼

没做出来认栽，没想到SET会出这种题。
难怪没人肯贴面经就因为你这种说风凉话的人太多了，还磕磕巴巴就过了，做梦了吧，
老印能出这题我就猜到结果了。

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

: MIT的书，每章基本算法，都搞懂也没多少时间。
: 这题你要立马说用拓扑排序，原理大致不错，code就算磕磕巴巴，估计也让过了。

n*n2011-10-11 07:10

22 楼

太敏感。这个确实是图论基本算法，DFS的典型应用。

【在 i*****h 的大作中提到】

: 没做出来认栽，没想到SET会出这种题。
: 难怪没人肯贴面经就因为你这种说风凉话的人太多了，还磕磕巴巴就过了，做梦了吧，
: 老印能出这题我就猜到结果了。

i*h2011-10-11 07:10

23 楼

还真没敏感，一上来就让我用hashmap，至于你们说的存链表啊dfs啊我也说了，code真
是没时间写完。都说了认栽了，但我不自贱，lc该刷的都刷了，热门面经该看的也看了
，没啥好自我检讨的了。自问比烙印老白做的多的多。
活该中国人找工作这样，反正个个都自贱，搞死了也只会躲家里哭，互相检讨，还挺有
意思的。

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

: 太敏感。这个确实是图论基本算法，DFS的典型应用。

h*k2011-10-11 07:10

24 楼

真心没笑话你，本来还想推荐你看ACM辅导材料的，现在吓得不敢说了。
你太紧张了，身份没问题的话，好好休息几周，再战江湖。

【在 i*****h 的大作中提到】

i*h2011-10-11 07:10

25 楼

看的再多也抵不住烙印声势浩大，面到现在什么情况大家自己心里清楚，完全不在于看
多看少。
你还是我都只是随时会被人扔掉的棋子罢了，谁笑谁都不重要。你要真好心就多贴点面
经造福下大众。

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

: 真心没笑话你，本来还想推荐你看ACM辅导材料的，现在吓得不敢说了。
: 你太紧张了，身份没问题的话，好好休息几周，再战江湖。

b*52011-10-11 07:10

26 楼

放你妈的狗屁! 那本书，人家一个学期的课，也基本就是上一半，还是简单的上。
。。

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

: MIT的书，每章基本算法，都搞懂也没多少时间。
: 这题你要立马说用拓扑排序，原理大致不错，code就算磕磕巴巴，估计也让过了。

h*k2011-10-11 07:10

27 楼

那你以前上过数据结构的课吗？上过，很多东西就是复习下吧。
一个学期的课，也就是一周两节四小时十几周，你一天8小时，五六个周末够了吧。

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

: 放你妈的狗屁! 那本书，人家一个学期的课，也基本就是上一半，还是简单的上。
: 。。

d*a2011-10-11 07:10

28 楼

烙印要搞你你题做对了都没用。。烙印对中国人敌意很大

真是没时间写完。都说了认栽了，但我不自贱，lc该刷的都刷了，热门面经该看的也看
了，没啥好自我检讨的了。自问比烙印老白做的多的多。
有意思的。

i*h2011-10-11 07:10

29 楼

听够你的废话了，右／左上角点X 不送

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

: 那你以前上过数据结构的课吗？上过，很多东西就是复习下吧。
: 一个学期的课，也就是一周两节四小时十几周，你一天8小时，五六个周末够了吧。

x*u2011-10-11 07:10

30 楼

猴姐, 我顶你.
啃那本书不是上策.

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

: 放你妈的狗屁! 那本书，人家一个学期的课，也基本就是上一半，还是简单的上。
: 。。

t*d2011-10-11 07:10

31 楼

clrs 那个那么厚，　３０　多章。　topological sort 不算很基本了，它是　dfs 的
变种。我每次看完没多久就忘记。实在是因为用的很少。

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

: MIT的书，每章基本算法，都搞懂也没多少时间。
: 这题你要立马说用拓扑排序，原理大致不错，code就算磕磕巴巴，估计也让过了。

n*n2011-10-11 07:10

32 楼

图论算法是相对重要的一章，很多本科课程会覆盖。拓扑培训又是基本的图论算法，应
用非常广泛。
事实上离散数学里也很可能讲到。

【在 t*********d 的大作中提到】

: clrs 那个那么厚，　３０　多章。　topological sort 不算很基本了，它是　dfs 的
: 变种。我每次看完没多久就忘记。实在是因为用的很少。

d*n2011-10-11 07:10

33 楼

这个算法比较有名。但是写起来还是比较麻烦的，我花了几十分钟写，又花了几十分钟
debug。加起来肯定超过半个小时了，再加上面试时候紧张，还真不好说。
这是我写的
import java.util.*;
public class Solution {
private int f;
public ArrayList sort(ArrayList >
list) {
HashMap m = new HashMap ();
HashMap visited = new HashMapCharacter> ();
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 ArrayListCharacter, 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 的大作中提到】

i*h2011-10-11 07:10

34 楼

我看一下，多谢了！

>

【在 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*e2011-10-11 07:10

35 楼

还一天8小时。。。醉了，lz有工作，一天2-3小时都够累的了，有些人真是站着说话不
腰疼。

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

: 那你以前上过数据结构的课吗？上过，很多东西就是复习下吧。
: 一个学期的课，也就是一周两节四小时十几周，你一天8小时，五六个周末够了吧。

b*52011-10-11 07:10

36 楼

我没工作，一天刷一二个题，都累死了。。。

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

: 还一天8小时。。。醉了，lz有工作，一天2-3小时都够累的了，有些人真是站着说话不
: 腰疼。

h*k2011-10-11 07:10

37 楼

周末...

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

: 还一天8小时。。。醉了，lz有工作，一天2-3小时都够累的了，有些人真是站着说话不
: 腰疼。

i*h2011-10-11 07:10

38 楼

装B装什么呀，中国人里就是太多你们这种人了，妒人有笑人无。刚反映过来这种sb题
目就是高端黑给出的，20分钟无bug你写给我看看，不是读书读的多嘛，你把书背出来
了也没用，这题根本不适合面试用，何况还是电面。碰到高端黑还真不好说什么，没法
投诉。
到时候给你出这种题，我就等着看你自己怎么写检讨了，别说倒霉啊，你印度三大爷叫
你回家看书去了。

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

: 图论算法是相对重要的一章，很多本科课程会覆盖。拓扑培训又是基本的图论算法，应
: 用非常广泛。
: 事实上离散数学里也很可能讲到。

n*n2011-10-11 07:10

39 楼

适合不适合，不是你说了算。如果这道不适合，难道LC上那些就适合？大部分比拓扑排
序偏。
合着你做过的才适合？没见过的都不适合？说实话你够幸运了。G禁了很多经典，新题
不断，而你拿到的是教科书的经典算法。

【在 i*****h 的大作中提到】

: 装B装什么呀，中国人里就是太多你们这种人了，妒人有笑人无。刚反映过来这种sb题
: 目就是高端黑给出的，20分钟无bug你写给我看看，不是读书读的多嘛，你把书背出来
: 了也没用，这题根本不适合面试用，何况还是电面。碰到高端黑还真不好说什么，没法
: 投诉。
: 到时候给你出这种题，我就等着看你自己怎么写检讨了，别说倒霉啊，你印度三大爷叫
: 你回家看书去了。

i*h2011-10-11 07:10

40 楼

你要考人文采不考论文也不考散文。来，三字经默写一遍，小时候可都读过，够照顾你
吧。是这个道理吗？

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

: 适合不适合，不是你说了算。如果这道不适合，难道LC上那些就适合？大部分比拓扑排
: 序偏。
: 合着你做过的才适合？没见过的都不适合？说实话你够幸运了。G禁了很多经典，新题
: 不断，而你拿到的是教科书的经典算法。

n*n2011-10-11 07:10

41 楼

只能考你刚背过的文章才公平，是这个道理吗？

【在 i*****h 的大作中提到】

: 你要考人文采不考论文也不考散文。来，三字经默写一遍，小时候可都读过，够照顾你
: 吧。是这个道理吗？

i*h2011-10-11 07:10

42 楼

三哥三姐考吗？老白考吗？为什么只有老中考？要不要再自我检讨下，因为洋大人
在考验我啊

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

: 只能考你刚背过的文章才公平，是这个道理吗？