Redian新闻
>
艾米古.,今年清明你吃了吗? (转载)
avatar
艾米古.,今年清明你吃了吗? (转载)# Joke - 肚皮舞运动
p*i
1
材料:
高汤:牛骨头
焖料:beef stew一磅半,土豆两个,洋葱一个,胡萝卜两个,黄油三大勺子
调味料:新鲜茴香dill叶子,新鲜欧洲香芹parsley叶子,香叶四片,欧洲防风parsnip
一根,大蒜四瓣,盐,黑胡椒,酸奶油
酥皮一大块
做法:
1. 牛骨头洗干净焯水后熬好高汤备用。
2. 土豆,洋葱,胡萝卜,欧洲防风,大蒜去皮切小块备用。
3. 锅烧热放黄油融化,转中火,加入牛肉块四面煎黄,撒少许盐,小火煎五分钟左右
。盛出后放入小陶罐底部,每个罐子放几块。
4. 分别用黄油炒香土豆,洋葱和胡萝卜,炒到五成熟,分别放入小陶罐里。
5. 加入高汤,量控制加到陶罐一半高度左右。
6. 撒入茴香,香芹,香叶,欧洲防风块儿,大蒜,加入现磨黑胡椒和盐少许调味。
7. 盖上盖子,400F预热好的烤箱烤1小时。如果盖酥皮,需先焖烤好食材分小罐子,盖
好酥皮后刷蛋液,撒上cheese丝丝,400F烤一刻钟。
8. 吃的时候汤里放上一大勺酸奶油,配面包,沙拉菜,酸黄瓜。
注意事项:
1. 肉类可以用羊肉,鸡肉,鱼肉,猪肉来代替,焖烤的时间要相应调整。全素的吃法
可以用鹰嘴豆和素油代替黄油和肉。
2. 蔬菜根据自己喜欢的内容调整,可以加蘑菇和蕃茄进一步调味。蔬菜切的大小要跟
所配肉类调整,如牛羊肉这种不好熟的,菜可以切大块,鸡肉这种好熟的肉,菜要切小
丁。以菜肉同时出炉都焖熟为准。
3. 如果没有那么多小陶罐子,可以用大陶罐子或者铸铁珐琅锅烤后,分小份上菜。
4. 如果陶罐子没有盖子,可以揉个面团放上去当盖子一起烤。注意面包的种类与所焖
的肉类要配,而且以出炉时面包烤好和菜肉都焖熟为准。这里有个面包方子可以参考 :
10oz 面粉,4oz黄油,一个蛋,半小勺baking powder,2tbsp milk 混匀,揉团,分
小份擀平,盖在罐子上。
5. 如果买不到欧式香料,用中式香料做也可以,我想回同样好吃。不过就不是俄式的
了。
6. 如果用酥皮(puff pastry sheet)代替面团当盖子,要特别注意烤的时间。因为
pastry puff通常十五分钟就烤好了。但肉类和块类蔬菜十五分钟烤不好。所以,建议
大罐子焖熟肉和菜,分小罐子烤的时候加酥皮盖上,然后烤十五分钟左右。
7. 牛肉高汤可以用牛肉汤粉加开水代替。
avatar
p*e
2
发一下自己碰到的两道题(面试好像也没签NDA啥的)
第一个是道以前没见过的题 :
有一群人,他们之间或者是朋友,或者是敌人,或者没有关系,程序的输入是一组关系
,如(甲,乙,朋友),(乙,丙,敌人)...
有一个附加的规则是,朋友的朋友还是朋友,敌人的敌人也是朋友人,敌人的朋友和朋
友的敌人都是敌人。
给你一组上面提到过的输入,要求是再任给两个新的人,输出他们之间的关系。
这道题答的不好,虽然最后嗑嗑绊绊给出了正确的答案,但是把一轮面试的时间都用光
了。当中面试官也没给啥提示,只是时不时问一下我当前的算法的复杂度,以及“能不
能再快一点”。。。
第二道题也是没见过到的面试题,不过这个问题我以前正好想过,答的还好:
如果你用过文件比较的工具,像各种各样的diff, 说一下这个功能是怎么实现的。
再说一下自己当前的情况,国内硕士毕业工作两年,国内面试后,没有适合的Head
count, 但正好碰到好心人帮我refer google MV, 然后MV的hr帮我move to next step
了,大概三周多前问我要了reference,transcripts等等(我说的reference也都被联
系过了,包括国内的老师和国外的同学),两周前安排了一个engineer和我打了电话(
但是因为印度口音很重,又问了很多技术问题,交流的很差)。之后一直没有消息(当
中好像hr OOO了一周),最近hr的消息就是“we're trying to determine the best
fit".. (四天前),然后我一个在国内的google的同学又接了个电话问了些关于我的事
情。
有人知道这算是什么情况吗?还是说找不到合适的组就先把我晾着?刚刚也看到有贴子
说现在google hiring slow down了。自己毕业找工作的时候运气就一直很背,这次的
机会也算是我的dream offer,希望能时来转啊。。
avatar
F*n
3
刚成立的公司。老板说我就是cofunder, 办h1b,绿卡什么的都没有问题。但是这个刚成
立一两个月的公司,资产可能只有4,5百万,有资格帮我办绿卡吗?
avatar
e*e
4
【 以下文字转载自 gardening 讨论区 】
发信人: Lydia (lydia), 信区: gardening
标 题: 艾米古.,今年清明你吃了吗?
发信站: BBS 未名空间站 (Thu May 5 11:37:40 2011, 美东)
闲话少说,大家看图.
avatar
c*p
5
第2题是用的LCS吧

【在 p****e 的大作中提到】
: 发一下自己碰到的两道题(面试好像也没签NDA啥的)
: 第一个是道以前没见过的题 :
: 有一群人,他们之间或者是朋友,或者是敌人,或者没有关系,程序的输入是一组关系
: ,如(甲,乙,朋友),(乙,丙,敌人)...
: 有一个附加的规则是,朋友的朋友还是朋友,敌人的敌人也是朋友人,敌人的朋友和朋
: 友的敌人都是敌人。
: 给你一组上面提到过的输入,要求是再任给两个新的人,输出他们之间的关系。
: 这道题答的不好,虽然最后嗑嗑绊绊给出了正确的答案,但是把一轮面试的时间都用光
: 了。当中面试官也没给啥提示,只是时不时问一下我当前的算法的复杂度,以及“能不
: 能再快一点”。。。

avatar
z*i
6
可以

★ 发自iPhone App: ChineseWeb 7.7

【在 F*****n 的大作中提到】
: 刚成立的公司。老板说我就是cofunder, 办h1b,绿卡什么的都没有问题。但是这个刚成
: 立一两个月的公司,资产可能只有4,5百万,有资格帮我办绿卡吗?

avatar
e*e
7
最后一张,不小心掉邻居草坪里又该有人骂街:妈的,没功德,出来遛狗也不带个粪兜
儿!
avatar
p*u
8
1题是不是用disjointed set?朋友在一个set里。 对每个set,同时记录对应的敌人set。
avatar
C*a
9

这个好。

【在 e******e 的大作中提到】
: 最后一张,不小心掉邻居草坪里又该有人骂街:妈的,没功德,出来遛狗也不带个粪兜
: 儿!

avatar
p*e
10
楼上两个都对。
第一题我觉的比较tricky的地方是两个人可能没有关系,disjointed set是比较适合的
data structure。
我一开始用了一些图的算法来处理这个问题,折腾到最后才想到disjointed set。。
后来一翻书algorithm in C第一章就讨论了一个差不多的问题(更简单些),懊恼啊。。
第二题想到用LCS就没什么难度了。。
avatar
p*n
11
吃了,很好吃。。。
avatar
w*r
12
求教lcs是什么?

。。

【在 p****e 的大作中提到】
: 楼上两个都对。
: 第一题我觉的比较tricky的地方是两个人可能没有关系,disjointed set是比较适合的
: data structure。
: 我一开始用了一些图的算法来处理这个问题,折腾到最后才想到disjointed set。。
: 后来一翻书algorithm in C第一章就讨论了一个差不多的问题(更简单些),懊恼啊。。
: 第二题想到用LCS就没什么难度了。。

avatar
p*p
13
这是神马玩意儿?哪个民族清明节吃这个?
avatar
y*g
14
longest common sub sequence

【在 w****r 的大作中提到】
: 求教lcs是什么?
:
: 。。

avatar
w*r
15
倒数第2张最恶
avatar
w*r
16
哦。。就是用个DP吗?

【在 y*******g 的大作中提到】
: longest common sub sequence
avatar
m*t
17
哈哈哈哈,我第一次见也吓一跳呢。。。很像糯米糍,但是有艾草味

【在 p*****p 的大作中提到】
: 这是神马玩意儿?哪个民族清明节吃这个?
avatar
b*8
18
第一题大概这就是正解了。我也被问到了,说的是输入是两两关系,有父子姐妹等等关
系。问啥数据结构,如何判断两人是否有关系(如何比较快判断,给出了个O(1)时间的
),复杂度,等等。

。。

【在 p****e 的大作中提到】
: 楼上两个都对。
: 第一题我觉的比较tricky的地方是两个人可能没有关系,disjointed set是比较适合的
: data structure。
: 我一开始用了一些图的算法来处理这个问题,折腾到最后才想到disjointed set。。
: 后来一翻书algorithm in C第一章就讨论了一个差不多的问题(更简单些),懊恼啊。。
: 第二题想到用LCS就没什么难度了。。

avatar
s*y
19
哪里买得到啊?

【在 m********t 的大作中提到】
: 哈哈哈哈,我第一次见也吓一跳呢。。。很像糯米糍,但是有艾草味
avatar
t*e
20
要我解的话,
第一题transitive closure
第二题edit distance
avatar
m*t
21
呃,在国内吃的,不知道这边有没有卖的。。。自己做吧,看起来不难

【在 s******y 的大作中提到】
: 哪里买得到啊?
avatar
d*n
22
不太一样。Union-Find解决的问题只是单一conectivity,这里面的conectivity有两种
:朋友,敌人。

【在 b*******8 的大作中提到】
: 第一题大概这就是正解了。我也被问到了,说的是输入是两两关系,有父子姐妹等等关
: 系。问啥数据结构,如何判断两人是否有关系(如何比较快判断,给出了个O(1)时间的
: ),复杂度,等等。
:
: 。。

avatar
p*n
23
汉族
俺家乡清明节吃青团子,不过比楼主做的好看

【在 p*****p 的大作中提到】
: 这是神马玩意儿?哪个民族清明节吃这个?
avatar
s*x
24
感觉是不是在 node 里面加一 enemy 的 pointer 指向另外一个 set 的 root 就可
以了 ?

【在 d***n 的大作中提到】
: 不太一样。Union-Find解决的问题只是单一conectivity,这里面的conectivity有两种
: :朋友,敌人。

avatar
A*l
25
浙江?我们家也吃。

【在 p****n 的大作中提到】
: 汉族
: 俺家乡清明节吃青团子,不过比楼主做的好看

avatar
c*j
26
第一道题,请问可以这样想吗?
each person is a vertex in this graph G(V,E). then use DFS find the path
between the two V_1, V_2,
(discussion: what if there are multiple paths?) From V_1 a value x, find the
V_2 value
using this path.
then edge_friend: do nothing, edge_enemy : *(-1):
then if value <0; then enemy; if >0; friend
avatar
s*y
27
这里哪里买得到艾草啊?

【在 m********t 的大作中提到】
: 呃,在国内吃的,不知道这边有没有卖的。。。自己做吧,看起来不难
avatar
g*k
28
应该是用 disjoint-set 来表示 friends'closure,敌人应该用adjacency list来表示。
判断朋友关系很简单就是直接用disjoint-set的root来判断。
判断敌人就比较麻烦,需要遍历该set下所有元素的敌人adjacency list。
只不过disjoint-set forests似乎不仅仅需要parent指针,还需要children指针,
没有想到一个好的办法来遍历该set中所有的节点。

【在 p****e 的大作中提到】
: 发一下自己碰到的两道题(面试好像也没签NDA啥的)
: 第一个是道以前没见过的题 :
: 有一群人,他们之间或者是朋友,或者是敌人,或者没有关系,程序的输入是一组关系
: ,如(甲,乙,朋友),(乙,丙,敌人)...
: 有一个附加的规则是,朋友的朋友还是朋友,敌人的敌人也是朋友人,敌人的朋友和朋
: 友的敌人都是敌人。
: 给你一组上面提到过的输入,要求是再任给两个新的人,输出他们之间的关系。
: 这道题答的不好,虽然最后嗑嗑绊绊给出了正确的答案,但是把一轮面试的时间都用光
: 了。当中面试官也没给啥提示,只是时不时问一下我当前的算法的复杂度,以及“能不
: 能再快一点”。。。

avatar
p*p
29
青团我知道,江浙沪一带某些族群吃这个,但是,不是这个鸟样啊

【在 p****n 的大作中提到】
: 汉族
: 俺家乡清明节吃青团子,不过比楼主做的好看

avatar
y*g
30
朋友和敌人是disjoint的,所以算出所有朋友的set,然后把敌人的情况都转化成set
representive ,放到一个hash就好了把

【在 d***n 的大作中提到】
: 不太一样。Union-Find解决的问题只是单一conectivity,这里面的conectivity有两种
: :朋友,敌人。

avatar
s*e
31
我们老家也有这个风俗。形状不同。
avatar
d*n
32
我觉得也是这样,搞清楚哪两个集合之间是敌人即可。感觉处理新的数据时如何合并现
有集合会tricky一些。

【在 s**x 的大作中提到】
: 感觉是不是在 node 里面加一 enemy 的 pointer 指向另外一个 set 的 root 就可
: 以了 ?

avatar
g*k
33
想了想,只需要一个disjoint-set来表示friends'closure.
但是每个set的root,有一个指针指向enemy set.
for each new friend pair(a,b), union(a, b) and union(root(a).enemy, root(b).
enemy)
for each enemy pair (a,b). union(root(a).enemy, b) and union(a, root(b).
enemy)
那么给定两个人,检测关系应该就容易了。
朋友就是判断是否在同一个set,
敌人就是判断另一个是否在敌人set里。

示。

【在 g*****k 的大作中提到】
: 应该是用 disjoint-set 来表示 friends'closure,敌人应该用adjacency list来表示。
: 判断朋友关系很简单就是直接用disjoint-set的root来判断。
: 判断敌人就比较麻烦,需要遍历该set下所有元素的敌人adjacency list。
: 只不过disjoint-set forests似乎不仅仅需要parent指针,还需要children指针,
: 没有想到一个好的办法来遍历该set中所有的节点。

avatar
g*y
34
第一题可以用染色来做,朋友染同色,敌人染异色。把图分成k个相邻子图,用2k种颜
色染完所有点。以后判断朋友敌人就很简单。
public class FriendEnemy {
private int[] color;

public void buildRelationGraph(int N, int[] a, int[] b, int[] relation)
throws Exception {
color = new int[N];
int[][] g = new int[N][N];

for (int i=0; iif (relation[i] == 0) { // enemy
g[a[i]][b[i]] = -1;
g[b[i]][a[i]] = -1;
}
else { // friend
g[a[i]][b[i]] = 1;
g[b[i]][a[i]] = 1;
}
}

int c = 1;
for (int i=0; iif (color[i] == 0) {
dfs(N, g, i, c);
c += 2;
}
}
}

private void dfs(int N, int[][] g, int i, int c) throws Exception {
if (color[i] > 0) {
if (color[i] != c) throw new Exception("Relation graph has
contradiction!");
return;
}

color[i] = c;
for (int j=0; jif (g[i][j] == 1) {
dfs(N, g, j, c);
}
else if (g[i][j] == -1) {
int nextC = ((c+1)/2)*4 - 1 - c;
dfs(N, g, j, nextC);
}
}
}

/**
* 1: friend
* 0: enemy
* -1: no relationship
*/
public int getRelation(int i, int j) {
if (color[i] == color[j]) return 1;
if (color[i]/2 == color[j]/2) return 0;
return -1;
}
}
avatar
g*i
35
A的敌人和A的朋友的敌人彼此之间算不算朋友呢? 三国鼎立也有可能啊.

).

【在 g*****k 的大作中提到】
: 想了想,只需要一个disjoint-set来表示friends'closure.
: 但是每个set的root,有一个指针指向enemy set.
: for each new friend pair(a,b), union(a, b) and union(root(a).enemy, root(b).
: enemy)
: for each enemy pair (a,b). union(root(a).enemy, b) and union(a, root(b).
: enemy)
: 那么给定两个人,检测关系应该就容易了。
: 朋友就是判断是否在同一个set,
: 敌人就是判断另一个是否在敌人set里。
:

avatar
h*8
36
mark

。。

【在 p****e 的大作中提到】
: 楼上两个都对。
: 第一题我觉的比较tricky的地方是两个人可能没有关系,disjointed set是比较适合的
: data structure。
: 我一开始用了一些图的算法来处理这个问题,折腾到最后才想到disjointed set。。
: 后来一翻书algorithm in C第一章就讨论了一个差不多的问题(更简单些),懊恼啊。。
: 第二题想到用LCS就没什么难度了。。

avatar
g*k
37
算啊,在我说的那个算法里,
A的敌人,和A的朋友的敌人是要做union的。
具体体现在,如果a和b是敌人。
union(root(a).enemy,b)
这里root(a)表示a的所有朋友,root(a).enemy表示a所有朋友的敌人。
那么union(root(a).enemy,b)的结果就是
a的所有朋友的敌人和b的所有朋友构成更大一个 friends' closure.

【在 g*****i 的大作中提到】
: A的敌人和A的朋友的敌人彼此之间算不算朋友呢? 三国鼎立也有可能啊.
:
: ).

avatar
c*n
38
我个人认为一个Dijkstra就可以解决问题了。
如果A是B的朋友,the edge value is 1.
如果A是B的敌人。the edge value is 0.
如果A->B->C,A和C的关系就是~(e(A, B) ^e(B, C))
avatar
p*e
39
尝试回忆一下我面试时给出的做法及我的思路:
我一开始就是给你的这种解法(我是用Floyd算法,给出所有点对的值),只可惜效率
不高:
假设一共有V个人,和E个关系,
那么最坏情况下,用Dijkstra算法判断任意两个人的关系,需要O(E + VlogV)的时间,
不用额外空间的话。
用Floyd算法的话,需要O(V^3)的时间预处理,O(V^2)的缓存,之后只需要O(1)的时间
判断。
这时间面试官说,如果给出的关系很少,人很多,你这个算法太浪费了。
那我想,他要的算法,复杂度必须是基于E的,才有戏。而基于关系来处理问题,肯定
把关系中出现的人加到一个一个group中间去的(因为不能再cover所有的人了)
于是我给了一个新的做法:
当我看到一个关系(A,B 朋友)的时候,我就把A,B加到一个group中去,如果出来一
个(B,C,敌人)的时候,就把C加到另外一个group中去。总之是把A的朋友们放到一个
group, 其它人放到另外一个group。这里忽略一些细节,最后可以得到两个group., 然
后对新的一对人,只要看一下他们在哪个group中就行了。这里我用的对应group的数据
结构是一个set.
针对这个算法,其实有点disjointed set的意思了,所以面试官跟我讨论了一下这个方
法的优化(太阴险了),我就跟着他一步步优化了。。
然后他突然又说,你这个算法不对啊,如果A,B是朋友,C,D也是朋友,那你这个算法
会输出A,C是敌人,其实他们没有关系。
后来我一想,日啊,上当了,其实这个关系是描述了很多组的朋友和敌人关系,这样才
能支持“没有关系”的这种情况。
然后到这一步我才想到其中的关键是如何快速的合并两个group,才想到了disjointed
set,不过时间已经用光鸟 :(
看了下一些朋友给出的解法,我事后想到的解法是:
1. 用图论的做法的应该是对的,也不难,只是效率不高,特别是人数很多的情况下。
2. 用disjointed set, 我现在的想法是,应该扩展一下现有的disjointed set结构,
一对朋友/敌人的group为一组,从数据结构上看,可以让朋友为一个tree, 敌人为一个
tree,然后让他们指向同一个root.
如果新来的关系是(A,B,朋友),那就在disjointed set中找A或B,找到之后,把它们
的朋友group merge起来, 敌人group也merge起来。
如果新来的关系是(A,B,敌人),那同样找到A或B后,把A的朋友与B的敌人merge, A的
敌人与B的朋友merge.
这样的话,disjointed set中查找A和B是O(1)的(要用上一些路径压缩啥的),merge
group也是O(1)的,整个预处理用O(E)的时候即可,额外空间也是O(E)的。

【在 c*******n 的大作中提到】
: 我个人认为一个Dijkstra就可以解决问题了。
: 如果A是B的朋友,the edge value is 1.
: 如果A是B的敌人。the edge value is 0.
: 如果A->B->C,A和C的关系就是~(e(A, B) ^e(B, C))

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。