p****e
发帖数: 37 | 1 发一下自己碰到的两道题（面试好像也没签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，希望能时来转啊。。 |
c****p
发帖数: 6474 | 2 第2题是用的LCS吧
【在 p****e 的大作中提到】
: 发一下自己碰到的两道题（面试好像也没签NDA啥的）
: 第一个是道以前没见过的题 ：
: 有一群人，他们之间或者是朋友，或者是敌人，或者没有关系，程序的输入是一组关系
: ，如（甲，乙，朋友），（乙，丙，敌人）...
: 有一个附加的规则是，朋友的朋友还是朋友，敌人的敌人也是朋友人，敌人的朋友和朋
: 友的敌人都是敌人。
: 给你一组上面提到过的输入，要求是再任给两个新的人，输出他们之间的关系。
: 这道题答的不好，虽然最后嗑嗑绊绊给出了正确的答案，但是把一轮面试的时间都用光
: 了。当中面试官也没给啥提示，只是时不时问一下我当前的算法的复杂度，以及“能不
: 能再快一点”。。。
|
p*****u
发帖数: 310 | 3 1题是不是用disjointed set？朋友在一个set里。 对每个set，同时记录对应的敌人set。 |
p****e
发帖数: 37 | 4 楼上两个都对。
第一题我觉的比较tricky的地方是两个人可能没有关系，disjointed set是比较适合的
data structure。
我一开始用了一些图的算法来处理这个问题，折腾到最后才想到disjointed set。。
后来一翻书algorithm in C第一章就讨论了一个差不多的问题（更简单些），懊恼啊。。
第二题想到用LCS就没什么难度了。。 |
w****r
发帖数: 245 | 5 求教lcs是什么？
。。
【在 p****e 的大作中提到】
: 楼上两个都对。
: 第一题我觉的比较tricky的地方是两个人可能没有关系，disjointed set是比较适合的
: data structure。
: 我一开始用了一些图的算法来处理这个问题，折腾到最后才想到disjointed set。。
: 后来一翻书algorithm in C第一章就讨论了一个差不多的问题（更简单些），懊恼啊。。
: 第二题想到用LCS就没什么难度了。。
|
y*******g
发帖数: 6599 | 6 longest common sub sequence
【在 w****r 的大作中提到】
: 求教lcs是什么？
:
: 。。
|
w****r
发帖数: 245 | 7 哦。。就是用个DP吗？
【在 y*******g 的大作中提到】
: longest common sub sequence
|
b*******8
发帖数: 37364 | 8 第一题大概这就是正解了。我也被问到了，说的是输入是两两关系，有父子姐妹等等关
系。问啥数据结构，如何判断两人是否有关系（如何比较快判断，给出了个O(1)时间的
），复杂度，等等。
。。
【在 p****e 的大作中提到】
: 楼上两个都对。
: 第一题我觉的比较tricky的地方是两个人可能没有关系，disjointed set是比较适合的
: data structure。
: 我一开始用了一些图的算法来处理这个问题，折腾到最后才想到disjointed set。。
: 后来一翻书algorithm in C第一章就讨论了一个差不多的问题（更简单些），懊恼啊。。
: 第二题想到用LCS就没什么难度了。。
|
t******e
发帖数: 98 | 9 要我解的话，
第一题transitive closure
第二题edit distance |
d***n
发帖数: 65 | 10 不太一样。Union-Find解决的问题只是单一conectivity，这里面的conectivity有两种
：朋友，敌人。
【在 b*******8 的大作中提到】
: 第一题大概这就是正解了。我也被问到了，说的是输入是两两关系，有父子姐妹等等关
: 系。问啥数据结构，如何判断两人是否有关系（如何比较快判断，给出了个O(1)时间的
: ），复杂度，等等。
:
: 。。
|
|
|
s**x
发帖数: 7506 | 11 感觉是不是在 node 里面加一 enemy 的 pointer 指向另外一个 set 的 root 就可
以了 ？
【在 d***n 的大作中提到】
: 不太一样。Union-Find解决的问题只是单一conectivity，这里面的conectivity有两种
: ：朋友，敌人。
|
c**j
发帖数: 103 | 12 第一道题，请问可以这样想吗？
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 |
g*****k
发帖数: 623 | 13 应该是用 disjoint-set 来表示 friends'closure，敌人应该用adjacency list来表示。
判断朋友关系很简单就是直接用disjoint-set的root来判断。
判断敌人就比较麻烦，需要遍历该set下所有元素的敌人adjacency list。
只不过disjoint-set forests似乎不仅仅需要parent指针，还需要children指针，
没有想到一个好的办法来遍历该set中所有的节点。
【在 p****e 的大作中提到】
: 发一下自己碰到的两道题（面试好像也没签NDA啥的）
: 第一个是道以前没见过的题 ：
: 有一群人，他们之间或者是朋友，或者是敌人，或者没有关系，程序的输入是一组关系
: ，如（甲，乙，朋友），（乙，丙，敌人）...
: 有一个附加的规则是，朋友的朋友还是朋友，敌人的敌人也是朋友人，敌人的朋友和朋
: 友的敌人都是敌人。
: 给你一组上面提到过的输入，要求是再任给两个新的人，输出他们之间的关系。
: 这道题答的不好，虽然最后嗑嗑绊绊给出了正确的答案，但是把一轮面试的时间都用光
: 了。当中面试官也没给啥提示，只是时不时问一下我当前的算法的复杂度，以及“能不
: 能再快一点”。。。
|
y*******g
发帖数: 6599 | 14 朋友和敌人是disjoint的，所以算出所有朋友的set，然后把敌人的情况都转化成set
representive ,放到一个hash就好了把
【在 d***n 的大作中提到】
: 不太一样。Union-Find解决的问题只是单一conectivity，这里面的conectivity有两种
: ：朋友，敌人。
|
d***n
发帖数: 65 | 15 我觉得也是这样，搞清楚哪两个集合之间是敌人即可。感觉处理新的数据时如何合并现
有集合会tricky一些。
【在 s**x 的大作中提到】
: 感觉是不是在 node 里面加一 enemy 的 pointer 指向另外一个 set 的 root 就可
: 以了 ？
|
g*****k
发帖数: 623 | 16 想了想，只需要一个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中所有的节点。
|
g**********y
发帖数: 14569 | 17 第一题可以用染色来做，朋友染同色，敌人染异色。把图分成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; i
if (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; i
if (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; j
if (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;
}
} |
g*****i
发帖数: 2162 | 18 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里。
:
|
h**********8
发帖数: 267 | 19 mark
。。
【在 p****e 的大作中提到】
: 楼上两个都对。
: 第一题我觉的比较tricky的地方是两个人可能没有关系，disjointed set是比较适合的
: data structure。
: 我一开始用了一些图的算法来处理这个问题，折腾到最后才想到disjointed set。。
: 后来一翻书algorithm in C第一章就讨论了一个差不多的问题（更简单些），懊恼啊。。
: 第二题想到用LCS就没什么难度了。。
|
g*****k
发帖数: 623 | 20 算啊，在我说的那个算法里，
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的朋友的敌人彼此之间算不算朋友呢? 三国鼎立也有可能啊.
:
: ).
|
|
|
c*******n
发帖数: 112 | 21 我个人认为一个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)） |
p****e
发帖数: 37 | 22 尝试回忆一下我面试时给出的做法及我的思路：
我一开始就是给你的这种解法（我是用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)）
|
s*****y
发帖数: 897 | |
