logo
Redian新闻
>未名空间
>PDA - 掌中宝
>
便宜的上网用的tablet，请推荐个
avatar
便宜的上网用的tablet，请推荐个# PDA - 掌中宝
i*y
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就是执着于树。。。各位加油。。。
avatar
c*e
2 楼
也不知道是律师弄错的还是TSC给弄错的。有谁有类似的经验么？这个应该通过啥途径
来纠正比较快速和可靠？
avatar
A*m
3 楼
公司的无线网，我的iphone5没信号，但同事的ipad就有
觉着ipad太贵，不知道有没有便宜的tablet可以用
谢谢
avatar
i*h
4 楼
第二个都不是树
good luck
avatar
b*n
5 楼
Nook HD+? Try it at local B&N stores.

【在 A*******m 的大作中提到】
: 公司的无线网，我的iphone5没信号，但同事的ipad就有
: 觉着ipad太贵，不知道有没有便宜的tablet可以用
: 谢谢
avatar
p*2
6 楼
把food->f2d, tea->t1a
这个没看懂
是SET，不是SDT，这个怎么都没搞清？
avatar
H*s
7 楼
第二个是graph吧，用BFS同时从两个端点搜索，应该就能得到
avatar
x*6
8 楼
1有点像ziv-lampel压缩，但又不是
avatar
p*2
9 楼
第二题应该是graph吧？
如果有共同祖先就算是有关系的话。DFS就够了。
avatar
l*7
10 楼
并查集 disjoint set
avatar
i*y
11 楼
是啊 我一开始就想往LCA上套，后来发现不对，然后就觉得是graph，但是思路很混乱
，该好好准备一下graph了

【在 p*****2 的大作中提到】
: 第二题应该是graph吧？
: 如果有共同祖先就算是有关系的话。DFS就够了。
avatar
k*g
12 楼
整个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。找到即有，找不到即无……
avatar
p*2
13 楼

不用存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。找到即有，找不到即无……
avatar
k*g
14 楼
恩，根据题目要求的确不用存

【在 p*****2 的大作中提到】
:
: 不用存children吧？
avatar
j*x
15 楼
Dag嘛
avatar
w*x
16 楼

不用把, 就是
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。找到即有，找不到即无……
avatar
h*e
17 楼
couple 不算 related , brothers and sisters算related么
avatar
p*l
18 楼
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;
: }
avatar
h*e
19 楼
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)
avatar
p*l
20 楼
which is correct, according to LZ
"婚姻关系不是related。爷爷和孙子是related。"

【在 h*******e 的大作中提到】
: husband and wife 没有common ancestor...
avatar
h*e
21 楼
我觉得如果和现实相同　　brothers 也叫realated 你的算法大体上可用
n1 为root bfs 上走 所有点　做　hash table， 之后n2 本身　和　n2 上走的　点
做hash 如果　第二个　hash 在第一个 hash 表中说明　两个人　related

【在 p**l 的大作中提到】
: which is correct, according to LZ
: "婚姻关系不是related。爷爷和孙子是related。"
avatar
p*l
22 楼
可能我没怎么懂你的意思, 如果你想的是以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
avatar
B*n
23 楼
有兄弟姐妹怎么办？
比如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。找到即有，找不到即无……
avatar
t*2
24 楼
你的assumption是近亲不结婚才是这样。。。。。
题目木说，要问问interviewer...

husband and wife 没有common ancestor...

【在 h*******e 的大作中提到】
: husband and wife 没有common ancestor...
avatar
h*u
25 楼
mark
avatar
w*o
26 楼
我被问过这个题，面试官说的很清楚，夫妻不算有blood关系，而弟兄姐妹算，每个父
母和所有的儿女算，问如何设计数据结构，使得任给两个person能判断他们是不是有
blood关系。其实就是找两个person是否有共同祖先。
我先说建从父母到子女的有向边的图，然后对图中所有没有祖先的root进行DFS或BFS遍
历，如果某个root的所有子孙同时包含了两个person那他们就有blood关系。
他不满意，不是他想要的答案，又挑不出错，就给了一个函数头，说你没办法access所
有indegree是0的Node，只能从函数提供的参数（两个Node)出发。那我说把有向边掉过
来，注意，跟很多人一样我想当然的认为是没有近亲婚姻的，写了个很简单的DFS，他
不断的提示，我也没想近亲结婚，最后他跳出来画了一个diamond，我才知道要考虑这
种情况。
后来跟他讨论了用着色和HashSet两种方法各自的优缺点。基本就是着色不能thread
safe。看样子他比较喜欢用HashSet。
avatar
e*e
27 楼
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.)
avatar
m*t
28 楼
why GOOGLE.
如果回答是之一，他们的饭好，会如何，哈哈。
话说，我觉得吃的，真的是个重要的考虑因素。
祝福楼主mm。
avatar
e*s
29 楼
第一题没看懂。
第二题
有向图，分别两个节点BFS，走过的放到HASHSET，看有没有重复？有重复则related？
avatar
v*3
30 楼
那请问各位，是同时BFS吗，用两个thread，还是一直走到尽头后，再开始另外一个BFS
，多谢！

【在 e***s 的大作中提到】
: 第一题没看懂。
: 第二题
: 有向图，分别两个节点BFS，走过的放到HASHSET，看有没有重复？有重复则related？
avatar
e*s
31 楼
我觉得要能搞出两个thread肯定是更好的，但是要问大牛，怎么考虑thread-safe。。
我也不懂。。。。。

BFS

【在 v*********3 的大作中提到】
: 那请问各位，是同时BFS吗，用两个thread，还是一直走到尽头后，再开始另外一个BFS
: ，多谢！
avatar
h*i
32 楼
第一题啥意思，楼主具体说一下，造福后人赞rp

【在 i****y 的大作中提到】
: 热腾腾 血淋淋的面经来了。。
: First 45min
: 1. 有一种压缩方式，把food->f2d, tea->t1a，这种，然后现在要搞一个dictionary，
: 问你咋设计，还要实现判断isUnique方法. 我用了trie的变种，用level表示当中那个
: 数字，应该有更好的方法
: class Trie{
: int level;
: ArrayList[] words;
: Trie nextLevelTrie;
: }
avatar
i*y
33 楼
热腾腾 血淋淋的面经来了。。
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就是执着于树。。。各位加油。。。
avatar
i*h
34 楼
第二个都不是树
good luck
avatar
p*2
35 楼
把food->f2d, tea->t1a
这个没看懂
是SET，不是SDT，这个怎么都没搞清？
avatar
H*s
36 楼
第二个是graph吧，用BFS同时从两个端点搜索，应该就能得到
avatar
x*6
37 楼
1有点像ziv-lampel压缩，但又不是
avatar
p*2
38 楼
第二题应该是graph吧？
如果有共同祖先就算是有关系的话。DFS就够了。
avatar
i*y
39 楼
是啊 我一开始就想往LCA上套，后来发现不对，然后就觉得是graph，但是思路很混乱
，该好好准备一下graph了

【在 p*****2 的大作中提到】
: 第二题应该是graph吧？
: 如果有共同祖先就算是有关系的话。DFS就够了。
avatar
k*g
40 楼
整个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。找到即有，找不到即无……
avatar
p*2
41 楼

不用存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。找到即有，找不到即无……
avatar
k*g
42 楼
恩，根据题目要求的确不用存

【在 p*****2 的大作中提到】
:
: 不用存children吧？
avatar
j*x
43 楼
Dag嘛
avatar
w*x
44 楼

不用把, 就是
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。找到即有，找不到即无……
avatar
h*e
45 楼
couple 不算 related , brothers and sisters算related么
avatar
p*l
46 楼
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;
: }
avatar
h*e
47 楼
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)
avatar
p*l
48 楼
which is correct, according to LZ
"婚姻关系不是related。爷爷和孙子是related。"

【在 h*******e 的大作中提到】
: husband and wife 没有common ancestor...
avatar
h*e
49 楼
我觉得如果和现实相同　　brothers 也叫realated 你的算法大体上可用
n1 为root bfs 上走 所有点　做　hash table， 之后n2 本身　和　n2 上走的　点
做hash 如果　第二个　hash 在第一个 hash 表中说明　两个人　related

【在 p**l 的大作中提到】
: which is correct, according to LZ
: "婚姻关系不是related。爷爷和孙子是related。"
avatar
p*l
50 楼
可能我没怎么懂你的意思, 如果你想的是以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
avatar
B*n
51 楼
有兄弟姐妹怎么办？
比如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。找到即有，找不到即无……
avatar
t*2
52 楼
你的assumption是近亲不结婚才是这样。。。。。
题目木说，要问问interviewer...

husband and wife 没有common ancestor...

【在 h*******e 的大作中提到】
: husband and wife 没有common ancestor...
avatar
h*u
53 楼
mark
avatar
w*o
54 楼
我被问过这个题，面试官说的很清楚，夫妻不算有blood关系，而弟兄姐妹算，每个父
母和所有的儿女算，问如何设计数据结构，使得任给两个person能判断他们是不是有
blood关系。其实就是找两个person是否有共同祖先。
我先说建从父母到子女的有向边的图，然后对图中所有没有祖先的root进行DFS或BFS遍
历，如果某个root的所有子孙同时包含了两个person那他们就有blood关系。
他不满意，不是他想要的答案，又挑不出错，就给了一个函数头，说你没办法access所
有indegree是0的Node，只能从函数提供的参数（两个Node)出发。那我说把有向边掉过
来，注意，跟很多人一样我想当然的认为是没有近亲婚姻的，写了个很简单的DFS，他
不断的提示，我也没想近亲结婚，最后他跳出来画了一个diamond，我才知道要考虑这
种情况。
后来跟他讨论了用着色和HashSet两种方法各自的优缺点。基本就是着色不能thread
safe。看样子他比较喜欢用HashSet。
avatar
e*e
55 楼
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.)
avatar
m*t
56 楼
why GOOGLE.
如果回答是之一，他们的饭好，会如何，哈哈。
话说，我觉得吃的，真的是个重要的考虑因素。
祝福楼主mm。
avatar
e*s
57 楼
第一题没看懂。
第二题
有向图，分别两个节点BFS，走过的放到HASHSET，看有没有重复？有重复则related？
avatar
v*3
58 楼
那请问各位，是同时BFS吗，用两个thread，还是一直走到尽头后，再开始另外一个BFS
，多谢！

【在 e***s 的大作中提到】
: 第一题没看懂。
: 第二题
: 有向图，分别两个节点BFS，走过的放到HASHSET，看有没有重复？有重复则related？
avatar
e*s
59 楼
我觉得要能搞出两个thread肯定是更好的，但是要问大牛，怎么考虑thread-safe。。
我也不懂。。。。。

BFS

【在 v*********3 的大作中提到】
: 那请问各位，是同时BFS吗，用两个thread，还是一直走到尽头后，再开始另外一个BFS
: ，多谢！
avatar
h*i
60 楼
第一题啥意思，楼主具体说一下，造福后人赞rp

【在 i****y 的大作中提到】
: 热腾腾 血淋淋的面经来了。。
: First 45min
: 1. 有一种压缩方式，把food->f2d, tea->t1a，这种，然后现在要搞一个dictionary，
: 问你咋设计，还要实现判断isUnique方法. 我用了trie的变种，用level表示当中那个
: 数字，应该有更好的方法
: class Trie{
: int level;
: ArrayList[] words;
: Trie nextLevelTrie;
: }
avatar
D*f
61 楼
按照父系关系建个树，再按照母系关系建个树，是不是简单些？big-O不会变，但可以
两个threads同时来。
相关阅读
out了，G+是什么？请问Tomtom 1505 怎么样用金刚dock的同修们first google ebook device this week at targetnook touch看中文怎么样Apple iPhone 3GS Used 16GB @ Amazon.com $187看了一下午小人书发现许茹芸在g+上面求助，如何升级MIO C320 地图apple吵着要办掉s2啊现在page plus是不是没有一年2000min的prepaid了？大家有没有发现升级android 2.2之后。。。virgin mobile的信号覆盖区域大吗?问一下行情kindle 3g $139 from Amazon请推荐一款T-Mobile的手机转Virgin Mobile能保留号码吗？xoom32gb$399 狗轮没理由不买了吧这回这两个HD2有啥不同?包子求kindle SO 25 off 50 baby item
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。