google intern

感谢分享～～～～～～～

serialize by level一下两个树，只不过一个左右一个右左，把val直接拼起来进行hash。这样应该能保证只有极小概率两个不是similartree吧？

我觉得应该会把树编码成字符串，然后比较字符串。因为结点的value，不重要，要比较的是结构，所以所有节点都用字符R表示，空节点用*表示，先序遍历输出一个字符串 "RRR***R**"
比较两棵树的编码字符串是否相等，相等则结构相同。

竟然过了hc...我当时觉得自己两题答得都不完美来着，既然过了就仔细说一下我的做法：

第一题：我本科ee，很惭愧没有学过线程，面试时候我一听到thread就打开了geek for geek搜了一个线程的例子，然后面试时候照猫画虎写，面试完自己在家恶补了几天线程，发现自己照猫画虎写的居然对。。具体就是把自己实现的这个class 变成runnable的，然后在run 里 call start。 当时面试官问我想怎么做，我说我想用一个while loop, 然后用一个boolean值作为开关控制start跑不跑，他说不用这样子，直接在run里call start就可以了。然后在draw function里要实现实时更新月球的地址，我之前学过一点computer graphics, 要使一个object绕另一点转动的计算方法是：1平移至原点，2乘cos sin来绕原点旋转，3平移回去 。面试官没听太懂，但是他人很好，我写完代码后他手算了一下说这个看起来可行，然后他跟我介绍了他期望的方法是横竖平移，也是通过角度来计算x y各平移多少。具体计算角度就是用过了多少时间来计算，我说 java获取当前时间还要声明一个calendar对象，我们时间不多了我直接assume一个getCurrentTime()行吗？面试官说好的没问题。这一轮感觉一直被很好地引导着做题，特别感谢这位面试官。

第二轮，原题很简单不说了，复杂度是n方有一个同学在楼里解释了，跟我想的一样：因为我们要去看两个孩子，而且对两个孩子来说有两种similar的可能性 （排列一样或者flip了），因此每一层的复杂度是4*（num of nodes）, 一共有logN层，所以复杂度是4^logN = N^2. md5 hash 我的做法肯定不好...但当时没有想出特别好的方法，面试官问我会如何实现，我就把怎么level order traversal说了一下，这个至今也没想出一个完美的md5 hash方法，面试结束我问面试官，如果是你的话你会怎么hash?他说最重要的是保存起来你的树的结构....并没有具体说他会怎么做，当时心里还凉凉的，现在也很感谢小哥放我一马。接下来就是跪求team match！！！求捞求解救QAQ

补充内容 (2018-1-20 17:20):
当然结构保证的同时值肯定也得是一样的，1-2 这样的树跟 3-4这样的树肯定不是 similar的..所以楼上有一个说不用考虑值的应该不是很对

wsypeter 发表于 2018-1-20 16:55
竟然过了hc...我当时觉得自己两题答得都不完美来着，既然过了就仔细说一下我的做法：

请问楼主。。从送hc到通知过hc大概用了多久？

bohaohan123 发表于 2018-1-25 13:29
请问楼主。。从送hc到通知过hc大概用了多久？

送hc两周，过hc是一天就过了

wsypeter 发表于 2018-1-20 17:05
第一题：我本科ee，很惭愧没有学过线程，面试时候我一听到thread就打开了geek for geek搜了一个线程的例子 ...

电话面试的时候，还可以查？

第二轮想到一个解法，用dfs，每次都先选小的那个node，按照这个方法serialize 整棵树