狗狗实习两轮面经，求打捞，求鱼塘群～

上周结束的背靠背电面，献出面筋回馈地里。
楼主在国内半夜两点用hangout面的，自认为表现得不够好，毕竟题目都不算难，能过hc真的是运气好。。

第一轮白人女面试官，楼主一开始vpn有问题，连了10多分钟才进聊天室，见到面试官时已经迟到10分钟了，一进去就疯狂道歉。然后让我介绍了一下最挑战的一个项目，如何克服的，自己在团队的角色是什么，问完了开始做题。

问题是，两棵树，如果其中一棵树，可以通过交换其任意数量的节点的left child 和right child，从而得到另一棵树的话，我们就称两颗树相似。题目要求你写一个判断两棵树是否相似的函数（返回true／false）。

楼主用比较intuitive的递归做的，对于每个节点，先不交换left child和right child，递归call，如果递归返回false，再交换left c

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

想到直接送hc还过了，真的是运气不错。。。

求一个选组鱼塘群～～

时间线：
10月初内推
11.12 OA， 拖延症11.20才做
12.7 第一次约背靠背，楼主正值final，往后延了一次
1.3 第二次约背靠背，国内视频面
1.8 送hc
1.10 进pool

希望选组顺利，也祝大家offer多多～





补充内容 (2018-1-13 10:23):
避免歧义。。12.7和1.3分别是第一次约的背靠背时间和第二次约的背靠背时间

粘粘喜气。楼主这过的速度真是惊人啊。。。

chengshuangdao 发表于 2018-2-10 21:57
谢谢，见楼上

还是没太懂啊。。。
像
  1          1
2   3      3  2
这种，这是必须交换的，不交换就绝对不一样
像
  1          1
2   3     2  3
这种，是必须不交换的，交换了就不一样了
我感觉对于每个root而言他的子节点交换不交换是已经确定了的，然后直接dfs子节点，复杂度应该是O(n),因为每个节点只遍历了一遍，感觉不需要递归call来判断用不用换。当然是说所有节点都unique的
还是我对题意的理解有问题么。。。

chengshuangdao 发表于 2018-1-16 23:22
这个你说的有道理。。。我这里好像默认假设所有node unique了，也不记得有没有跟面试官确认过。。
但是 ...

我觉得就算node不是unique，BFS+MAP依然不行啊。譬如下面的结构：
虽然对于两棵树，B的parent都是A，但是他们应该不能算相似吧？
    A                  A
  /                      \
B                        B

补充内容 (2018-2-13 13:59):
sorry，我是说就算node是unique，依然不能判断。

补充内容 (2018-2-13 14:07):
sorry，忽略我吧。我刚刚举的栗子是满足要求的。

沾沾喜气。。真的是速度惊人

请问楼主shuffle数组用的什么方法呢？

请问楼主第一问的followup，如果只把node的val转化成edge list的话好像可能有问题？
比如树(a(a)(a)) 和 (a(a(a)))的edge list一样， 但树不是相似的

appleLeaf 发表于 2018-1-16 16:35
请问楼主shuffle数组用的什么方法呢？

shuffle方法当场不要求写，但也不难，

1. void shuffle(int[] A) {
   
2.   for(int i = 0; i < A.length; i++) {
   
3.     int target = (int) ((i+1)* Math.random());
   
4.     int temp = A[target];
   
5.     A[target] = A[i];
   
6.     A[i] = temp;
   
7.   }
   
8. }

复制代码

appleLeaf 发表于 2018-1-16 16:41
请问楼主第一问的followup，如果只把node的val转化成edge list的话好像可能有问题？
比如树(a(a)(a)) 和 ( ...

这个你说的有道理。。。我这里好像默认假设所有node unique了，也不记得有没有跟面试官确认过。。
但是如果node不是unique的，用bfs+map的方法貌似也不行？因为bfs每一层的顺序也需要考虑了，但是考虑顺序的话，当一个node下两个children相同时又很麻烦，可能需要swap可能不需要swap，这样worst case复杂度可能也到n^2去了。。。

恭喜楼主, 祝早日match

楼主第一题能不能直接把树弄成数组，空的加null，这样子从根开始左右子树分别指针跳转去做类似dfs的查找？