i****y
发帖数: 58 | 1 热腾腾 血淋淋的面经来了。。
First 45min
1. 有一种压缩方式，把food->f2d, tea->t1a，这种，然后现在要搞一个dictionary，
问你咋设计，还要实现判断isUnique方法. 我用了trie的变种，用level表示当中那个
数字，应该有更好的方法
class Trie{
int level;
ArrayList[] words;
Trie nextLevelTrie;
}
2. 问问题
我说我投的是Test职位，问具体工作内容是啥。他说他也是SET，但是不写test case两
年了，google没有专门的测试组，SET的manager和developer的是同一个，上班也一起
，开会也一起，主要还是需要开发，具体是不是需要测试也和team有关。
Second 45min
1. why google
2. 有很多个文件信息，每个文件信息里都有一个Person, 以及他的father, mother信
息，设计一个结构，并判断if two persons are related to each other. 婚姻关系不
是related。爷爷和孙子是related。
我搞这个relationship就搞了很久。第一眼觉得应该用LCA做，然后各种往上面套，于
是就悲剧了。
感觉google就是执着于树。。。各位加油。。。 |
i***h
发帖数: 12655 | |
p*****2
发帖数: 21240 | 3 把food->f2d, tea->t1a
这个没看懂
是SET，不是SDT，这个怎么都没搞清？ |
H****s
发帖数: 247 | 4 第二个是graph吧，用BFS同时从两个端点搜索，应该就能得到 |
x*******6
发帖数: 262 | |
p*****2
发帖数: 21240 | 6 第二题应该是graph吧？
如果有共同祖先就算是有关系的话。DFS就够了。 |
l********7
发帖数: 19 | |
i****y
发帖数: 58 | 8 是啊 我一开始就想往LCA上套，后来发现不对，然后就觉得是graph，但是思路很混乱
，该好好准备一下graph了
【在 p*****2 的大作中提到】
: 第二题应该是graph吧？
: 如果有共同祖先就算是有关系的话。DFS就够了。
|
k***g
发帖数: 58 | 9 整个data structure应该是
class Node {
Node father;
Node mother;
HashSet children;
}
这个应该不是graph，应为没有circle（不会变态的有乱伦关系吧……），整体看起来
像forest
给两个Node N1,N2，从N1用DFS往father, mother两个分支找N2，以及从N2用DFS往
father, mother两个分支找N1。找到即有，找不到即无…… |
p*****2
发帖数: 21240 | 10
不用存children吧？
【在 k***g 的大作中提到】
: 整个data structure应该是
: class Node {
: Node father;
: Node mother;
: HashSet children;
: }
: 这个应该不是graph，应为没有circle（不会变态的有乱伦关系吧……），整体看起来
: 像forest
: 给两个Node N1,N2，从N1用DFS往father, mother两个分支找N2，以及从N2用DFS往
: father, mother两个分支找N1。找到即有，找不到即无……
|
|
|
k***g
发帖数: 58 | 11 恩，根据题目要求的确不用存
【在 p*****2 的大作中提到】
:
: 不用存children吧？
|
j********x
发帖数: 2330 | |
w****x
发帖数: 2483 | 13
不用把, 就是
struct NODE
{
vector relation;
};
就可以了吧
【在 k***g 的大作中提到】
: 整个data structure应该是
: class Node {
: Node father;
: Node mother;
: HashSet children;
: }
: 这个应该不是graph，应为没有circle（不会变态的有乱伦关系吧……），整体看起来
: 像forest
: 给两个Node N1,N2，从N1用DFS往father, mother两个分支找N2，以及从N2用DFS往
: father, mother两个分支找N1。找到即有，找不到即无……
|
h*******e
发帖数: 1377 | 14 couple 不算 related , brothers and sisters算related么 |
p**l
发帖数: 125 | 15 relation题:
如果是related的话, 必定是N1,N2都在同一条path上, 而不是common ancestor(
otherwise husband and wife would be related).
所以从N1开始, 向上走, hash所经过的nodes. 如果N2在hash的nodes里面, 就是
related.
child
/\
father mother
还需要从N2开始, 向上走, 如果N1在经过的nodes里面, 就是related.
两次均没有就是unrelated. Worst case O(n)
class Node
{
Node* father;
Node* monther;
}
【在 i****y 的大作中提到】
: 热腾腾 血淋淋的面经来了。。
: First 45min
: 1. 有一种压缩方式，把food->f2d, tea->t1a，这种，然后现在要搞一个dictionary，
: 问你咋设计，还要实现判断isUnique方法. 我用了trie的变种，用level表示当中那个
: 数字，应该有更好的方法
: class Trie{
: int level;
: ArrayList[] words;
: Trie nextLevelTrie;
: }
|
h*******e
发帖数: 1377 | 16 husband and wife 没有common ancestor...
【在 p**l 的大作中提到】
: relation题:
: 如果是related的话, 必定是N1,N2都在同一条path上, 而不是common ancestor(
: otherwise husband and wife would be related).
: 所以从N1开始, 向上走, hash所经过的nodes. 如果N2在hash的nodes里面, 就是
: related.
: child
: /\
: father mother
: 还需要从N2开始, 向上走, 如果N1在经过的nodes里面, 就是related.
: 两次均没有就是unrelated. Worst case O(n)
|
p**l
发帖数: 125 | 17 which is correct, according to LZ
"婚姻关系不是related。爷爷和孙子是related。"
【在 h*******e 的大作中提到】
: husband and wife 没有common ancestor...
|
h*******e
发帖数: 1377 | 18 我觉得如果和现实相同 brothers 也叫realated 你的算法大体上可用
n1 为root bfs 上走 所有点 做 hash table， 之后n2 本身 和 n2 上走的 点
做hash 如果 第二个 hash 在第一个 hash 表中说明 两个人 related
【在 p**l 的大作中提到】
: which is correct, according to LZ
: "婚姻关系不是related。爷爷和孙子是related。"
|
p**l
发帖数: 125 | 19 可能我没怎么懂你的意思, 如果你想的是以n1为root来做subtree做bfs, 那就误会我的
意思了.
至于child 1 和 child 2 和child n是否是因为兄弟而related. 我不认为这样的假设
有道理. 因为如果是的话, 那同父异母也可以? 当然如果是看blood构成成分的话这就
完全是另一道题了, 比如1/32的father blood和1/64father blood也可能是related.
但这样的不确定性不会用来出题的. 我还是觉得这是一个tree/hashtable的题.
【在 h*******e 的大作中提到】
: 我觉得如果和现实相同 brothers 也叫realated 你的算法大体上可用
: n1 为root bfs 上走 所有点 做 hash table， 之后n2 本身 和 n2 上走的 点
: 做hash 如果 第二个 hash 在第一个 hash 表中说明 两个人 related
|
B***n
发帖数: 84 | 20 有兄弟姐妹怎么办？
比如N1和N2是兄弟
如果兄弟不算related的话，那father，mother要重复出现在N1和N2两个分支？
如果兄弟算related的话，那他们在一个树里面是什么关系？
【在 k***g 的大作中提到】
: 整个data structure应该是
: class Node {
: Node father;
: Node mother;
: HashSet children;
: }
: 这个应该不是graph，应为没有circle（不会变态的有乱伦关系吧……），整体看起来
: 像forest
: 给两个Node N1,N2，从N1用DFS往father, mother两个分支找N2，以及从N2用DFS往
: father, mother两个分支找N1。找到即有，找不到即无……
|
|
|
t*******2
发帖数: 292 | 21 你的assumption是近亲不结婚才是这样。。。。。
题目木说，要问问interviewer...
husband and wife 没有common ancestor...
【在 h*******e 的大作中提到】
: husband and wife 没有common ancestor...
|
h*u
发帖数: 122 | |
w***o
发帖数: 109 | 23 我被问过这个题，面试官说的很清楚，夫妻不算有blood关系，而弟兄姐妹算，每个父
母和所有的儿女算，问如何设计数据结构，使得任给两个person能判断他们是不是有
blood关系。其实就是找两个person是否有共同祖先。
我先说建从父母到子女的有向边的图，然后对图中所有没有祖先的root进行DFS或BFS遍
历，如果某个root的所有子孙同时包含了两个person那他们就有blood关系。
他不满意，不是他想要的答案，又挑不出错，就给了一个函数头，说你没办法access所
有indegree是0的Node，只能从函数提供的参数（两个Node)出发。那我说把有向边掉过
来，注意，跟很多人一样我想当然的认为是没有近亲婚姻的，写了个很简单的DFS，他
不断的提示，我也没想近亲结婚，最后他跳出来画了一个diamond，我才知道要考虑这
种情况。
后来跟他讨论了用着色和HashSet两种方法各自的优缺点。基本就是着色不能thread
safe。看样子他比较喜欢用HashSet。 |
e****e
发帖数: 418 | 24 Directed graph from children to parents.
From persion1, persion2 build set1, set2 by BFS. Also add persion1 in set1,
person2 in set2.
On each step of BFS, compare if there is a common node in set1 and set2.(can
be optimized by only comparing newly added nodes with the other sets to
avoid comparing the same nodes repeatedly.) |
m****t
发帖数: 2329 | 25 why GOOGLE.
如果回答是之一，他们的饭好，会如何，哈哈。
话说，我觉得吃的，真的是个重要的考虑因素。
祝福楼主mm。 |
e***s
发帖数: 799 | 26 第一题没看懂。
第二题
有向图，分别两个节点BFS，走过的放到HASHSET，看有没有重复？有重复则related？ |
v*********3
发帖数: 40 | 27 那请问各位，是同时BFS吗，用两个thread，还是一直走到尽头后，再开始另外一个BFS
，多谢！
【在 e***s 的大作中提到】
: 第一题没看懂。
: 第二题
: 有向图，分别两个节点BFS，走过的放到HASHSET，看有没有重复？有重复则related？
|
e***s
发帖数: 799 | 28 我觉得要能搞出两个thread肯定是更好的，但是要问大牛，怎么考虑thread-safe。。
我也不懂。。。。。
BFS
【在 v*********3 的大作中提到】
: 那请问各位，是同时BFS吗，用两个thread，还是一直走到尽头后，再开始另外一个BFS
: ，多谢！
|
h**i
发帖数: 431 | 29 第一题啥意思，楼主具体说一下，造福后人赞rp
【在 i****y 的大作中提到】
: 热腾腾 血淋淋的面经来了。。
: First 45min
: 1. 有一种压缩方式，把food->f2d, tea->t1a，这种，然后现在要搞一个dictionary，
: 问你咋设计，还要实现判断isUnique方法. 我用了trie的变种，用level表示当中那个
: 数字，应该有更好的方法
: class Trie{
: int level;
: ArrayList[] words;
: Trie nextLevelTrie;
: }
|
i****y
发帖数: 58 | 30 热腾腾 血淋淋的面经来了。。
First 45min
1. 有一种压缩方式，把food->f2d, tea->t1a，这种，然后现在要搞一个dictionary，
问你咋设计，还要实现判断isUnique方法. 我用了trie的变种，用level表示当中那个
数字，应该有更好的方法
class Trie{
int level;
ArrayList[] words;
Trie nextLevelTrie;
}
2. 问问题
我说我投的是Test职位，问具体工作内容是啥。他说他也是SET，但是不写test case两
年了，google没有专门的测试组，SET的manager和developer的是同一个，上班也一起
，开会也一起，主要还是需要开发，具体是不是需要测试也和team有关。
Second 45min
1. why google
2. 有很多个文件信息，每个文件信息里都有一个Person, 以及他的father, mother信
息，设计一个结构，并判断if two persons are related to each other. 婚姻关系不
是related。爷爷和孙子是related。
我搞这个relationship就搞了很久。第一眼觉得应该用LCA做，然后各种往上面套，于
是就悲剧了。
感觉google就是执着于树。。。各位加油。。。 |
|
|
i***h
发帖数: 12655 | |
p*****2
发帖数: 21240 | 32 把food->f2d, tea->t1a
这个没看懂
是SET，不是SDT，这个怎么都没搞清？ |
H****s
发帖数: 247 | 33 第二个是graph吧，用BFS同时从两个端点搜索，应该就能得到 |
x*******6
发帖数: 262 | |
p*****2
发帖数: 21240 | 35 第二题应该是graph吧？
如果有共同祖先就算是有关系的话。DFS就够了。 |
i****y
发帖数: 58 | 36 是啊 我一开始就想往LCA上套，后来发现不对，然后就觉得是graph，但是思路很混乱
，该好好准备一下graph了
【在 p*****2 的大作中提到】
: 第二题应该是graph吧？
: 如果有共同祖先就算是有关系的话。DFS就够了。
|
k***g
发帖数: 58 | 37 整个data structure应该是
class Node {
Node father;
Node mother;
HashSet children;
}
这个应该不是graph，应为没有circle（不会变态的有乱伦关系吧……），整体看起来
像forest
给两个Node N1,N2，从N1用DFS往father, mother两个分支找N2，以及从N2用DFS往
father, mother两个分支找N1。找到即有，找不到即无…… |
p*****2
发帖数: 21240 | 38
不用存children吧？
【在 k***g 的大作中提到】
: 整个data structure应该是
: class Node {
: Node father;
: Node mother;
: HashSet children;
: }
: 这个应该不是graph，应为没有circle（不会变态的有乱伦关系吧……），整体看起来
: 像forest
: 给两个Node N1,N2，从N1用DFS往father, mother两个分支找N2，以及从N2用DFS往
: father, mother两个分支找N1。找到即有，找不到即无……
|
k***g
发帖数: 58 | 39 恩，根据题目要求的确不用存
【在 p*****2 的大作中提到】
:
: 不用存children吧？
|
j********x
发帖数: 2330 | |
|
|
w****x
发帖数: 2483 | 41
不用把, 就是
struct NODE
{
vector relation;
};
就可以了吧
【在 k***g 的大作中提到】
: 整个data structure应该是
: class Node {
: Node father;
: Node mother;
: HashSet children;
: }
: 这个应该不是graph，应为没有circle（不会变态的有乱伦关系吧……），整体看起来
: 像forest
: 给两个Node N1,N2，从N1用DFS往father, mother两个分支找N2，以及从N2用DFS往
: father, mother两个分支找N1。找到即有，找不到即无……
|
h*******e
发帖数: 1377 | 42 couple 不算 related , brothers and sisters算related么 |
p**l
发帖数: 125 | 43 relation题:
如果是related的话, 必定是N1,N2都在同一条path上, 而不是common ancestor(
otherwise husband and wife would be related).
所以从N1开始, 向上走, hash所经过的nodes. 如果N2在hash的nodes里面, 就是
related.
child
/\
father mother
还需要从N2开始, 向上走, 如果N1在经过的nodes里面, 就是related.
两次均没有就是unrelated. Worst case O(n)
class Node
{
Node* father;
Node* monther;
}
【在 i****y 的大作中提到】
: 热腾腾 血淋淋的面经来了。。
: First 45min
: 1. 有一种压缩方式，把food->f2d, tea->t1a，这种，然后现在要搞一个dictionary，
: 问你咋设计，还要实现判断isUnique方法. 我用了trie的变种，用level表示当中那个
: 数字，应该有更好的方法
: class Trie{
: int level;
: ArrayList[] words;
: Trie nextLevelTrie;
: }
|
h*******e
发帖数: 1377 | 44 husband and wife 没有common ancestor...
【在 p**l 的大作中提到】
: relation题:
: 如果是related的话, 必定是N1,N2都在同一条path上, 而不是common ancestor(
: otherwise husband and wife would be related).
: 所以从N1开始, 向上走, hash所经过的nodes. 如果N2在hash的nodes里面, 就是
: related.
: child
: /\
: father mother
: 还需要从N2开始, 向上走, 如果N1在经过的nodes里面, 就是related.
: 两次均没有就是unrelated. Worst case O(n)
|
p**l
发帖数: 125 | 45 which is correct, according to LZ
"婚姻关系不是related。爷爷和孙子是related。"
【在 h*******e 的大作中提到】
: husband and wife 没有common ancestor...
|
h*******e
发帖数: 1377 | 46 我觉得如果和现实相同 brothers 也叫realated 你的算法大体上可用
n1 为root bfs 上走 所有点 做 hash table， 之后n2 本身 和 n2 上走的 点
做hash 如果 第二个 hash 在第一个 hash 表中说明 两个人 related
【在 p**l 的大作中提到】
: which is correct, according to LZ
: "婚姻关系不是related。爷爷和孙子是related。"
|
p**l
发帖数: 125 | 47 可能我没怎么懂你的意思, 如果你想的是以n1为root来做subtree做bfs, 那就误会我的
意思了.
至于child 1 和 child 2 和child n是否是因为兄弟而related. 我不认为这样的假设
有道理. 因为如果是的话, 那同父异母也可以? 当然如果是看blood构成成分的话这就
完全是另一道题了, 比如1/32的father blood和1/64father blood也可能是related.
但这样的不确定性不会用来出题的. 我还是觉得这是一个tree/hashtable的题.
【在 h*******e 的大作中提到】
: 我觉得如果和现实相同 brothers 也叫realated 你的算法大体上可用
: n1 为root bfs 上走 所有点 做 hash table， 之后n2 本身 和 n2 上走的 点
: 做hash 如果 第二个 hash 在第一个 hash 表中说明 两个人 related
|
B***n
发帖数: 84 | 48 有兄弟姐妹怎么办？
比如N1和N2是兄弟
如果兄弟不算related的话，那father，mother要重复出现在N1和N2两个分支？
如果兄弟算related的话，那他们在一个树里面是什么关系？
【在 k***g 的大作中提到】
: 整个data structure应该是
: class Node {
: Node father;
: Node mother;
: HashSet children;
: }
: 这个应该不是graph，应为没有circle（不会变态的有乱伦关系吧……），整体看起来
: 像forest
: 给两个Node N1,N2，从N1用DFS往father, mother两个分支找N2，以及从N2用DFS往
: father, mother两个分支找N1。找到即有，找不到即无……
|
t*******2
发帖数: 292 | 49 你的assumption是近亲不结婚才是这样。。。。。
题目木说，要问问interviewer...
husband and wife 没有common ancestor...
【在 h*******e 的大作中提到】
: husband and wife 没有common ancestor...
|
h*u
发帖数: 122 | |
|
|
w***o
发帖数: 109 | 51 我被问过这个题，面试官说的很清楚，夫妻不算有blood关系，而弟兄姐妹算，每个父
母和所有的儿女算，问如何设计数据结构，使得任给两个person能判断他们是不是有
blood关系。其实就是找两个person是否有共同祖先。
我先说建从父母到子女的有向边的图，然后对图中所有没有祖先的root进行DFS或BFS遍
历，如果某个root的所有子孙同时包含了两个person那他们就有blood关系。
他不满意，不是他想要的答案，又挑不出错，就给了一个函数头，说你没办法access所
有indegree是0的Node，只能从函数提供的参数（两个Node)出发。那我说把有向边掉过
来，注意，跟很多人一样我想当然的认为是没有近亲婚姻的，写了个很简单的DFS，他
不断的提示，我也没想近亲结婚，最后他跳出来画了一个diamond，我才知道要考虑这
种情况。
后来跟他讨论了用着色和HashSet两种方法各自的优缺点。基本就是着色不能thread
safe。看样子他比较喜欢用HashSet。 |
e****e
发帖数: 418 | 52 Directed graph from children to parents.
From persion1, persion2 build set1, set2 by BFS. Also add persion1 in set1,
person2 in set2.
On each step of BFS, compare if there is a common node in set1 and set2.(can
be optimized by only comparing newly added nodes with the other sets to
avoid comparing the same nodes repeatedly.) |
m****t
发帖数: 2329 | 53 why GOOGLE.
如果回答是之一，他们的饭好，会如何，哈哈。
话说，我觉得吃的，真的是个重要的考虑因素。
祝福楼主mm。 |
e***s
发帖数: 799 | 54 第一题没看懂。
第二题
有向图，分别两个节点BFS，走过的放到HASHSET，看有没有重复？有重复则related？ |
v*********3
发帖数: 40 | 55 那请问各位，是同时BFS吗，用两个thread，还是一直走到尽头后，再开始另外一个BFS
，多谢！
【在 e***s 的大作中提到】
: 第一题没看懂。
: 第二题
: 有向图，分别两个节点BFS，走过的放到HASHSET，看有没有重复？有重复则related？
|
e***s
发帖数: 799 | 56 我觉得要能搞出两个thread肯定是更好的，但是要问大牛，怎么考虑thread-safe。。
我也不懂。。。。。
BFS
【在 v*********3 的大作中提到】
: 那请问各位，是同时BFS吗，用两个thread，还是一直走到尽头后，再开始另外一个BFS
: ，多谢！
|
h**i
发帖数: 431 | 57 第一题啥意思，楼主具体说一下，造福后人赞rp
【在 i****y 的大作中提到】
: 热腾腾 血淋淋的面经来了。。
: First 45min
: 1. 有一种压缩方式，把food->f2d, tea->t1a，这种，然后现在要搞一个dictionary，
: 问你咋设计，还要实现判断isUnique方法. 我用了trie的变种，用level表示当中那个
: 数字，应该有更好的方法
: class Trie{
: int level;
: ArrayList[] words;
: Trie nextLevelTrie;
: }
|
D**f
发帖数: 439 | 58 按照父系关系建个树，再按照母系关系建个树，是不是简单些？big-O不会变，但可以
两个threads同时来。 |
